Scheduling Splitable Jobs on Identical Parallel Machines to Minimize Makespan using Mixed Integer Linear Programming

  • Ayudita Oktafiani Universitas Telkom
  • Muhammad Nashir Ardiansyah
Keywords: Identical Parallel Machine, Makespan, Job-splitting Property, Injection Molding, Workload Balancing

Abstract

The scheduling of parallel machines with and without a job-splitting property, deterministic demand, and sequence-independent setup time with the goal of minimizing makespan is examined in this work. For simultaneous processing by multiple machines, single-stage splitable jobs are broken into random (job) sections. When a job starts to be processed on a machine, an operator has to setup the machine for an hour. By creating two Mixed Integer Linear Programming models, this work proposes a mathematical programming strategy (MILP). A MILP model takes the job-splitting property into account. Another model, however, does not include the job-splitting property. This study investigates the performance of the proposed models using Gurobi solver. These programs' numerical calculations are based on actual problems in the Indonesian city of Bandung's plastics industry. On four identical parallel injection molding machines, 318 jobs must be finished in 22 periods. The real scheduling method is contrasted with these two MILP models. The maximum workload imbalance, the maximum relative percentage of imbalance, and the makespan of these three scheduling systems are used to evaluate their effectiveness. Without the job-splitting property, MILP can handle the real issue of scheduling identical parallel machines on injection molding machines to reduce makespan, resulting in a 36% average decrease. The MILP model's job-splitting property can reduce makespan by an additional 2.40%. The order of relative ranking is MILP with job-splitting property, MILP without job-splitting property, and actual scheduling based on the makespan minimization, workload imbalance, and relative percentage of imbalance.

References

[1] T. C. E. Cheng and C. C. S. Sin, “A state-of-the-art review of parallel-machine scheduling research,” Eur. J. Oper. Res., vol. 47, no. 3, pp. 271–292, 1990, doi: 10.1016/0377-2217(90)90215-W.
[2] D. Biskup, J. Herrmann, and J. N. D. Gupta, “Scheduling identical parallel machines to minimize total tardiness,” Int. J. Prod. Econ., vol. 115, no. 1, pp. 134–142, 2008, doi: 10.1016/j.ijpe.2008.04.011.
[3] A. Kramer, M. Iori, and P. Lacomme, “Mathematical formulations for scheduling jobs on identical parallel machines with family setup times and total weighted completion time minimization,” Eur. J. Oper. Res., vol. 289, no. 3, pp. 825–840, 2021, doi: 10.1016/j.ejor.2019.07.006.
[4] A. Najat, C. Yuan, S. Gursel, and Y. Tao, “Minimizing the number of tardy jobs on identical parallel machines subject to periodic maintenance,” Procedia Manuf., vol. 38, no. 2019, pp. 1409–1416, 2019, doi: 10.1016/j.promfg.2020.01.147.
[5] N. Maisazahra, M. D. Astuti, and M. D. Prasetio, “Identical Parallel Machine Scheduling to Minimize Makespan Using Suggested Algorithm Method at XYZ Company,” Int. J. Innov. Enterp. Syst., vol. 6, no. 01, pp. 1–10, 2022, doi: 10.25124/ijies.v6i01.146.
[6] J. H. Lee and H. J. Kim, A heuristic algorithm for identical parallel machine scheduling: splitting jobs, sequence-dependent setup times, and limited setup operators, vol. 33, no. 4. Springer US, 2021.
[7] D. Nait Tahar, F. Yalaoui, C. Chu, and L. Amodeo, “A linear programming approach for identical parallel machine scheduling with job splitting and sequence-dependent setup times,” Int. J. Prod. Econ., vol. 99, no. 1–2, pp. 63–73, 2006, doi: 10.1016/j.ijpe.2004.12.007.
[8] D. Laha and J. N. D. Gupta, “An improved cuckoo search algorithm for scheduling jobs on identical parallel machines,” Comput. Ind. Eng., vol. 126, pp. 348–360, 2018, doi: 10.1016/j.cie.2018.09.016.
[9] J. H. Lee, H. Jang, and H. J. Kim, “Iterative job splitting algorithms for parallel machine scheduling with job splitting and setup resource constraints,” J. Oper. Res. Soc., vol. 72, no. 4, pp. 780–799, 2021, doi: 10.1080/01605682.2019.1700191.
[10] O. Ozturk, M. L. Espinouse, M. Di Mascolo, and A. Gouin, “Makespan minimisation on parallel batch processing machines with non-identical job sizes and release dates,” Int. J. Prod. Res., vol. 50, no. 20, pp. 6022–6035, 2012, doi: 10.1080/00207543.2011.641358.
[11] V. H. Nguyen, N. H. Tuong, V. H. Tran, and N. Thoai, “An MILP-based makespan minimization model for single-machine scheduling problem with splitable jobs and availability constraints,” 2013 Int. Conf. Comput. Manag. Telecommun. ComManTel 2013, pp. 397–400, 2013, doi: 10.1109/ComManTel.2013.6482427.
[12] F. Schalekamp, R. Sitters, S. van der Ster, L. Stougie, V. Verdugo, and A. van Zuylen, “Split scheduling with uniform setup times,” J. Sched., vol. 18, no. 2, pp. 119–129, 2015, doi: 10.1007/s10951-014-0370-4.
[13] P. Godhandaraman, V. Poongothai, and A. Yuvashree, “Parallel machine with learning, tool changes and job splitting to reduce the makespan,” AIP Conf. Proc., vol. 2277, no. November, 2020, doi: 10.1063/5.0025324.
[14] Y. D. Kim, S. O. Shim, S. B. Kim, Y. C. Choi, and H. M. Yoon, “Parallel machine scheduling considering a job-splitting property,” Int. J. Prod. Res., vol. 42, no. 21, pp. 4531–4546, 2004, doi: 10.1080/00207540410001720745.
[15] R. L. Graham, E. L. Lawler, J. K. Lenstra, and A. H. G. R. Kan, “Optimization and heuristic in deterministic sequencing and scheduling: a survey,” Ann. Discret. Math., vol. 5, pp. 287–326, 1979, [Online]. Available: https://ac.els-cdn.com/S016750600870356X/1-s2.0-S016750600870356X-main.pdf?_tid=cbf345a3-808d-42df-9560-bf8a52069d0e&acdnat=1550949881_e9837bfdf6316caefaf71ae2f3779b10.
[16] I. Kantor, J. L. Robineau, H. Bütün, and F. Maréchal, “A Mixed-Integer Linear Programming Formulation for Optimizing Multi-Scale Material and Energy Integration,” Front. Energy Res., vol. 8, no. April, 2020, doi: 10.3389/fenrg.2020.00049.
[17] M. Boccia, G. Bruno, and C. Sterle, “A MILP formulation for a batch scheduling problem on parallel machines in the aircraft industry,” 2013 5th Int. Conf. Model. Simul. Appl. Optim. ICMSAO 2013, 2013, doi: 10.1109/ICMSAO.2013.6552650.
[18] S. Rajakumar, V. P. Arunachalam, and V. Selladurai, “Workflow balancing strategies in parallel machine scheduling,” Int. J. Adv. Manuf. Technol., vol. 23, no. 5–6, pp. 366–374, 2004, doi: 10.1007/s00170-003-1603-4.
[19] Y. Ouazene, F. Yalaoui, H. Chehade, and A. Yalaoui, “Workload balancing in identical parallel machine scheduling using a mathematical programming method,” Int. J. Comput. Intell. Syst., vol. 7, no. SUPPL.1, pp. 58–67, 2014, doi: 10.1080/18756891.2013.853932.
Published
2023-01-31
How to Cite
Oktafiani, A., & Ardiansyah, M. (2023, January 31). Scheduling Splitable Jobs on Identical Parallel Machines to Minimize Makespan using Mixed Integer Linear Programming. International Journal of Innovation in Enterprise System, 7(01), 41-54. https://doi.org/https://doi.org/10.25124/ijies.v7i01.190