Job shop scheduling using heuristics through Python programming and excel interface
DOI:
https://doi.org/10.31181/dmame0316102022nKeywords:
Job Shop Scheduling Problem (JSSP), Priority Dispatching Rules (PDR), Python Programming, Micro Small and Medium Enterprises (MSME)Abstract
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.
Downloads
References
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.
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.
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.
Bülbül, K., & Kaminsky, P. (2013). A linear programming-based method for job shop scheduling. International Journal of Scheduling, 16(2), 161-183.
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.
Cowling, P., & Johansson, M. (2002). Using real time information for effective dynamic scheduling. European journal of operational research, 139(2), 230-244.
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., & Smith, S. F. (1984). ISIS—a knowledge‐based system for factory scheduling. Expert systems, 1(1), 25-49.
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.
Gupta, A. K., & Sivakumar, A. I. (2006). Job shop scheduling techniques in semiconductor manufacturing. The International Journal of Advanced Manufacturing Technology, 27, 1163-1169.
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.
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.
Kapanoglu, M., & Alikalfa, M. (2011). Learning IF–THEN priority rules for dynamic job shops using genetic algorithms. Robotics and Computer-Integrated Manufacturing, 27(1), 47-55.
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.
Kumar, A., Negi, G., Pant, S., Ram, M., & Dimri, S. C. (2021a). Availability-cost optimization of butter oil processing system by using nature inspired optimization algorithms. Reliability: Theory & Applications, 16(SI 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.
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.
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.
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.
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.
Raghuram, P., & Harisankar, G. (2021). Modelling and assessment of the impact of supply disruption and cost of recovery using system dynamics approach. International Journal of Industrial and Systems Engineering, 38(4), 432-449.
Raghuram, P., & Saleeshya, P. G. (2021). Responsiveness model of the textile supply chain-a structural equation modelling-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, V., Gheysen, N., & Vanhoucke, M. (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.
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 (pp. 1-6).
Suresh, V., & Chaudhuri, D. (1993). Dynamic scheduling - A survey of research. International Journal of Production Economics, 32(1), 53-63.
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.
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.
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.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2022 Decision Making: Applications in Management and Engineering
This work is licensed under a Creative Commons Attribution 4.0 International License.
