Makespan Minimization on Parallel Batch Processing Machines with Release Times and Job Sizes

Abstract

[1] Chandru, V., Lee, C.-Y., & Uzsoy, R. (1993). Minimizing total completion time on batch processing machines. International Journal of Production Research, 31, 2097–2121.
http://dx.doi.org/10.1080/00207549308956847

[2] Lee, C.-Y., Uzsoy, R., & Martin-Vega, L. A. (1992). Efficient algorithms for scheduling semiconductor burn-in operations. Operation Research, 40, 764–775.
http://dx.doi.org/10.1287/opre.40.4.764

[3] Sung, C. S., & Choung, Y. I. (2000). Minimizing makespan on a single burn-in oven in semiconductor manufacturing. European Journal of Operational Research, 120, 559–574.
http://dx.doi.org/10.1016/S0377-2217(98)00391-9

[4] Lee, C.-Y., & Uzsoy, R. (1999). Minimizing makespan on a single batch processing machine with dynamic job arrivals. International Journal of Production Research, 37, 219–236.
http://dx.doi.org/10.1080/002075499192020

[5] Shuguang Li, Guojun Li, Shaoqiang Zhang. (2005). Minimizing makespan with release times on identical parallel batching machines. Discrete Applied Mathematics, 148, 127–134.
http://dx.doi.org/10.1016/j.dam.2004.11.004

[6] Shuguang Li, Guojun Li, Shaoqiang Zhang. Minimizing maximum lateness on identical parallel batch processing machines. Lecture Notes in Computer Science 3106: Proceedings of the 10th Annual International Conference on Computing and Combinatorics, 229–237, 2004.

[7] Dupont, L., & Ghazvini, F. J. (1997). A branch and bound algorithm for minimizing mean flow time on a single batch processing machine. International Journal of Industrial Engineering, 4, 197–203.

[8] Qi, X., & Tu, F. (1999). Earliness and tardiness scheduling problems on a batch processor. Discrete Applied Mathematics, 98, 131–145.
http://dx.doi.org/10.1016/S0166-218X(99)00113-4

[9] Wang, C.-S., & Uzsoy, R. (2002). A genetic algorithm to minimize maximum lateness on a batch processing machine. Computers &Operations Research, 29, 1621–1640.
http://dx.doi.org/10.1016/S0305-0548(01)00031-4

[10] Uzsoy, R. (1994). Scheduling a single batch processing machine with non-identical job sizes. International Journal of Production Research, 32, 1615–1635.
http://dx.doi.org/10.1080/00207549408957026

[11] Zhang, G., Cai, X., Lee, C.-Y., & Wong, C. K. (2001). Minimizing makespan on a single batch processing machine with nonidentical job sizes. Naval Research Logistics, 48, 226–240.
http://dx.doi.org/10.1002/nav.4

[12] Shuguang Li, Guojun Li, Xiaoli Wang, Qiming Liu. Minimizing Makespan on a Single Batching Machine with Release Times and Non-Identical Job Sizes. Operations Research Letters, 33(2): 157–164, 2005.
http://dx.doi.org/10.1016/j.orl.2004.04.009

[13] Q.Q. Nong, C.T. Ng and T.C.E. Cheng (2008). The bounded single-machine parallel-batching scheduling problem with family jobs and release dates to minimize makespan, Operations Research Letters, 36(1), 61-66.
http://dx.doi.org/10.1016/j.orl.2007.01.007

[14] Dupont, L., & Dhaenens-Flipo, C. (2002). Minimizing the makespan on a batch machine with non-identical job sizes: An exact procedure. Computers & Operations Research, 29, 807–819.
http://dx.doi.org/10.1016/S0305-0548(00)00078-2

[15] Chung, S. H., Tai, Y. T., & Pearn, W. L. (2008). Minimising makespan on parallel batch processing machines with non-identical ready time and arbitrary job sizes. International Journal of Production Research. doi:10.1080/00207540802010807.
http://dx.doi.org/10.1080/00207540802010807

[16] Wang Hui-Mei and Fuh-Der Chou (2010). Solving the parallel batch-processing machines with different job sizes, and capacity limits by metaheuristics. Expert Systems with Applications, 37, 1510-1521.
http://dx.doi.org/10.1016/j.eswa.2009.06.070

[17] Chang, P.-C., & Wang, H.-M. (2004). A heuristic for a batch processing machine scheduled to minimize total completion time with non-identical job sizes. International Journal of Advanced Manufacturing Technology, 24, 615–620.
http://dx.doi.org/10.1007/s00170-003-1740-9

[18] Ghazvini, F. J., & Dupont, L. (1998). Minimizing mean flow times criteria on a single batch processing machine with non-identical jobs sizes. International Journal of Production Economics, 55, 273–280.
http://dx.doi.org/10.1016/S0925-5273(98)00067-X

[19] F. Afrati, E., C. Chekuri, D. Karger, C. Kenyon, S. Khanna, I. Milis, M. Queyranne, M. Skutella, C. Stein, M. Sviridenko (1999). Approximation schemes for minimizing average weighted completion time with release dates, Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, New York, October, 32–43.

[20] R. L. Graham (1966). Bounds for certain multiprocessor anomalies. Bell System Technical Journal, 45: 1563–1581.

[21] Melouk S, Damodaran P, Chang P-Y. Minimizing makespan for single machine batch processing with non-identical job sizes using simulated annealing. International Journal of Production Economics, 2004, 87: 141–7.
http://dx.doi.org/10.1016/S0925-5273(03)00092-6

[22] 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, 2006, 44: 2337–60.
http://dx.doi.org/10.1080/00207540500525254

[23] 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, 2005, 98: 81–96.
http://dx.doi.org/10.1016/j.ijpe.2004.10.001

[24] Chou FD, Chang PC, Wang HM. A hybrid genetic algorithm to minimize makespan for the single batch machine dynamic scheduling problem. International Journal of Advanced Manufacturing Technology, 2006, 31: 350–9.
http://dx.doi.org/10.1007/s00170-005-0194-7

[25] Chou FD. A joint GA+DP approach for single burn-in oven scheduling problems with makespan criterion. International Journal of Advanced Manufacturing Technology, 2007, 35: 587–95.
http://dx.doi.org/10.1007/s00170-006-0738-5

[26] N. Rafiee Parsa, B. Karimi, A. Husseinzedeh Kashan. A branch and bound algorithm to minimize makespan on a single batch processing machine with non-identical job sizes. Computers & Operations Research, 2010, 37 (10): 1720-1730.
http://dx.doi.org/10.1016/j.cor.2009.12.007

[27] Husseinzadeh Kashan A, Karimi B, Jolai F. Bi-criteria scheduling on a single batch processing machine with non-identical job sizes. In: Proceeding of the 12th IFAC symposium on information control problems in manufacturing, INCOM’2006, St-Etienne, France, 2006b.

[28] Koh S-G, Koo P-H, Ha J-W, Lee W-S. Scheduling parallel batch processing machines with arbitrary job sizes and incompatible job families. International Journal of Production Research, 2004, 42: 4091–41107.
http://dx.doi.org/10.1080/00207540410001704041

[29] Chang P Y, Damodaran P, Melouk S. Minimizing makespan on parallel batch processing machines. International Journal of Production Research, 2004, 42: 4211–20.
http://dx.doi.org/10.1080/00207540410001711863

[30] Husseinzadeh Kashan A, Karimi B, Jenabi M. A hybrid genetic heuristic for scheduling parallel batch processing machines with arbitrary job sizes. Computers & Operations Research, 2008, 35: 1084–98.
http://dx.doi.org/10.1016/j.cor.2006.07.005