Job shop scheduling using heuristics through Python programming and excel interface
Job shop scheduling problem (JSSP) has remained a challenge both for the practitioners and the researchers. A JSSP consists of multiple number of machines (m) and jobs (n). As the number of jobs increases, the complexity of the problem increases exponentially and it becomes difficult to schedule manually. Practitioners use their experience to schedule jobs in ad hoc sessions resulting in inefficient allocation of jobs and machines. In this paper, a job shop scheduling problem under static and dynamic conditions is solved using heuristic approaches using python programming with an MS Excel user interface. For a supplier of automotive parts with a set of jobs and machines, priority dispatching rules, viz., Shortest Processing Time (SPT), Earliest Due Date (EDD), First-In First-Out (FIFO), Critical Ratio (CR) and Slack Per Remaining Operation (S/RO) are evaluated. The obtained performance metrics such as makespan, and tardiness are compared between the heuristics to select an optimal schedule by the job shop. The user inputs the jobs, machines, start and due dates through the MS Excel interface and obtains faster, practically usable results. This reduces the time taken for job scheduling and helps in making faster productivity-based decisions to maximize resource utilization and the total time to produce the product.
Abbas, M., Abbas, A., & Khan, W. A. (2016). Scheduling job shop-A case study. In IOP Conference Series: Materials Science and Engineering. 146(1), 012052. DOI: https://doi.org/10.1088/1757-899X/146/1/012052
Admi Syarif, A. S., Pamungkas, A., Mahendra, R. K., & Gen, M. (2021). Performance Evaluation of Various Heuristic Algorithms to Solve Job Shop Scheduling Problem. International Journal of Intelligent Engineering & System, 14(2), 334-343.
Ahmadian, M. M., Salehipour, A., & Cheng, T. C. E. (2021). A meta-heuristic to solve the just-in-time job-shop scheduling problem. European Journal of Operational Research, 288(1), 14-29.
Amaro, D., Rosenkranz, M., Fitzpatrick, N., Hirano, K., & Fiorentini, M. (2022). A case study of variational quantum algorithms for a job shop scheduling problem. EPJ Quantum Technology, 9(1), 1-20.
Asadzadeh, L. (2015). A local search genetic algorithm for the job shop scheduling problem with intelligent agents. Computers & Industrial Engineering, 85(1), 376-383. DOI: https://doi.org/10.1016/j.cie.2015.04.006
Ashwin, S., Shankaranarayanan, V., Anbuudayasankar, S. P., & Thenarasu, M. (2022). Development and Analysis of Efficient Dispatching Rules for Minimizing Flow Time and Tardiness-Based Performance Measures in a Job Shop Scheduling. In Intelligent Manufacturing and Energy Sustainability, 34(1), 337-345.
Bakuli, D. L. (2006). A survey of multi-objective scheduling techniques applied to the job shop problem (JSP). In Applications of Management Science: In Productivity, Finance, and Operations, 12, 129-143.
Bulbul, K., & Kaminsky, P. (2013). A linear programming-based method for job shop scheduling. International Journal of Scheduling, 16(2), 161-183. DOI: https://doi.org/10.1007/s10951-012-0270-4
Chaube, S., Singh, S. B., Pant, S., & Kumar, A. (2018). Time-dependent conflicting bifuzzy set and its applications in reliability evaluation. Advanced Mathematical Techniques in Engineering Sciences, 111-128. DOI: https://doi.org/10.1201/b22440-6
Cowling, P., & Johansson, M. (2002). Using real time information for effective dynamic scheduling. European journal of operational research, 139(2), 230-244. DOI: https://doi.org/10.1016/S0377-2217(01)00355-1
Delgoshaei, A., Aram, A. K., Ehsani, S., Rezanoori, A., Hanjani, S. E., Pakdel, G. H., & Shirmohamdi, F. (2021). A supervised method for scheduling multi-objective job shop systems in the presence of market uncertainties. RAIRO-Operations Research, 55, S1165-S1193.
Fox., M.S, and Smith., S.F. (1984). “ISIS—a knowledge-based system for factory scheduling,” International Journal of Expert Systems, 1(1), 25–49. DOI: https://doi.org/10.1111/j.1468-0394.1984.tb00424.x
Garey, M. R., & Johnson, D. S. (1979). Computers and intractability, San Francisco: freeman.
Ghedira, K., & Ennigrou, M. (2000). How to schedule a job shop problem through agent cooperation. In International Conference on Artificial Intelligence: Methodology, Systems, and Applications, Springer, Berlin, Heidelberg, 132-141. DOI: https://doi.org/10.1007/3-540-45331-8_13
Gupta A.K., and Sivakumar, A.I. (2006), Job shop scheduling techniques in semiconductor manufacturing, International Journal of Advanced Manufacturing Technology, 27(11), 1163–1169. DOI: https://doi.org/10.1007/s00170-004-2296-z
Jiang, T., & Zhang, C. (2018). Application of grey wolf optimization for solving combinatorial problems: job shop and flexible job shop scheduling cases. IEEE Access, 6, 26231-26240. DOI: https://doi.org/10.1109/ACCESS.2018.2833552
Kahraman, C. (2006). Metaheuristic techniques for job shop scheduling problem and a fuzzy ant colony optimization algorithm. In Fuzzy Applications in Industrial Engineering, 201, 401-425.
Kalita, R., Barua, P. B., & Dutta, A. K. (2016). Development of a heuristic algorithm for finding optimum machine loading sequence in fabrication shop with job shop layout. International Conference on Electrical, Electronics, and Optimization Techniques, IEEE, 1324-1329. DOI: https://doi.org/10.1109/ICEEOT.2016.7754898
Kapanoglu., M and Alikalfa., M. (2011) Learning IF-THEN priority rules for dynamic job shops using genetic algorithms. Robot. Computer Integrated Manufacturing, 27(1), 47–55. DOI: https://doi.org/10.1016/j.rcim.2010.06.001
Kim, S. C., & Bobrowski, P. M. (1994). Impact of sequence-dependent setup time on job shop scheduling performance. International Journal of Production Research, 32(7), 1503-1520. DOI: https://doi.org/10.1080/00207549408957019
Kumar, A., Negi, G., Pant, S., Ram, M. (2021a). Availability-Cost Optimization of Butter Oil Processing System by Using Nature Inspired Optimization Algorithms. Reliability: Theory & Applications, 2(64), 188-200.
Kumar, A., Vohra, M., Pant, S., & Singh, S. K. (2021b). Optimization techniques for petroleum engineering: A brief review. International Journal of Modelling and Simulation, 41(5), 326-334.
Kumar, A., Pant, S., Ram, M. & Yadav, O. (2022). Meta-heuristic Optimization Techniques: Applications in Engineering, Berlin, Boston: De Gruyter, 1-10.
Lenstra, J.K., Rinnooy Kan, R.H.G., and Brucker, P. (1977). Complexity of machine scheduling problems, Annals of Discrete Mathematics, 1, 343-362. DOI: https://doi.org/10.1016/S0167-5060(08)70743-X
Liaqait, R. A., Hamid, S., Warsi, S. S., & Khalid, A. (2021). A critical analysis of job shop scheduling in context of industry 4.0. International Journal of Sustainability, 13(14), 7684.
Meloni, C., Pacciarelli, D., & Pranzo, M. (2004). A rollout metaheuristic for job shop scheduling problems. Annals of Operations Research, 131(1), 215-235. DOI: https://doi.org/10.1023/B:ANOR.0000039520.24932.4b
Mohanavelu, T., Krishnaswamy, R., & Marimuthu, P. (2017). Simulation modelling and development of analytic hierarchy process-based priority dispatching rule for a dynamic press shop. International Journal of Industrial and Systems Engineering, 27(3), 340-364. DOI: https://doi.org/10.1504/IJISE.2017.10007557
Negi, G., Kumar, A., Pant, S., & Ram, M. (2021a). GWO: a review and applications. International Journal of System Assurance Engineering and Management, 12(1), 1-8.
Negi, G., Kumar, A., Pant, S., & Ram, M. (2021b). Optimization of complex system reliability using hybrid grey wolf optimizer. Decision Making: Applications in Management and Engineering, 4(2), 241-256. DOI: https://doi.org/10.31181/dmame210402241n
Pant, S., Kumar, A., Bhan, S., & Ram, M. (2017). A modified particle swarm optimization algorithm for nonlinear optimization. Nonlinear Studies, 24(1),127-138.
Pongchairerks, P. (2019). A two-level metaheuristic algorithm for the job-shop scheduling problem. Complexity, 1-11.
Pranzo, M., & Pacciarelli, D. (2016). An iterated greedy metaheuristic for the blocking job shop scheduling problem. Journal of Heuristics, 22(4), 587-611. DOI: https://doi.org/10.1007/s10732-014-9279-5
Raghuram, P., & Harisankar,G. (2021) Modeling and Assessment of the Impact of Supply Disruption and Cost of Recovery using Systems Dynamics Approach. International Journal of Industrial and Systems Engineering, 38(4). 432-449.
Raghuram, P., & Saleeshya, P.G. (2021) Responsiveness Model of Textile Supply Chain – A Structural Equation Modeling based Investigation. International Journal of Services and Operations Management, 38(3), 419-440.
Romero-Silva, R., Santos, J., & Hurtado-Hernández, M. (2022). A conceptual framework of the applicability of production scheduling from a contingency theory approach: addressing the theory-practice gap. International Journal of Production Planning & Control, published online, 1-21.
Sels, Veronique; Gheysen, Nele; Vanhoucke, Mario (2012). A comparison of priority rules for the job shop scheduling problem under different flow time- and tardiness-related objective functions. International Journal of Production Research, 50(15), 4255–4270. DOI: https://doi.org/10.1080/00207543.2011.611539
Snyman S & Bekker J. (2019), A Real-Time Scheduling System in a Sensorised Job Shop, In Proceedings of the International Conference on Competitive Manufacturing (COMA’19), Stellenbosch, South Africa,1-6.
Suresh, V., & Chaudhuri, D. (1993). Dynamic scheduling - A survey of research. International Journal of Production Economics, 32(1), 53-63. DOI: https://doi.org/10.1016/0925-5273(93)90007-8
Tasgetiren, M. F., Liang, Y. C., Sevkli, M., & Gencyilmaz, G. (2007). A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem. European journal of operational research, 177(3), 1930-1947. DOI: https://doi.org/10.1016/j.ejor.2005.12.024
Thenarasu, M., Rameshkumar, K., & Anbuudayasankar, S. P. (2019). Multi-criteria decision-making approach for minimizing makespan in a large-scale press-shop. International Journal of Industrial Engineering, 26(6), 962-985.
Thenarasu, M., Rameshkumar, K., Anbuudayasankar, S. P., Arjunbarath, G., & Ashok, P. (2020). Development and selection of hybrid dispatching rule for dynamic job shop scheduling using multi-criteria decision making analysis (MCDMA). International Journal for Quality Research, 14(2), 487–504.
Thenarasu, M., Rameshkumar, K., Rousseau, J., & Anbuudayasankar, S. P. (2022). Development and analysis of priority decision rules using MCDM approach for a flexible job shop scheduling: A simulation study. Simulation Modelling Practice and Theory, 114, 102416.
Uniyal, N., Pant, S., & Kumar, A. (2020). An overview of few nature inspired optimization techniques and its reliability applications. International Journal of Mathematical, Engineering and Management Sciences, 5(4), 732-743.
Uniyal, N., Pant, S., Kumar, A., & Pant, P. (2022). Nature-inspired metaheuristic algorithms for optimization. In Kumar, A., Pant, S., Ram, M. & Yadav, O. (Eds). Meta-heuristic Optimization Techniques: Applications in Engineering, Berlin, Boston: De Gruyter, 1-10.
Vinod, V., & Sridharan, R. (2011). Simulation modeling and analysis of due-date assignment methods and scheduling decision rules in a dynamic job shop production system. International Journal of Production Economics, 129(1), 127-146. DOI: https://doi.org/10.1016/j.ijpe.2010.08.017
Wang, Z., Qi., Y., Cui., H, Zhang., J. (2019). A hybrid algorithm for order acceptance and scheduling problem in make-to-stock/make-to-order industries, Computers & Industrial Engineering, 127(46), 841–852.
Xiong, H., Shi, S., Ren, D., & Hu, J. (2022). A survey of job shop scheduling problem: The types and models. Computers & Operations Research, 142, 105731.