New Lower Bounds for the Optimal Makespan on a Single Batch Processing Machine

Document Type : Research Article

Authors

Abstract

This paper considers minimizing makespan (Cmax) on a single batch-processing machine. A batch-processing machine can process a group of jobs simultaneously, as long as the total size of jobs in the batch does not exceed the machine capacity (B). For each job, we assume a specific job size and job processing time. The processing time of a batch is just the longest processing time of all jobs in the batch. We introduce two new procedures for obtaining lower bounds of the optimal makespan, entitled LB2 and LB3, respectively. We prove that both of the new bounds are tighter than the only existing bound called LB1. We also prove that LB3 is at least as tight as LB2.

Keywords

References

[1] حسین زاده کاشان، علی؛ “ارائه حدود بالا و پایین برای مسائل زمانبندی تک ماشین و جریان کارگاهی در سیستمهای تولید انباشتهای با فرض وجود نیازمندی ظرفیتی متفاوت برای کارها”. رساله دکتری مهندسی صنایع، دانشگاه صنعتی امیرکبیر، 1388
[2] Azizoglu, M.; Webster, S.; “Scheduling a batch processing machine with incompatible job families”. Computers & Industrial Engineering, vol. 39, p.p. 325-335, 2000.
[3] Boudhar, M.; Finke, G.; “Scheduling on a batch machine with job compatibilities”, Belgian Journal of Operations Research, Statistics and Computer Science, vol. 40, p.p. 69–80, 2000.
[4] Chang, P.Y.; Damodaran, P.; Melouk, S.; “Minimizing makespan on parallel batch processing machines”, International Journal of Production Research, vol. 42, p.p. 4211-4220, 2004.
[5] Damodaran, P., Chang, P.Y.; “Heuristics to minimize makespan of parallel batch processing machines”, International Journal of Advance Manufacturing Technology, vol. 37, p.p. 1005-1013, 2008.
[6] Damodaran, P.; Manjeshwar, P.K.; Srihari, K.; “Minimizing makespan on a batch-processing machine with non-identical job sizes using genetic algorithms”, International journal of production economics, vol. 103, p.p. 882-891, 2006.
[7] Damodaran, P.; Srihari, K.; “Mixed integer formulation to minimize makespan in flow shop with batch processing machines”. Mathematical and Computer Modeling, vol. 40, p.p. 1465-1472, 2004.
[8] Dobson, G.; Nambimadom, R.S.; “The batch loading and scheduling problem”, Research Report, Simon School of Business Administration. University of Rochester, Rochester, NY, 1992.
[9] Dupont, L.; Dhaenens-Flipo, C.; “Minimizing the makespan on a batch machine with non-identical job sizes: an exact procedure”, Computers & Operations Research, vol. 29, p.p. 807-819,2002.
[10] Dupont, L.; Jolai Ghazvini, F.; “Minimizing Makespan on a Single Batch Processing Machine with Non identical Job Sizes”, European journal of Automation Systems, vol. 32, p.p. 431-440, 1998.
[11] Husseinzadeh Kashan, A.; Karimi, B.; “Scheduling a single batch-processing machine with arbitrary job sizes and incompatible job families: an ant colony framework”, Journal of the Operational Research Society, vol. 59, p.p. 1269-1280, 2008.
[12] Husseinzadeh Kashan, A.; Karimi, B.; “An improved mixed integer linear formulation and several lower bounds for minimizing makespan on a flowshop with batch processing machines”, International Journal of Advanced manufacturing Technology, vol. 40, p.p. 582-594, 2009.
[13] Husseinzadeh Kashan, A.; Karimi, B.; Fatemi Ghomi, S.M.T.; “A note on: Minimizing makespan on a single batch processing machine with non-identical job sizes”, Theoretical Computer Science, vol. 410, p.p. 2754-2758, 2009.
[14] Husseinzadeh Kashan, A.; Karimi, B.; Jenabi, M.; “A hybrid genetic heuristic for scheduling parallel batch processing machines with arbitrary job sizes”, Computers & Operations Research, vol. 35, p.p. 1084-1098, 2008.
[15] Husseinzadeh Kashan, A.; Karimi, B.; Jolai, F.; “Effective hybrid genetic algorithm for minimizing makespan on a single-batch-processing machine with non-identical job sizes”, International Journal of Production Research, vol. 44, p.p. 2337-2360, 2006.
[16] Husseinzadeh Kashan, A.; Karimi, B.; Jolai, F.; “An effective hybrid multi-objective genetic algorithm for bi-criteria scheduling on a single batch processing machine with non-identical job sizes”. Engineering Applications of Artificial Intelligence, vol. 23, p.p. 911-922, 2010.
[17] Koh, S.G.; Koo, P.H.; Kim, D.C.; Hur, W.S.; “Scheduling a single-batch-processing machine with arbitrary job sizes and incompatible job families”, International Journal of Production Economics, vol. 98, p.p. 81–96, 2005.
[18] Lee, C.Y.; Uzsoy, R.; Martin-Vega, L.A.; “Efficient Algorithms for Scheduling Semiconductor Burn-in Operations”, Operations Research, vol. 40, p.p. 764-775, 1992.
[19] Liao L.M.; Huang, C.J.; “Tabu search heuristic for two-machine flowshop with batch processing machines”, Computers & Industrial Engineering, In Press, 2010.
[20] Mathirajan, M.; Sivakumar, A.I.; “A Literature Review, Classification and Simple Meta-analysis on Scheduling of Batch Processors in Semiconductor”,International Journal of Advanced Manufacturing Technology, vol. 29, p.p. 990-1001, 2006.
[21] Melouk, S.; Damodaran, P.; Cheng, P.Y.; “Minimizing make span for single machine batch processing with non-identical job sizes using simulated annealing”, International Journal of Production Economics, vol. 87,p.p. 141-147, 2004.
[22] Rafiee Parsa, N.; Karimi, B.; Husseinzadeh Kashan, A.; “A branch and price algorithm to minimize makespan on a single batch processing machine with non-identical job sizes”, Computers & Operations Research, vol. 37, p.p. 1720-1730, 2010.
[23] Uzsoy, R.; “A Single Batch Processing Machine with Non-identical Job Sizes”, International Journal of
Production Research, vol. 32, p.p. 1615-1635, 1994.
[24] Wang, H.M.; Chou, F.D.; “Solving the parallel batch- processing machines with different release times, job sizes, and capacity limits by metaheuristics”, Expert Systems with Applications, vol 37. p.p. 1510-1521,2010.
[25] Zhang, G.; Cai, X.; Lee, C.Y.; Wong, C.K.; “Minimizing makespan on a single batch processing machine with nonidentical job sizes”, Naval Research Logistics, vol. 48, p.p. 226-240, 2001.
[26] Zhang, W.G.; Chen, H.P.; Lu, D.; Shao, H.; “A Novel Differential Evolution Algorithm for a Single Batchprocessing
Machine with Non-identical Job Sizes”,Proc. Fourth International Conference on Natural Computation, p.p. 447-451, 2008.
[27] Zhang, Y.L.; Chen, H.P.; Shao, H.; Xu, R.; “Minimizing Makespan for Single Batch Processing Machine with Non-identical Job Sizes Using a Novel Algorithm: Free Search”, Proc. International Conference on Information Technology and Computer
Science p.p. 180-183, 2009.

Files

Share

How to cite

Statistics