Abstract
The common due window scheduling problem with batching on a single machine is dealt with to minimize the total penalty of weighted earliness and tardiness. In this paper it is assumed that a job incurs no penalty as long as it is completed within the common due window. The problem is extended to the environment of non-identical job sizes. Then several optimal properties are given to schedule batches effectively. And by introducing the concept of PRN, it is proven that the PRN of each batch should be made as small as possible in order to minimize the objective. Based on these properties, an algorithm F-PRN for batch forming is proposed for the problem.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Kramer, F.J., Lee, C.Y.: Common due-window scheduling. Prod. Oper. Manage. 2(4), 262–275 (1993)
Liman, S.D., Panwalkar, S.S., Thong, S.: Determination of common due window location in a single machine scheduling problem. Eur. J. Oper. Res. 93, 68–74 (1996)
Liman, S.D., Panwalkar, S.S., Thong, S.: Common due window size and location determination in a single machine scheduling. J. Oper. Res. Soc. 49, 1007–1010 (1998)
Weng, M.X., Ventura, J.A.: A note on common due window scheduling. Prod. Oper. Manage. 5, 194–200 (1995)
Hongluan, Z.H.A.O., Guojun, L.I.: Unbounded batch scheduling with a common due window on a single machine. J. Syst. Sci. Complexity 21(2), 296–303 (2008)
Ikura, Y., Gimple, M.: Efficient scheduling algorithms for a single batch processing machine. Oper. Res. Lett. 5(2), 61–65 (1986)
Li, C.L., Lee, C.Y.: Scheduling with agreeable release times and due dates on a batch processing machine. Eur. J. Oper. Res. 96(3), 564–569 (1997)
Pan, Q., Zhou, B.: Dynamic scheduling algorithm for E/T problem in furnace district of semiconductor fab. Semicond. Technol. 33(7), 639–643 (2008)
Yin, Y., Cheng, T., Xu, D., Wu, C.: Common due date assignment and scheduling with a rate-modifying activity to minimize the due date, earliness, tardiness, holding, and batch delivery cost. Comput. Ind. Eng. 63(1), 223–234 (2012)
Xu, R., Chen, H., Li, X.: Makespan minimization on single batch-processing machine via ant colony optimization. Comput. Oper. Res. 39(3), 582–593 (2012)
Uzsoy, R.: Scheduling a single batch processing machine with nonidentical job sizes. Int. J. Prod. Res. 32(7), 1615–1635 (1994)
Sung, C.S., Choung, Y.I., Fowler, J.W.: Heuristic algorithm for minimizing earliness–tardiness on single burn-in oven in semiconductor manufacturing. In: Proceedings of MASM, pp. 217–222. Tempe, Arizona (2002)
Damodaran, P., Manjeshwar, P.K., Srihari, K.: Minimizing makespan on a batch processing machine with non-identical job sizes using genetic algorithms. Int. J. Prod. Econ. 103(2), 882–891 (2006)
Chen, H., Du, B., Huang, G.Q.: Scheduling a batch processing machine with non-identical job sizes: A clustering perspective. Int. J. Prod. Res. 49(19), 5755–5778 (2011)
Deng, X., Li, G., Feng, H., et al.: A PTAS for semiconductor burn-in scheduling. J. Comb. Optim. 9(1), 5–17 (2005)
Acknowledgments
This paper is supported by NSFC of Shandong Province (ZR2012GQ010), Development Projects of Science and Technology of Shandong Province (2015GGX101047, 2015GGX101018), and Ji’nan Higher Educational Independent Innovation Plan (201303001, 201401214).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Zhao, H., Han, G., Xu, G. (2016). The Bounded Batch Scheduling with Common Due Window and Non-identical Size Jobs. In: Zhu, D., Bereg, S. (eds) Frontiers in Algorithmics. FAW 2016. Lecture Notes in Computer Science(), vol 9711. Springer, Cham. https://doi.org/10.1007/978-3-319-39817-4_24
Download citation
DOI: https://doi.org/10.1007/978-3-319-39817-4_24
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-39816-7
Online ISBN: 978-3-319-39817-4
eBook Packages: Computer ScienceComputer Science (R0)