Job shop scheduling using heuristics through Python programming and excel interface

Padmanabhan Sowmia  Narayanan; Nitish Shankar  Kumar; Raghuram  Potluru; Thenarasu  Mohanavelu

doi:10.31181/dmame0316102022n

Padmanabhan Sowmia Narayanan Department of Mechanical Engineering, Amrita School of Engineering, India
Nitish Shankar Kumar Department of Mechanical Engineering, Amrita School of Engineering, India https://orcid.org/0000-0003-4600-531X
Raghuram Potluru Maryland Health Benefit Exchange, Baltimore, USA https://orcid.org/0000-0002-2737-2811
Thenarasu Mohanavelu Department of Mechanical Engineering, Amrita School of Engineering, India https://orcid.org/0000-0001-6759-6417

DOI: https://doi.org/10.31181/dmame0316102022n

Keywords: 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

Download data is not yet available.

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. 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.