Robust and Stable Flow Shop Scheduling Problem under Uncertain Processing Times and Machines’ Disruption

Document Type : Original Article

Authors

Department of Industrial Engineering, College of Engineering, Shahed University, Persian Gulf Expressway, Tehran, Iran

Abstract

This paper presents a predictive robust and stable approach for a two-machine flow shop scheduling problem with machine disruption and uncertain job processing time. Indeed, a general approach is proposed that can be used for robustness and stability optimization in an m-machine flow shop or job shop scheduling problem. The robustness measure is the total expected realized completion time. The expected sum of squared aberration between each jobs’ completion time in the realized and initial schedules is the stability measure. We proposed and compared two methods to deal with such an NP-hard problem; a method based on decomposing the problem into sub-problem and solving each sub-problem, and a theorem-based method. The extensive computational results indicated that the second method has a better performance in terms of robustness and stability, especially in large-sized problems. In other words, the second method is preferable because of the better manufacturer responsiveness to the customer and the production staff satisfaction enhancement.

Keywords

References

1.     Fuchigami, H. Y., and Rangel, S., "A survey of case studies in production scheduling: Analysis and perspectives", Journal of Computational Science, Vol. 25, (2018), 425–436. doi:10.1016/j.jocs.2017.06.004
2.     Mokhtari, H., Molla-Alizadeh, S., and Noroozi, A., "Modelling and Optimization of Reliability of a Flowshop Production System via Preventive Maintenance Policy", International Journal of Engineering, Transaction C: Aspects, Vol. 28, No. 12, (2015), 1774–1781. doi:10.5829/idosi.ije.2015.28.12c.10
3.     Yazdi, M., Zandieh, M., and Haleh, H., "A Mathematical Model for Scheduling Elective Surgeries for Minimizing the Waiting Times in Emergency Surgeries", International Journal of Engineering, Transaction C: Aspects, Vol. 33, No. 3, (2020), 448–458. doi:10.5829/ije.2020.33.03c.09
4.     Abtahi, Z., Sahraeian, R., and Rahmani, D., "A Stochastic Model for Prioritized Outpatient Scheduling in a Radiology Center", International Journal of Engineering, Transactions A: Basics, Vol. 33, No. 4, (2020), 598–606. doi:10.5829/ije.2020.33.04a.11
5.     Pinedo, M. L., Scheduling, (2012), Boston, MA, New York: Springer. doi:10.1007/978-1-4614-2361-4
6.     Gupta, J. N. D., and Stafford, E. F., "Flowshop scheduling research after five decades", European Journal of Operational Research, Vol. 169, No. 3, (2006), 699–711. doi:10.1016/j.ejor.2005.02.001
7.     Liao, W., and Fu, Y., "Min–max regret criterion-based robust model for the permutation flow-shop scheduling problem", Engineering Optimization, Vol. 52, No. 4, (2020), 687–700. doi:10.1080/0305215X.2019.1607848
8.     Drwal, M., and Józefczyk, J., "Robust min–max regret scheduling to minimize the weighted number of late jobs with interval processing times", Annals of Operations Research, Vol. 284, No. 1, (2020), 263–282. doi:10.1007/s10479-019-03263-6
9.     Rahmani, D., "A new proactive-reactive approach to hedge against uncertain processing times and unexpected machine failures in the two-machine flow shop scheduling problems", Scientia Iranica, Vol. 24, No. 3, (2017), 1571–1584. doi:10.24200/sci.2017.4136
10.   Framinan, J. M., Fernandez-Viagas, V., and Perez-Gonzalez, P., "Using real-time information to reschedule jobs in a flowshop with variable processing times", Computers & Industrial Engineering, Vol. 129, (2019), 113–125. doi:10.1016/j.cie.2019.01.036
11.   Abtahi, Z., Sahraeian, R., and Rahmani, D., "A New Approach Generating Robust and Stable Schedules in m-Machine Flow Shop Scheduling Problems: A Case Study", International Journal of Engineering, Transaction B: Applications, Vol. 33, No. 2, (2020), 293–303. doi:10.5829/ije.2020.33.02b.14
12.   Mehta, S. V., and Uzsoy, R. M., "Predictable scheduling of a job shop subject to breakdowns", IEEE Transactions on Robotics and Automation, Vol. 14, No. 3, (1998), 365–378. doi:10.1109/70.678447
13.   Lee, J.-Y., and Kim, Y.-D., "Minimizing total tardiness in a two-machine flowshop scheduling problem with availability constraint on the first machine", Computers & Industrial Engineering, Vol. 114, (2017), 22–30. doi:10.1016/j.cie.2017.10.004
14.   Ma, S., Wang, Y., and Li, M., "A Novel Artificial Bee Colony Algorithm for Robust Permutation Flowshop Scheduling", In: Natural Computing for Unsupervised Learning, (2019), 163–182, Springer, Cham. doi:10.1007/978-3-319-98566-4_8
15.   Liu, F., Wang, S., Hong, Y., and Yue, X., "On the Robust and Stable Flowshop Scheduling Under Stochastic and Dynamic Disruptions", IEEE Transactions on Engineering Management, Vol. 64, No. 4, (2017), 539–553. doi:10.1109/TEM.2017.2712611
16.   Cui, W., Lu, Z., Li, C., and Han, X., "A proactive approach to solve integrated production scheduling and maintenance planning problem in flow shops", Computers & Industrial Engineering, Vol. 115, (2018), 342–353. doi:10.1016/j.cie.2017.11.020
17.   Shen, J., and Zhu, Y., "Uncertain flexible flow shop scheduling problem subject to breakdowns", Journal of Intelligent & Fuzzy Systems, Vol. 32, No. 1, (2017), 207–214. doi:10.3233/JIFS-151400
18.   Graham, R. L., Lawler, E. L., Lenstra, J. K., and Kan, A. H. G. R., "Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey", In: Annals of Discrete Mathematics (Vol. 5), (1979), 287–326, Elsevier. doi:10.1016/S0167-5060(08)70356-X
19.   Abedinnia, H., Glock, C. H., and Brill, A., "New simple constructive heuristic algorithms for minimizing total flow-time in the permutation flowshop scheduling problem", Computers & Operations Research, Vol. 74, (2016), 165–174. doi:10.1016/j.cor.2016.04.007
20.   Rakrouki, M. A., Kooli, A., Chalghoumi, S., and Ladhari, T., "A branch-and-bound algorithm for the two-machine total completion time flowshop problem subject to release dates", Operational Research, Vol. 20, No. 1, (2020), 21–35. doi:10.1007/s12351-017-0308-7
21.   Rossi, F. L., Nagano, M. S., and Sagawa, J. K., "An effective constructive heuristic for permutation flow shop scheduling problem with total flow time criterion", The International Journal of Advanced Manufacturing Technology, Vol. 90, Nos. 1–4, (2017), 93–107. doi:10.1007/s00170-016-9347-0
22.   Ghezail, F., Pierreval, H., and Hajri-Gabouj, S., "Analysis of robustness in proactive scheduling: A graphical approach", Computers & Industrial Engineering, Vol. 58, No. 2, (2010), 193–198. doi:10.1016/j.cie.2009.03.004
23.   Kasperski, A., Kurpisz, A., and Zieliński, P., "Approximating a two-machine flow shop scheduling under discrete scenario uncertainty", European Journal of Operational Research, Vol. 217, No. 1, (2012), 36–43. doi:10.1016/j.ejor.2011.08.029
24.   Katragjini, K., Vallada, E., and Ruiz, R., "Flow shop rescheduling under different types of disruption", International Journal of Production Research, Vol. 51, No. 3, (2013), 780–797. doi:10.1080/00207543.2012.666856
25.   Ying, K.-C., "Scheduling the two-machine flowshop to hedge against processing time uncertainty", Journal of the Operational Research Society, Vol. 66, No. 9, (2015), 1413–1425. doi:10.1057/jors.2014.100
26.   Fazayeli, M., Aleagha, M.-R., Bashirzadeh, R., and Shafaei, R., "A hybrid meta-heuristic algorithm for flowshop robust scheduling under machine breakdown uncertainty", International Journal of Computer Integrated Manufacturing, Vol. 29, No. 7, (2016), 709–719. doi:10.1080/0951192X.2015.1067907
27.   Pinedo, M., and Singer, M., "A shifting bottleneck heuristic for minimizing the total weighted tardiness in a job shop", Naval Research Logistics (NRL), Vol. 46, No. 1, (1999), 1–17. doi: https://doi.org/10.1002/(SICI)1520-6750(199902)46:13.0.CO;2-%23
28.   Shi, F., Zhao, S., and Meng, Y., "Hybrid algorithm based on improved extended shifting bottleneck procedure and GA for assembly job shop scheduling problem", International Journal of Production Research, Vol. 58, No. 9, (2020), 2604–2625. doi:10.1080/00207543.2019.1622052
29.   Koulamas, C., "A guaranteed accuracy shifting bottleneck algorithm for the two-machine flowshop total tardiness problem", Computers & Operations Research, Vol. 25, No. 2, (1998), 83–89. doi:10.1016/S0305-0548(97)00028-2
30.   Mukherjee, S., and Chatterjee, A. K., "Applying machine based decomposition in 2-machine flow shops", European Journal of Operational Research, Vol. 169, No. 3, (2006), 723–741. doi:10.1016/j.ejor.2004.10.028
31.   Elyasi, A., and Salmasi, N., "Stochastic flow-shop scheduling with minimizing the expected number of tardy jobs", The International Journal of Advanced Manufacturing Technology, Vol. 66, Nos. 1–4, (2013), 337–346. doi:10.1007/s00170-012-4328-4
32.   Allahverdi, M., and Allahverdi, A., "Minimizing total completion time in a two-machine no-wait flowshop with uncertain and bounded setup times", Journal of Industrial & Management Optimization, Vol. 16, No. 5, (2020), 2439–2457. doi:10.3934/jimo.2019062
33.   Abtahi, Z., Sahraeian, R., and Rahmani, D., "Predictive heuristics to generate robust and stable schedules in single machine systems under disruptions", Scientia Iranica, Vol. 16, No. 5, (2019), 0–0. doi:10.24200/sci.2019.50809.1873
34.   Pinedo, M., "Optimal policies in stochastic shop scheduling", Annals of Operations Research, Vol. 1, No. 3, (1984), 305–329. doi:10.1007/BF01874395
35.   Nouiri, M., Bekrar, A., Jemai, A., Trentesaux, D., Ammari, A. C., and Niar, S., "Two stage particle swarm optimization to solve the flexible job shop predictive scheduling problem considering possible machine breakdowns", Computers & Industrial Engineering, Vol. 112, (2017), 595–606. doi:10.1016/j.cie.2017.03.006
International Journal of Engineering
Volume 34, Issue 4
TRANSACTIONS A: Basics
April 2021
Pages 935-947

Files

Cited by

Share

How to cite

Statistics