A reactive approach for flexible job shop scheduling problem with tardiness penalty under uncertainty

Document Type : Article

Authors

1 Industrial Engineering Department, Faculty of Engineering, Islamic Azad University-North Tehran Branch,Tehran, Iran

2 Department of Industrial Engineering, Karaj Branch, Islamic Azad University, Karaj, Iran

3 School of Strategy and Leadership, Faculty of Business and Law, Coventry University, Coventry, UK

4 Industrial Engineering Department, Faculty of Engineering, Islamic Azad University-North Tehran Branch, Tehran, Iran

5 Industrial Engineering and Management Department, Shahrood University of Technology, Shahrood, Iran

Abstract

Flexible job shop scheduling under uncertainty plays an important role in real-world manufacturing systems. This paper deals with the flexible job shop scheduling problem to minimize the sum of jobs’ tardiness considering machines breakdown and order due date modification as two important disruptions in this production system. To this end, the problem is formulated as a mixed-integer linear programming model. In addition, two different strategies are proposed including allocating multiple machines to each job and selecting the best alternative process from other jobs to handle these disruptions. Since the problem is well-known strongly NP-hard, a hybrid metaheuristic algorithm based on the Genetic Algorithm (GA) and Particle Swarm Optimization (PSO) is proposed to solve the real-sized instances of these problems. Numerical experiments are used to evaluate the performance and effectiveness of the proposed hybrid algorithm. Obtained results for the small-sized instances show that the proposed algorithm provides proper solutions in terms of optimality and CPU Time. In addition, results for the medium- and large-sized scales validate the efficiency of the proposed algorithm and indicate that the proposed hybrid solution approach outperformed the classic GA in terms of the objective function value and the CPU time.

Keywords

References

References:
[1] Coffman, E. G. & Bruno, J. L. “Computer and job-shop scheduling theory”, John Wiley & Sons (1976).
[2] Gan, H.-S. & Wirth, A. “Comparing deterministic, robust and online scheduling using entropy”, International journal of production research, 43, 2113-2134 (2005).
[3] Gao, J., Gen, M. & Sun, L. “Scheduling jobs and maintenances in flexible job shop with a hybrid genetic algorithm”, Journal of Intelligent Manufacturing, 17, 493-507 (2006).
[4] Gao, J., Gen, M., Sun, L. & Zhao, X. “A hybrid of genetic algorithm and bottleneck shifting for multiobjective flexible job shop scheduling problems”, Computers & Industrial Engineering, 53, 149-162 (2007).
[5] Gao, J., Sun, L. & Gen, M. “A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems”, Computers & Operations Research, 35, 2892-2907 (2008).
[6] Gen, M., Gao, J. & Lin, L. “Multistage-based genetic algorithm for flexible job-shop scheduling problem”, Intelligent and evolutionary systems, 187, 183-196 (2009).
[7] Herroelen, W. & Leus, R. “Project scheduling under uncertainty: Survey and research potentials”, European journal of operational research, 165, 289-306 (2005).
[8] Ayyoubzadeh, B., Ebrahimnejad, S., Bashiri, M., Baradaran, V., & Hosseini, S.M.H., “Modeling and an improved NSGA-II algorithm for sustainable manufacturing systems with energy conservation under environmental uncertainties: a case study”, International Journal of Sustainable Engineering, 14(3), 255-279 (2021). https://doi.org/10.1080/19397038.2021.1923083
[9] Ayyoubzadeh, B., Ebrahimnejad, S., Bashiri, M., Baradaran, V., & Hosseini, S.M.H., “Energy-aware reactive flexible job shop scheduling with timely delivery under uncertainty: a case study”, Journal of Industrial Engineering and Management Studies, 8(2), 26-53 (2021). 10.22116/JIEMS.2022.138123
[10] Hasani, A., & Hosseini S.M.H., "Auxiliary resource planning in a flexible flow shop scheduling problem considering stage skipping.” Computers & Operations Research 138 (2022): 105625.
[11] Jackson, J. R. “Simulation research on job shop production”, Naval Research Logistics Quarterly, 4, 287-295 (1957).
 [12] Sabuncuoglu, I. & Bbyiz, M. “Analysis of reactive scheduling problems in a job shop environment”, European Journal of operational research, 126, 567-586 (2000).
[13] Chryssolouris, G. & Subramaniam, V. “Dynamic scheduling of manufacturing job shops using genetic algorithms”, Journal of Intelligent Manufacturing, 12, 281-293 (2001).
[14] Albers, S. & Schmidt, G. “Scheduling with unexpected machine breakdowns”. Discrete Applied Mathematics, 110, 85-99 (2001).
[15] Qi, X., Yu, G. & Bard, J. F. “Single machine scheduling with assignable due dates”, Discrete Applied Mathematics, 122, 211-233 (2002).
[16] Suwa, H. & Sandoh, H. “Capability of cumulative delay based reactive scheduling for job shops with machine breakdowns”, Computers & Industrial Engineering, 53, 63-78 (2007).
[17] Hao, X. & Lin, L. “Job shop rescheduling by using multi-objective genetic algorithm”,  The 40th International Conference on Computers and Industrial Engineering, Japan, 1-6 (2010).
[18] Adibi, M., Zandieh, M. & Amiri, M. “Multi-objective scheduling of dynamic job shop using variable neighborhood search”, Expert Systems with Applications, 37, 282-287 (2010).
[19] Kianfar, K., Ghomi, S. F. & Jadid, A. O. “Study of stochastic sequence-dependent flexible flow shop via developing a dispatching rule and a hybrid GA”, Engineering Applications of Artificial Intelligence, 25, 494-506 (2012).
[20] He, W. & Sun, D.-H. “Scheduling flexible job shop problem subject to machine breakdown with route changing and right-shift strategies”, The International Journal of Advanced Manufacturing Technology, 66, 501-514 (2013).
[21] Zhang, L., Gao, L. & Li, X. “A hybrid intelligent algorithm and rescheduling technique for job shop scheduling problems with disruptions”, The International Journal of Advanced Manufacturing Technology, 65, 1141-1156 (2013).
[22] De Freitas Rodrigues, R., Dourado, M. C. & Szwarcfiter, J. L. “Scheduling problem with multi-purpose parallel machines,. Discrete Applied Mathematics, 164, 313-319 (2014).
[23] He, C., Leung, J. Y.-T., Lee, K. & Pinedo, M. L. “Scheduling a single machine with parallel batching to minimize makespan and total rejection cost”, Discrete Applied Mathematics, 204, 150-163 (2015).
[24] Zinder, Y. & Walker, S. “Algorithms for scheduling with integer preemptions on parallel machines to minimize the maximum lateness”, Discrete Applied Mathematics, 196, 28-53 (2015).
[25] Rey, G. Z., Bekrar, A., Trentesaux, D. & Zhou, B.-H. “Solving the flexible job-shop just-in-time scheduling problem with quadratic earliness and tardiness costs”, The International Journal of Advanced Manufacturing Technology, 81, 1871–1891 (2015).
[26] Rohaninejad, M., Kheirkhah, A., Fattahi, P. & Vahedi-Nouri, B. “A hybrid multi-objective genetic algorithm based on the electre method for a capacitated flexible job shop scheduling problem”, The International Journal of Advanced Manufacturing Technology, 77, 51-66 (2015).
[27] Shen, J. & Zhu, Y. “Chance-constrained model for uncertain job shop scheduling problem”, Soft Computing, 20, 2383–2391 (2016).
[28] Xie N.,Chen N. “Flexible job shop scheduling problem with interval grey processing time”, Applied Soft Computing,70, 513-524 (2018).
[29] Xing, L.-N., Chen, Y.-W., Wang, P., Zhao, Q.-S. & Xiong, J. “A knowledge-based ant colony optimization for flexible job shop scheduling problems”, Applied Soft Computing, 10, 888-896 (2010).
[30] Tavakkoli-Moghaddam, R., Jolai, F., Vaziri, F., Ahmed, P. & Azaron, A. “A hybrid method for solving stochastic job shop scheduling problems”, Applied Mathematics and Computation, 170, 185-206 (2005).
[31] Subramaniam, V., Raheja, A. & Rama Bhupal Reddy, K. “Reactive repair tool for job shop schedules”, International Journal of Production Research, 43, 1-23 (2005).
[32] Xiuli, W. “Research on flexible job shop dynamic scheduling problem”, Journal of System Simulation, 20, 3828-3832 (2008).
[33] Fattahi, P. & Fallahi, A. “Dynamic scheduling in flexible job shop systems by considering simultaneously efficiency and stability”, CIRP Journal of Manufacturing Science and Technology, 2, 114-123 (2010).
[34] Lei, D. “A genetic algorithm for flexible job shop scheduling with fuzzy processing time”, International Journal of Production Research, 48, 2995-3013 (2010).
[35] Hatami, S., Ebrahimnejad, S., Tavakkoli-Moghaddam, R. et al. “Two meta-heuristics for three-stage assembly flowshop scheduling with sequence-dependent setup times”, Int J Adv Manuf Technol, 50, 1153–1164 (2010).
[36] Liu, A.-J., Yang, Y., Xing, Q.-S., Lu, H., Zhang, Y.-D., Zhou, Z.-Y., Wu, G.-H. & Zhao, X.-H. “Dynamic scheduling on multi-objective flexible Job Shop”, Computer Integrated Manufacturing Systems, 17, 2629-2637 (2011).
[37] Jolai, F., Rabiee, M. & Asefi, H. “A novel hybrid meta-heuristic algorithm for a no-wait flexible flow shop scheduling problem with sequence dependent setup times”, International Journal of Production Research, 50, 7447-7466 (2012).
[38] Hokim.,H.,Gyum.,K.,Young.,J. and Park.,S. “The mixing process scheduling using particle swarm optimization”, Computers and industrial engineering, 110, 333-343 (2017).
[39] Naderi-Beni, M., Ghobadian, E.,  Ebrahimnejad, S., Tavakkoli-Moghaddam, R.” Fuzzy bi-objective formulation for a parallel machine scheduling problem with machine eligibility restrictions and sequence-dependent setup times”, International Journal of Production Research,52, 5799-5822,(2014).
 [40] Shen, L.,Dauzere-Pares, S.,Neufeld, J.S. “Solving the flexible job shop scheduling problem with sequence-dependent setup times”, European Journal of Operational Research, 265, 503-516 (2018).
[41] Jamrus, T.,  Chien, C., Gen, M.  and Sethanan, K."Hybrid Particle Swarm Optimization Combined With Genetic Operators for Flexible Job-Shop Scheduling Under Uncertain Processing Time for Semiconductor Manufacturing", IEEE Transactions on Semiconductor Manufacturing, 31(1), 32-41, (2018).
[42] Soleimani Nia, F., & Mehdizadeh, E. “Presenting a Mathematical Model for Flexible job-shop Production Scheduling Problem with Reverse Flows and Solving it by Using Genetic Algorithm”, Journal of Industrial Engineering (Journal of Faculty of Engineering), 52(1), 87-96, (2018).
[43] Huang, X., Guan, Z., Yang, L. “An effective hybrid algorithm for multi-objective flexible job-shop scheduling problem”, Advances in Mechanical Engineering, 10(9), 1-14, (2018). 
[44] Liu, Z., Guo, S., & Wang, L. “Integrated green scheduling optimization of flexible job shop and crane transportation considering comprehensive energy consumption”, Journal of Cleaner Production, 211, 765-786 (2019).
[45] Bagheri, M. & Bashiri, M. “A new mathematical model towards the integration of cell formation with operator assignment and inter-cell layout problems in a dynamic environment”, Applied Mathematical Modelling, 38, 1237-1254 (2014).
[46] Lin, L. & Gen, M. “Auto-tuning strategy for evolutionary algorithms: balancing between exploration and exploitation”, Soft Computing, 13, 157-168 (2009).
Scientia Iranica

Articles in Press, Accepted Manuscript
Available Online from 20 June 2022

Files

Share

How to cite

Statistics