Novel Heuristic Algorithm for Flexible Job Shop Scheduling based on the Longest Processing Time Rules to Minimize Makespan
DOI:
https://doi.org/10.22219/JTIUMM.Vol24.No1.17-30Keywords:
Scheduling, Heuristic Algorithms, Flexible machines, Job Shop, MakespanAbstract
This research examined the scheduling of jobs with multiple stages unto identical parallel machines to minimize the makespan. The work is motivated by a Flexible Manufacturing System case that produces various parts and has multiple machining centers. Early research towards this system proposed a stage-by-stage independent scheduling, resulting in a non-optimal solution. This study aimed to create a better solution for the system by developing a novel heuristic algorithm based on the classical longest processing time algorithm and simultaneously considering processing time for all stages when deciding the job sequencing and job-machine allocation. The algorithm is defined as Modified LPT for Multiple Identical Machine with Multi-process Capability (M-LPT MIMMPC). We performed a numerical experiment to assess the algorithm's performance by incorporating various cases. We concluded that the resulting makespans are always better than LPT's theoretical bound for parallel machine scheduling. In some cases, it successfully gave an optimal value. Although the experiment scope was still limited, the algorithm showed promising performance results.
Downloads
References
K. R. Baker and D. Trietsch, Principles of sequencing and scheduling. John Wiley & Sons, 2013.
A. Setiawan, R. Wangsaputra, Y. Y. Martawirya, and A. H. Halim, "A production scheduling model considering cutting tools for an FMS to minimize makespan," 2015: Asia Pacific Industrial Engineering and Management Society: Ho Chi Minh International Univ., 2015.
E. K. A. Pakpahan, S. Kristina, and A. Setiawan, "Proposed algorithm to improve job shop production scheduling using ant colony optimization method," IOP Conference Series: Materials Science and Engineering, vol. 277, no. 1, p. 012050, 2017. https://doi.org/10.1088/1757-899X/277/1/012050.
D. Laha and D. K. Behera, "A comprehensive review and evaluation of LPT, MULTIFIT, COMBINE and LISTFIT for scheduling identical parallel machines," International Journal of Information and Communication Technology, vol. 11, no. 2, pp. 151-165, 2017. https://doi.org/10.1504/IJICT.2017.086246.
C. Koulamas and G. J. Kyparisis, "A modified LPT algorithm for the two uniform parallel machine makespan minimization problem," European Journal of Operational Research, vol. 196, no. 1, pp. 61-68, 2009. https://doi.org/10.1016/j.ejor.2008.02.008.
H. habiba, A. Hassam, Z. Sari, C. M. Amine, and T. Souad, "Minimizing Makespan on Identical Parallel Machines," in 2019 International Conference on Applied Automation and Industrial Diagnostics (ICAAID), 2019, vol. 1, pp. 1-6. https://doi.org/10.1109/ICAAID.2019.8934993.
D. De Giovanni, J. C. Ho, G. Paletta, and A. J. Ruiz-Torres, "Heuristics for Scheduling Uniform Machines," 2018, vol. 2, pp. 937-939: IMECS. https://www.iaeng.org/publication/IMECS2018/IMECS2018_pp937-939.pdf.
F. Della Croce and R. Scatamacchia, "The Longest Processing Time rule for identical parallel machines revisited," Journal of Scheduling, vol. 23, no. 2, pp. 163-176, 2020. https://doi.org/10.1007/s10951-018-0597-6.
L. Ghalami and D. Grosu, "Scheduling parallel identical machines to minimize makespan:A parallel approximation algorithm," Journal of Parallel and Distributed Computing, vol. 133, pp. 221-231, 2019. https://doi.org/10.1016/j.jpdc.2018.05.008.
I. Alharkan, M. Saleh, M. A. Ghaleb, H. Kaid, A. Farhan, and A. Almarfadi, "Tabu search and particle swarm optimization algorithms for two identical parallel machines scheduling problem with a single server," Journal of King Saud University - Engineering Sciences, vol. 32, no. 5, pp. 330-338, 2020. https://doi.org/10.1016/j.jksues.2019.03.006.
S. Kamaraj and M. Saravanan, "Optimisation of identical parallel machine scheduling problem," International Journal of Rapid Manufacturing, vol. 8, no. 1-2, pp. 123-132, 2018. https://doi.org/10.1504/IJRAPIDM.2019.097033.
F. Yu, P. Wen, and S. Yi, "A multi-agent scheduling problem for two identical parallel machines to minimize total tardiness time and makespan," Advances in Mechanical Engineering, vol. 10, no. 2, p. 1687814018756103, 2018. https://doi.org/10.1177/1687814018756103.
M. Khatami, A. Salehipour, and F. J. Hwang, "Makespan minimization for the m-machine ordered flow shop scheduling problem," Computers & Operations Research, vol. 111, pp. 400-414, 2019. https://doi.org/10.1016/j.cor.2019.06.012.
I. Amallynda, "The Discrete Particle Swarm Optimization Algorithms for Permutation Flowshop Scheduling Problem," Jurnal Teknik Industri, vol. 20, no. 2, pp. 105-116, 2019. https://doi.org/10.22219/JTIUMM.Vol20.No2.105-116.
I. Amallynda and B. Hutama, "The Moth-Flame Optimization Algorithm for Flow Shop Scheduling Problem with Travel Time," Jurnal Teknik Industri, vol. 22, no. 2, pp. 224-235, 2021. https://doi.org/10.22219/JTIUMM.Vol22.No2.224-235.
D. Marsetiya Utama, "An Effective Hybrid Sine Cosine Algorithm to Minimize Carbon Emission on Flow-shop Scheduling Sequence Dependent Setup," Jurnal Teknik Industri, vol. 20, no. 1, pp. 62-72, 2019. https://doi.org/10.22219/JTIUMM.Vol20.No1.62-72.
A. N. A. A. K. Jabari and A. Hasan, "Energy-Aware Scheduling in Hybrid Flow Shop using Firefly Algorithm," Jurnal Teknik Industri, vol. 22, no. 1, pp. 18-30, 2021. https://doi.org/10.22219/JTIUMM.Vol22.No1.18-30.
N. Dridi and A. O. Bedhief, "Minimizing makespan in a three-stage hybrid flow shop with dedicated machines," International Journal of Industrial Engineering Computations, vol. 10, no. 2, pp. 161-176, 2019. http://dx.doi.org/10.5267/j.ijiec.2018.10.001.
J. Zhu, H. Wang, and T. Zhang, "A Deep Reinforcement Learning Approach to the Flexible Flowshop Scheduling Problem with Makespan Minimization," in 2020 IEEE 9th Data Driven Control and Learning Systems Conference (DDCLS), 2020, pp. 1220-1225. https://doi.org/10.1109/DDCLS49620.2020.9275080.
C. Cebi, E. Atac, and O. K. Sahingoz, "Job Shop Scheduling Problem and Solution Algorithms: A Review," in 2020 11th International Conference on Computing, Communication and Networking Technologies (ICCCNT), 2020, pp. 1-7. https://doi.org/10.1109/ICCCNT49239.2020.9225581.
J. Xie, L. Gao, K. Peng, X. Li, and H. Li, "Review on flexible job shop scheduling," IET Collaborative Intelligent Manufacturing, vol. 1, no. 3, pp. 67-77, 2019. https://doi.org/10.1049/iet-cim.2018.0009.
L. Meng, C. Zhang, Y. Ren, B. Zhang, and C. Lv, "Mixed-integer linear programming and constraint programming formulations for solving distributed flexible job shop scheduling problem," Computers & Industrial Engineering, vol. 142, p. 106347, 2020. https://doi.org/10.1016/j.cie.2020.106347.
C. Soto, B. Dorronsoro, H. Fraire, L. Cruz-Reyes, C. Gomez-Santillan, and N. Rangel, "Solving the multi-objective flexible job shop scheduling problem with a novel parallel branch and bound algorithm," Swarm and Evolutionary Computation, vol. 53, p. 100632, 2020. https://doi.org/10.1016/j.swevo.2019.100632.
B. Denkena, F. Schinkel, J. Pirnay, and S. Wilmsmeier, "Quantum algorithms for process parallel flexible job shop scheduling," CIRP Journal of Manufacturing Science and Technology, vol. 33, pp. 100-114, 2021. https://doi.org/10.1016/j.cirpj.2021.03.006.
M. Shahgholi Zadeh, Y. Katebi, and A. Doniavi, "A heuristic model for dynamic flexible job shop scheduling problem considering variable processing times," International Journal of Production Research, vol. 57, no. 10, pp. 3020-3035, 2019. https://doi.org/10.1080/00207543.2018.1524165.
A. Baykasoğlu, F. S. Madenoğlu, and A. Hamzadayı, "Greedy randomized adaptive search for dynamic flexible job-shop scheduling," Journal of Manufacturing Systems, vol. 56, pp. 425-451, 2020. https://doi.org/10.1016/j.jmsy.2020.06.005.
R. H. Caldeira and A. Gnanavelbabu, "Solving the flexible job shop scheduling problem using an improved Jaya algorithm," Computers & Industrial Engineering, vol. 137, p. 106064, 2019. https://doi.org/10.1016/j.cie.2019.106064.
R. Zarrouk, I. E. Bennour, and A. Jemai, "A two-level particle swarm optimization algorithm for the flexible job shop scheduling problem," Swarm Intelligence, vol. 13, no. 2, pp. 145-168, 2019. https://doi.org/10.1007/s11721-019-00167-w.
K. Gao, Z. Cao, L. Zhang, Z. Chen, Y. Han, and Q. Pan, "A review on swarm intelligence and evolutionary algorithms for solving flexible job shop scheduling problems," IEEE/CAA Journal of Automatica Sinica, vol. 6, no. 4, pp. 904-916, 2019. https://doi.org/10.1109/JAS.2019.1911540.
T. Jiang and C. Zhang, "Application of Grey Wolf Optimization for Solving Combinatorial Problems: Job Shop and Flexible Job Shop Scheduling Cases," IEEE Access, vol. 6, pp. 26231-26240, 2018. https://doi.org/10.1109/ACCESS.2018.2833552.
G. Zhang, L. Zhang, X. Song, Y. Wang, and C. Zhou, "A variable neighborhood search based genetic algorithm for flexible job shop scheduling problem," Cluster Computing, vol. 22, no. 5, pp. 11561-11572, 2019. https://doi.org/10.1007/s10586-017-1420-4.
R. H. Caldeira and A. Gnanavelbabu, "A simheuristic approach for the flexible job shop scheduling problem with stochastic processing times," SIMULATION, vol. 97, no. 3, pp. 215-236, 2020. https://doi.org/10.1177/0037549720968891.
R. Chen, B. Yang, S. Li, and S. Wang, "A self-learning genetic algorithm based on reinforcement learning for flexible job-shop scheduling problem," Computers & Industrial Engineering, vol. 149, p. 106778, 2020. https://doi.org/10.1016/j.cie.2020.106778.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2022 Eka Pakpahan, Kenneth David Sumarna
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
