Document Type : Research Paper

Authors

1 Department of Mathematics, University of Dhaka, Dhaka-1000, Dhaka, Bangladesh.

2 Department of Industrial and Production Engineering, Military Institute of Science and Technology, Dhaka-1216, Dhaka, Bangladesh.

Abstract

Sequencing and scheduling are the forms of decision-making approach that play a vital role in the automation and services industries. Efficient scheduling can help the industries to achieve the full potential of their supply chains. Conversely, inefficient scheduling causes additional idle time for machines and reduces productivity, which may escalate the product price. This study aims to find the most effective algorithm for solving sequencing and scheduling problems in a non-preemptive flow shop environment where the objective functions are to reduce the total elapsed time and idle time. In this research, four prominent exact algorithms are considered and examined their efficiency by calculating the ‘total completion time’ and their goodness. In order to demonstrate the comparative analysis, numerical examples are illustrated. A Gantt chart is additionally conducted to exhibit the efficiency of these algorithms graphically. Eventually, a feasible outcome for each condition has been obtained by analyzing these four algorithms, which leads to getting a competent, time and cost-efficient algorithm.

Keywords

Main Subjects

  • Defersha, F. M., & Rooyani, D. (2020). An efficient two-stage genetic algorithm for a flexible job-shop scheduling problem with sequence dependent attached/detached setup, machine release date and lag-time. Computers & industrial engineering, 147, 106605. https://doi.org/10.1016/j.cie.2020.106605
  • Metaxiotis, K. S., Psarras, J. E., & Ergazakis, K. A. (2003). Production scheduling in ERP systems: an AI‐based approach to face the gap. Business process management journal, 9(2), 221-247. https://doi.org/10.1108/14637150310468416
  • Samadpour, E., Ghousi, R., Makui, A., & Heydari, M. (2022). Routing and scheduling for a home health care problem considering health workers' skills. Journal of applied research on industrial engineering, 9(3), 249-263. https://doi.org/10.22105/jarie.2022.314240.1397
  • Ruhbakhsh, R., & Adibi, M. A. (In Press). Presenting a model for solving lot-streaming hybrid flow shop scheduling problem by considering independent setup time and transportation time. Journal of decisions and operations research. DOI: 22105/dmor.2022.296154.1450
  • Sarfaraj, N., Lingkon, M. L., & Zahan, N. (2021). Applying flexible job shop scheduling in patients management to optimize processing time in hospitals. International journal of research in industrial engineering, 10(1), 46-55. https://doi.org/10.22105/riej.2021.260145.1158
  • Jayasankari, S. (2021). An efficient flow shop scheduling problem with makespan objective. Turkish journal of computer and mathematics education (TURCOMAT), 12(4), 461-466. https://doi.org/10.17762/turcomat.v12i4.527
  • Michael, L. P. (2018). Scheduling: theory, algorithms, and systems. Springer.
  • Fakheri, S. (2022). A comprehensive review of big data applications. Big data and computing visions, 2(1), 9-17. https://doi.org/10.22105/bdcv.2022.325256.1041
  • Johnson, S. M. (1954). Optimal two‐and three‐stage production schedules with setup times included. Naval research logistics quarterly, 1(1), 61-68. https://doi.org/10.1002/nav.3800010110
  • Gill, S., & Kumar, R. (2012). Literature review for scheduling problems. International journal of latest research in science and technology, 1(1), 98-100. https://www.mnkjournals.com/journal/ijlrst/pdf/Volume_1_1_2012/10018.pdf
  • Palmer, D. S. (1965). Sequencing jobs through a multi-stage process in the minimum total time—a quick method of obtaining a near optimum. Journal of the operational research society, 16(1), 101-107. https://doi.org/10.1057/jors.1965.8
  • Ignall, E., & Schrage, L. (1965). Application of the branch and bound technique to some flow-shop scheduling problems. Operations research, 13(3), 400-412. https://doi.org/10.1287/opre.13.3.400
  • Campbell, H. G., Dudek, R. A., & Smith, M. L. (1970). A heuristic algorithm for the n job, m machine sequencing problem. Management science, 16(10), B-630. https://doi.org/10.1287/mnsc.16.10.B630
  • Gupta, J. N. (1976). A heuristic algorithm for the flowshop scheduling problem. Revue française d'automatique, informatique, recherche opérationnelle. Recherche opérationnelle, 10(V2), 63-73. http://www.numdam.org/item/RO_1976__10_2_63_0.pdf
  • Dannenbring, D. G. (1977). An evaluation of flow shop sequencing heuristics. Management science, 23(11), 1174-1182. https://doi.org/10.1287/mnsc.23.11.1174
  • Muhammad, N., Emory, E. J., & Inyong, H. (1983). A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. The international journal of management science, 11(1), 91-95. https://doi.org/10.1016/0305-0483(83)90088-9
  • Kusiak, A. (1986). Efficient implementation of Johnson's scheduling algorithm. IIE transactions, 18(2), 215-216. https://doi.org/10.1080/07408178608975349
  • Rajendran, C., & Chaudhuri, D. (1992). An efficient heuristic approach to the scheduling of jobs in a flowshop. European journal of operational research, 61(3), 318-325. https://doi.org/10.1016/0377-2217(92)90361-C
  • Modrak, V., Semanco, P., & Kulpa, W. (2013). Performance measurement of selected heuristic algorithms for solving scheduling problems. 2013 IEEE 11th international symposium on applied machine intelligence and informatics (SAMI) (pp. 205-209). IEEE. https://doi.org/10.1109/SAMI.2013.6480977
  • Rao, N. N., Raju, O. N., & Babu, I. R. (2013). Modified heuristic time deviation technique for job sequencing and computation of minimum total elapsed time. International journal of computer science & information technology, 5(3), 67. http://dx.doi.org/10.5121/ijcsit.2013.5305
  • Gupta, S., Ali, I., & Ahmed, A. (2016). A new algorithm for solving job shop sequencing problem. International journal for computer science engineering, 5(2), 93-100. http://www.ijcse.net/docs/IJCSE16-05-02-019.pdf
  • Geetha, M. (2019). A different technique for solving sequencing problem. International journal of analytical and experimental modal analysis, 11(11), 2584–2587. http://www.ijaema.com/gallery/290-november-2941.pdf
  • Kouider, A., & Haddadène, H. A. (2021). A bi-objective branch-and-bound algorithm for the unit-time job shop scheduling: a mixed graph coloring approach. Computers & operations research, 132, 105319. https://doi.org/10.1016/j.cor.2021.105319
  • Takano, M. I., & Nagano, M. S. (2017). A branch-and-bound method to minimize the makespan in a permutation flow shop with blocking and setup times. Cogent engineering, 4(1), 1389638. https://doi.org/10.1080/23311916.2017.1389638
  • Kim, Y. D. (1995). Minimizing total tardiness in permutation flowshops. European journal of operational research, 85(3), 541-555. https://doi.org/10.1016/0377-2217(94)00029-C
  • Ronconi, D. P. (2005). A branch-and-bound algorithm to minimize the makespan in a flowshop with blocking. Annals of operations research, 138(1), 53-65. https://doi.org/10.1007/s10479-005-2444-3