Optimizing the Job Shop Scheduling Problem with a no Wait Constraint by Using the Jaya Algorithm Approach

• Autorzy: Aimade Eddine Bougloula
• Języki publikacji: EN

Abstrakty

EN

This work is interested to optimize the job shop scheduling problem with a no wait constraint. This constraint occurs when two consecutive operations in a job must be processed without any waiting time either on or between machines. The no wait job shop scheduling problem is a combinatorial optimization problem. Therefore, the study presented here is focused on solving this problem by proposing strategy for making Jaya algorithm applicable for handling optimization of this type of problems and to find processing sequence that minimizes the makespan (Cmax). Several benchmarks are used to analyze the performance of this algorithm compared to the best-known solutions.(original abstract)

Słowa kluczowe

EN

Optimalization; Labour efficiency; Measuring work time

PL

Optymalizacja; Wydajność pracy; Pomiar czasu pracy

• Czasopismo: Management and Production Engineering Review
• Rocznik: 2023
• Tom: 14
• Numer: nr 3
• Strony: 148--155

Twórcy

autor

Aimade Eddine Bougloula

• University Batna2, Department of Industrial Engineering, Algeria

Bibliografia

• AitZai, A., Benmedjdoub, B., & Boudhar, M. (2014). Branch-and-bound and PSO algorithms for no-wait job shop scheduling. Journal of Intelligent Manufacturing, 27, 679-688
• Allahverdi, A. (2016). A survey of scheduling problems with no wait in process. European Journal of Operational Research, 255, 665-686.
• Asadzadeh, L. (2016). A parallel artificial bee colony algorithm for the job shop-scheduling problem with a dynamic migration strategy. Computer & Industrial Engineering, 102, 359-367.
• Aydin, M.E., & Fogarty, T.C. (2004). A distributed evolutionary simulated annealing algorithm for combinatorial optimisation problems. Journal of Heuristics, 10, 269-292.
• Bansal, N., Mahdian, M., & Sviridenko, M. (2005). Minimizing makespan in no-wait job shops. Mathematics of Operations Research, 30(4), 817-831.
• Bozejko, W., & Makuchowski, M. (2011). Solving the no-wait job-shop problem by using genetic algorithm with automatic adjustment. International Journal of Advanced Manufacturing Technology, 57, 735-752.
• Bürgy, R., & Gröflin, H. (2012). Optimal job insertion in the no-wait job shop. Journal of Combinatorial Optimization, 26(2), 345-371.
• Chaithanya, M., Reddy, N.S.R., & Reddy, P.R. (2017). Sequencing and Scheduling of Jobs and Tools in a Flexible Manufacturing System using Jaya Algorithm. International Journal for Research in Applied Science & Engineering Technology (IJRASET), 5(11).
• Chaouch, O.B., Driss, K., & Ghedira, A. (2017). Modified ant colony optimization algorithm for the distributed job shop scheduling problem. Procedia Computer. Science, 112, 296-305.
• Chaudhry, I.A., & Khan, A.A. (2015). A research survey: review of flexible job shop scheduling techniques. International Transactions in Operational Research, 23(3), 551-591.
• Dao, T.K., Pan, T.S., Nguyen, T.-T., & Pan, J.S. (2018). Parallel bat algorithm for optimizing makespan in job shop scheduling problems. Journal of Intelligent Manufacturing, 29, 245-462.
• Deng, G., Zhang, Z., Jiang, T., & Zhang, S. (2019). Total flow time minimization in no-wait job shop using a hybrid discrete group search optimizer. Applied Soft Computing, 81.
• Deng, G., Wei, M., Su, Q., & Zhao, M. (2015). An effective co-evolutionary quantum genetic algorithm for the no-wait flow shop scheduling problem. Advances in Mechanical Engineering, 7(12), 1-10.
• Engin, O., & Güçlü, A., (2018). A new hybrid ant colony optimization algorithm for solving the no-wait flow shop scheduling problems. Applied Soft Computing, 72, 166-176.
• Framinan, J., & Schuster, C. (2006). An enhanced timetabling procedure for the no-wait job shop problem: a complete local search approach. Computer & Operations. Research, 33(5), 1200-1213.
• Gao, K., Sadollah, A., Zhang, Y., Su, R., & Li, K.G.J. (2016). Discrete Jaya algorithm for flexible job shop scheduling problem with new job insertion. 14th international conference on control, automation, robotics and vision (ICARCV), 1-5.
• Gong, G.L., Deng, Q.W., Chiong, R., Gong, X., Huang, H. (2019). An effective memetic algorithm for multiobjective job-shop scheduling. Knowl-Based System, 182.
• Grabowski, J., & Pempera, J. (2000). Sequencing of jobs in some production system. European Journal. Operation Research, 125, 535-550.
• Gröflin, H., & Klinkert, A. (2007). Feasible insertions in job shop scheduling, short cycles and stable sets. European Journal of Operational Research, 177(2), 763-785.
• Hadri, A., Bougloula, A.E., Belkaid, F., & Smadi, H. (2023). An efficient approach for solving a job shop scheduling problem with resources constraints: a case study iCIM 3000'. Int. J. Operational Research, 46(1), 73-92.
• He, L., Li, W., Chiong, R., Abedi, M., Cao, Y., & Zhang, Y. (2021). Optimising the job-shop schedulng problem using a multi-objective Jaya algorithm. Applied Soft Computing, 111.
• Kurdi, M. (2016). An effective new island model genetic algorithm for job shop scheduling problem. Computer Operation Research, 67, 132-142.
• Lawrence, S. (1984). Resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques, GSIA, Carnegie Mellon University, Pittsburgh, PA.
• Li, J.; Deng, J., Li, C., Han, Y., Tian, J., Zhang, B., & Wang, C. (2020). An improved Jaya algorithm for solving the flexible job shop scheduling problem with transportation and setup times. KnowledgeBased Systems, 200, 2020.
• Lin, T.L., Horng, S.J., & Kao, T.W. (2010). An efficient job-shop scheduling algorithm based on particle swarm optimization. Expert Systems with Applications, 37(3), 2629-2636.
• Mahapatra, D. (2012). Job Shop Scheduling Using Artificial Immune System. BSc, National Institute of Technology, Rourkela, India.
• Mokhtari, H. (2014). A two-stage no-wait job shop scheduling problem by using a neuro-evolutionary variable neighborhood search. The International Journal of Advanced Manufacturing Technology, 74, 1595-1610.
• Naderi, B., & Zandieh, M., (2014). Modeling and scheduling no-wait open shop problems. International Journal of Production Economics, 158, 256-266.
• Ozolinz, A. (2016). A new exact algorithm for no wait job shop problem to minimize makespan. Operational Research, 20(4) 2333-2363
• Pinedo, M. (2016). Scheduling: Theory, Algorithms, and Systems. 5th ed. Berlin Heidelberg.
• Pongchairerks, P., & Kachitvichyanukul, V. (2009). A particle swarm optimization algorithm on job-shop scheduling problems with multi-purpose machines. Asia Pacific Journal of Operational Research, 26(02), 161-184
• Pranzo, M., & Pacciarelli, D. (2016). An iterated greedy metaheuristic for the blocking job shop scheduling problem. Journal of Heuristics, 22, 587-611.
• Rao, R. (2016). Jaya: a simple and new optimization algorithm for solving constrained and unconstrained optimization problems. International Journal of Industrial Engineering Computations, 7(1), 19-34.
• Sachchida, N. C., Shyam, S., Donghwi, J., & Ho, M.L. (2018). An Evolutionary Algorithm Based Hyperheuristic for the Job-Shop Scheduling Problem with No-Wait Constraint: Theory and Applications. ICHSA, 249-257.
• Schuster, C.J. (2006). No-wait Job Shop Scheduling: Tabu Search and Complexity of Subproblems. Mathematical Methods of Operations Research, 63(3), 473-491
• Song, X.Y., Meng, Q.H., & Yang, C. (2008). Improved taboo search algorithm for job shop scheduling problems. Syst. Eng. Electron, 30, 93-96.
• Sundar, S., Suganthan, P.N., Jin, C.T., Xiang, C.T., & Soon, C.C. (2000). A hybrid artificial bee colony algorithm for the job-shop scheduling problem with nowait constraint. Soft Computer, 21(5), 1193-1202.
• Tang, L., Liu, J., Rong, A., & Yang, Z. (2000). A mathematical programming model for scheduling steelmaking-continuous casting production. European Journal of Operation Research, 120, 423-435.
• Vermeulen, H., Hoogeveen, H., & VandenAkker, J.M. (2011). Solving the no-wait job shop problem: An ILP and CP approach. The 8th International Conference on Integration of Artificial Intelligence (AI) and Operations Research (OR) techniques in Constraint Programming, 2011, Berlin, Germany.
• Weckma, G.R., Ganduri, C.V., & Koonce, D. (2008). A neural network job-shop scheduler. Journal of Intelligent Manufacturing, 19(2), 191-201.
• Zhu, J., & Li, X., (2011). An Effective Meta-Heuristic for No-Wait Job Shops to Minimize Makespan. IEEE Transactions on Automation Science and Engineering, 9(1), 189-198

Identyfikatory

DOI

10.24425/mper.2023.147196