Solving the Unrelated Parallel Batch Machine Scheduling Problem with Mixed-Integer Programming

Öz

In this study, the problem of scheduling jobs with arbitrary sizes and non-zero release times on a set of unrelated parallel batch processing machines with different capacities is discussed. Three mixed-integer programming models with different objective functions are developed to solve the problem. Corresponding models aim at minimizing (i) the total flow time, (ii) the makespan and (iii) the total tardiness, respectively, which are considered to be among the most important objectives in scheduling problems. In order to test the validity and applicability of the proposed solution approach, different datasets are generated using some rules in the literature. The results obtained by solving the mathematical programming models with these data sets are analyzed in terms of some performance parameters.

Anahtar Kelimeler

• Unrelated parallel batch processing
• machine scheduling
• total flow time
• makespan
• total tardiness
• mixed-integer programming

Bağlantısız Paralel Parti Üretimi Yapan Makine Çizelgeleme Probleminin Karışık-Tamsayılı Programlama ile Çözümü

Öz

Bu çalışmada, keyfi boyutlara ve sıfır olmayan hazır olma zamanlarına sahip işlerin farklı kapasitelere sahip bir dizi bağlantısız paralel parti üretimi yapan makinelerde çizelgelenmesi problemi ele alınmıştır. Problemin çözümü için farklı amaç fonksiyonlarına sahip üç karışık-tamsayılı programlama modeli geliştirilmiştir. Bu modeller, sırasıyla, çizelgeleme problemlerinde en önemli amaçlar arasında bulunan (i) toplam akış süresini, (ii) son işin tamamlanma zamanını ve (iii) toplam gecikmeyi minimize etmeyi amaçlamaktadır. Sunulan çözüm yaklaşımının doğruluğunun ve uygulanabilirliğinin test edilmesi amacıyla, literatürdeki birtakım kurallar doğrultusunda farklı veri setleri üretilmiştir. Matematiksel programlama modellerinin bu veri setleri ile çözülmesiyle birlikte elde edilen sonuçlar çeşitli performans parametreleri açısından analiz edilmiştir.

Anahtar Kelimeler

• Bağlantısız paralel parti üretimi
• makine çizelgeleme
• toplam akış süresi
• son işin tamamlanma zamanı
• toplam gecikme
• karışık-tamsayılı programlama

Kaynakça

1. [1] Chang P. Y., Damodaran P. and Melouk S., “Minimizing makespan on parallel batch processing machines”, International Journal of Production Research, 42(19), 4211-4220, (2004).
2. [2] Stefansson H., Sigmarsdottir S., Jensson P. and Shah N., “Discrete and continuous time representations and mathematical models for large production scheduling problems: A case study from the pharmaceutical industry”, European Journal of Operational Research, 215(2), 383-392, (2011).
3. [3] Mönch L., Fowler J. W., Dauzère-Pérès S., Mason S. J. and Rose O., “A survey of problems, solution techniques, and future challenges in scheduling semiconductor manufacturing operations”, Journal of scheduling, 14(6), 583-599, (2011).
4. [4] Arroyo J. E. C. and Leung J. Y. T., “An effective iterated greedy algorithm for scheduling unrelated parallel batch machines with non-identical capacities and unequal ready times”, Computers & Industrial Engineering, 105, 84-100, (2017).
5. [5] Arroyo J. E. C., Leung J. Y. T. and Tavares R. G., “An iterated greedy algorithm for total flow time minimization in unrelated parallel batch machines with unequal job release times”, Engineering Applications of Artificial Intelligence, 77, 239-254, (2019).
6. [6] Ceylan Z., Karan R. E., Bakırcı Ç. ve Sabuncu S., “Sıra Bağımlı Hazırlık Süreli Tek Makine Çizelgeleme Problemi: Beyaz Eşya Sektöründe Bir Uygulama”, International Journal of Multidisciplinary Studies and Innovative Technologies, 3(1), 14-21, (2019).
7. [7] Chu C., “A branch‐and‐bound algorithm to minimize total tardiness with different release dates”, Naval Research Logistics (NRL), 39(2), 265-283, (1992).
8. [8] Kaya S., “A genetic algorithm for the resource constraıned project scheduling problem having a single machine with sequence dependent setup times”, MSc Thesis, Middle East Technical University, (2013).

9. [9] Chen W. J., “Minimizing total flow time in the single-machine scheduling problem with periodic maintenance” Journal of the Operational Research Society, 57(4), 410-415, (2006).
10. [10] Kanet J. J., “Minimizing the average deviation of job completion times about a common due date”, Naval Research Logistics Quarterly, 28(4), 643-651, (1981).
11. [11] Arkin E. M. and Roundy R. O., “Weighted-tardiness scheduling on parallel machines with proportional weights”, Operations Research, 39(1), 64-81, (1991).
12. [12] De P., Ghosh J. B. and Wells C. E., “Due‐date assignment and early/tardy scheduling on identical parallel machines”, Naval Research Logistics (NRL), 41(1), 17-32, (1994).
13. [13] Balakrishnan N., Kanet J. J. and Sridharan V., “Early/tardy scheduling with sequence dependent setups on uniform parallel machines”, Computers & Operations Research, 26(2), 127-141, (1999).
14. [14] De CM Nogueira J. P., Arroyo J. E. C., Villadiego H. M. M. and Gonçalves L. B., “Hybrid GRASP heuristics to solve an unrelated parallel machine scheduling problem with earliness and tardiness penalties”, Electronic Notes in Theoretical Computer Science, 302, 53-72, (2014).
15. [15] Gedik R., Kalathia D., Egilmez G. and Kirac E., “A constraint programming approach for solving unrelated parallel machine scheduling problem”, Computers & Industrial Engineering, 121, 139-149, (2018).
16. [16] Kaya S. ve Saraç T., “Plasti̇k enjeksi̇yon maki̇neleri̇ni̇n vardi̇ya bazinda çi̇zelgelenmesi̇ problemi̇ i̇çi̇n bi̇r hedef programlama modeli̇”, Endüstri Mühendisliği Dergisi, 24(1), 12, (2013).
17. [17] Eren T. ve Güner E., “Paralel Makineli Çizelgelemede Toplam Tamamlanma Zamanı ve Maksimum Gecikmenin Enküçüklenmesi”, Selçuk Üniversitesi Mühendislik, Bilim Ve Teknoloji Dergisi, 21(1), 21-32, (2006).
18. [18] Xu D. and Yang D. L., “Makespan minimization for two parallel machines scheduling with a periodic availability constraint: mathematical programming model, average-case analysis, and anomalies”, Applied Mathematical Modelling, 37(14-15), 7561-7567, (2013).
19. [19] Yang-Kuei L. and Chi-Wei L., “Dispatching rules for unrelated parallel machine scheduling with release dates”, The International Journal of Advanced Manufacturing Technology, 67(1-4), 269-279, (2013).
20. [20] Sivrikaya-Şerifoǧlu F. and Ulusoy G., “Parallel machine scheduling with earliness and tardiness penalties”, Computers & Operations Research, 26(8), 773-787, (1999).
21. [21] Ikura Y. and Gimple M., “Efficient scheduling algorithms for a single batch processing machine”, Operations Research Letters, 5(2), 61-65, (1986).
22. [22] Jin M., Liu X. and Luo W., “Single-machine parallel-batch scheduling with nonidentical job sizes and rejection”, Mathematics, 8(2), 258, (2020).
23. [23] Herr O. and Goel A., “Comparison of two integer programming formulations for a single machine family scheduling problem to minimize total tardiness”, Procedia CIRP, 19, 174-179, (2014).
24. [24] Gokhale R. and Mathirajan M., “Minimizing total weighted tardiness on heterogeneous batch processors with incompatible job families”, The International Journal of Advanced Manufacturing Technology, 70(9-12), 1563-1578, (2014).
25. [25] Zhang H., Wu F. and Yang Z., “Hybrid approach for a single-batch-processing machine scheduling problem with a just-in-time objective and consideration of non-identical due dates of jobs”, Computers & Operations Research, 128, 105194, (2021).
26. [26] Zheng S., Xie N. and Wu Q., “Single batch machine scheduling with dual setup times for autoclave molding manufacturing”, Computers & Operations Research, 133, 105381, (2021).
27. [27] Muter İ., “Exact algorithms to minimize makespan on single and parallel batch processing machines”, European Journal of Operational Research, 285(2), 470-483, (2020).
28. [28] Abedi M., Seidgar H., Fazlollahtabar H. and Bijani R., “Bi-objective optimisation for scheduling the identical parallel batch-processing machines with arbitrary job sizes, unequal job release times and capacity limits”, International Journal of Production Research, 53(6), 1680-1711, (2015).
29. [29] Bilyk A., Mönch L. and Almeder C., “Scheduling jobs with ready times and precedence constraints on parallel batch machines using metaheuristics”, Computers & Industrial Engineering, 78, 175-185, (2014).
30. [30] Chung S. H., Tai Y. T. and Pearn W. L., “Minimising makespan on parallel batch processing machines with non-identical ready time and arbitrary job sizes”, International Journal of Production Research, 47(18), 5109-5128, (2009).
31. [31] Damodaran P. and Vélez-Gallego M. C., “A simulated annealing algorithm to minimize makespan of parallel batch processing machines with unequal job ready times”, Expert systems with Applications, 39(1), 1451-1458, (2012).
32. [32] Jia Z., Li X. and Leung J. Y. T., “Minimizing makespan for arbitrary size jobs with release times on P-batch machines with arbitrary capacities”, Future Generation Computer Systems, 67, 22-34, (2017).
33. [33] Kashan A. H., Karimi B. and Jenabi M., “A hybrid genetic heuristic for scheduling parallel batch processing machines with arbitrary job sizes”, Computers & Operations Research, 35(4), 1084-1098, (2008).
34. [34] Koh S. G., Koo P. H., Ha J. W. and Lee W. S., “Scheduling parallel batch processing machines with arbitrary job sizes and incompatible job families”, International Journal of Production Research, 42(19), 4091-4107, (2004).
35. [35] Ozturk O., Espinouse M. L., Mascolo M. D. and Gouin A., “Makespan minimisation on parallel batch processing machines with non-identical job sizes and release dates”, International Journal of Production Research, 50(20), 6022-6035, (2012).
36. [36] Zhou S., Liu M., Chen H. and Li X., “An effective discrete differential evolution algorithm for scheduling uniform parallel batch processing machines with non-identical capacities and arbitrary job sizes”, International Journal of Production Economics, 179, 1-11, (2016).
37. [37] Wang J. Q. and Leung J. Y. T., “Scheduling jobs with equal-processing-time on parallel machines with non-identical capacities to minimize makespan”, International Journal of Production Economics, 156, 325-331, (2014).
38. [38] Mönch L., Balasubramanian H., Fowler J. W. and Pfund M. E., “Heuristic scheduling of jobs on parallel batch machines with incompatible job families and unequal ready times”, Computers & Operations Research, 32(11), 2731-2750, (2005).
39. [39] Gong H., Chen D. and Xu K., “Parallel-batch scheduling and transportation coordination with waiting time constraint”, The Scientific World Journal, (2014).
40. [40] Rocholl J., Mönch L. and Fowler J., “Bi-criteria parallel batch machine scheduling to minimize total weighted tardiness and electricity cost”, Journal of Business Economics, 90(9), 1345-1381, (2020).
41. [41] Zhang H., Jia Z. H. and Li K., “Ant colony optimization algorithm for total weighted completion time minimization on non-identical batch machines”, Computers & Operations Research, 117, 104889, (2020).
42. [42] Ozturk O., “A truncated column generation algorithm for the parallel batch scheduling problem to minimize total flow time”, European Journal of Operational Research, 286(2), 432-443, (2020).
43. [43] Fowler J. W. and Mönch L., “A survey of scheduling with parallel batch (p-batch) processing”, European Journal of Operational Research, (2021).
44. [44] Arroyo J. E. C. and Leung J. Y. T., “Scheduling unrelated parallel batch processing machines with non-identical job sizes and unequal ready times”, Computers & Operations Research, 78, 117-128, (2017).
45. [45] Li X., Huang Y., Tan Q. and Chen H., “Scheduling unrelated parallel batch processing machines with non-identical job sizes”, Computers & operations research, 40(12), 2983-2990, (2013).
46. [46] Shahidi-Zadeh B., Tavakkoli-Moghaddam R., Taheri-Moghadam A. and Rastgar I., “Solving a bi-objective unrelated parallel batch processing machines scheduling problem: A comparison study”, Computers & Operations Research, 88, 71-90, (2017).
47. [47] Klemmt A., Weigert G., Almeder C. and Mönch L., “A comparison of MIP-based decomposition techniques and VNS approaches for batch scheduling problems”, In Proceedings of the 2009 Winter Simulation Conference (WSC), 1686-1694, IEEE., (2009).
48. [48] Che Y., Hu K., Zhang Z. and Lim A., “Machine scheduling with orientation selection and two-dimensional packing for additive manufacturing”, Computers & Operations Research, 130, 105245, (2021).
49. [49] Baker K. R. and Bertrand J. W. M., “An investigation of due-date assignment rules with constrained tightness”, Journal of Operations Management, 1(3), 109-120, (1981).