Investigating the two-stage assembly flow shop scheduling problem with uncertain assembling times

Document Type : Research Paper

Authors

1 Department of Industrial Management, Tabriz Branch, Islamic Azad University, Tabriz, Iran

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

3 Department of Industrial Engineering and management, Shahrood University of technology, Shahrood, Iran

4 Department of Management, Tabriz Branch, Islamic Azad University, Tabriz, Iran

Abstract

The majority of scheduling research considers a deterministic environment with pre-known and fixed data. However, under the tools conditions and worker skill levels in assembly work stations, there is uncertainty in the assembling times of the products. This study aims to address a two-stage assembly flow shop scheduling problem with uncertain assembling times of the products which is assumed to follow a normal distribution. The problem is formulated as an MIP model in general form and under deterministic condition. Since the problem is strongly NP-hard, genetic algorithm is adopted with a new solution structure and fitness function to solve the problem on the practical scales. The presented robust procedure aims to maximize the probability of ensuring that makespan will not exceed the expected completion time. In addition, Johnson’s rule is extended and simulated annealing algorithm is tuned for the problem at hand. The computational results indicate that the obtained robust schedules hedge effectively against uncertain assembling times. The results also show that the proposed genetic algorithm gets better robust schedules than Johnson’s rule and outperforms simulated annealing algorithm in terms of deviation percentage ( ) of the expected makespan from the optimal schedule.

Keywords

Main Subjects


Allahverdi, A., & Al-Anzi, F. S. (2006). A PSO and a Tabu search heuristics for the assembly scheduling problem of the two-stage distributed database application. Computers & Operations Research, 33(4), 1056–1080. https://doi.org/10.1016/j.cor.2004.09.002
Allahverdi, A., & Al-Anzi, F. S. (2008). The two-stage assembly flowshop scheduling problem with bicriteria of makespan and mean completion time. International Journal of Advanced Manufacturing Technology, 37, 166–177. https://doi.org/10.1007/S00170-007-0950-Y
Allahverdi, A., & Aydilek, H. (2010). Heuristics for the two-machine flowshop scheduling problem to minimise makespan with bounded processing times. International Journal of Production Research, 48(21), 6367–6385. https://doi.org/10.1080/00207540903321657
Allahverdi, A., & Aydilek, H. (2015). The two stage assembly flowshop scheduling problem to minimize total tardiness. Journal of Intelligent Manufacturing, 26, 225–237. https://doi.org/10.1007/S10845-013-0775-5
Balasubramanian, J., & Grossmann, I. E. (2002). A novel branch and bound algorithm for scheduling flowshop plants with uncertain processing times. Computers & Chemical Engineering, 26(1), 41–57. https://doi.org/10.1016/S0098-1354(01)00735-9
Billaut, J. C., Moukrim, A., & Sanlaville, E. (2008). Flexibility and robustness in scheduling. John Wiley.
Daneshamooz, F., Fattahi, P., & Hosseini, S. M. H. (2021). Mathematical modeling and two efficient branch and bound algorithms for job shop scheduling problem followed by an assembly stage. Kybernetes. https://doi.org/10.1108/K-08-2020-0521/FULL/HTML
Fattahi, P., Hosseini, S. M. H., & Jolai, F. (2013). A mathematical model and extension algorithm for assembly flexible flow shop scheduling problem. The International Journal of Advanced Manufacturing Technology, 65(5–8), 787–802. https://doi.org/10.1007/s00170-012-4217-x
Freeman, N. K., Melouk, S. H., & Mittenthal, J. . (2016). A scenario-based approach for operating theater scheduling under uncertainty. Manufacturing and Service Operations Management, 18(2), 245–261. https://doi.org/10.1287/MSOM.2015.0557
Ghezail, F., Pierreval, H., & Hajri-Gabouj, S. (2010). Analysis of robustness in proactive scheduling: A graphical approach. Computers & Industrial Engineering, 58(2), 193–198. https://doi.org/10.1016/j.cie.2009.03.004
González-Neira, E., M., Montoya-Torres, j., R., & Barrera, D. (2017). Flow-shop scheduling problem under uncertainties: Review and trends. International Journal of Industrial Engineering Computations, 8(4), 399–426.
Goren, S., & Sabuncuoglu, I. (2008). Robustness and stability measures for scheduling: single-machine environment. IIE Transactions, 40(1), 66–83. https://doi.org/10.1080/07408170701283198
Hasani, A., & Hosseini, S. M. H. (2020). A bi-objective flexible flow shop scheduling problem with machine-dependent processing stages: Trade-off between production costs and energy consumption. Applied Mathematics and Computation, 386, 125533. https://doi.org/10.1016/j.amc.2020.125533
Herroelen, W., & Leus, R. (2004). Robust and reactive project scheduling: A review and classification of procedures. International Journal of Production Research, 42(8), 1599–1620. https://doi.org/10.1080/00207540310001638055
Hosseini, S. M. H. (2016). Modeling the hybrid flow shop scheduling problem followed by an assembly stage considering aging effects and preventive maintenance activities. International Journal of Supply and Operations Management, 3(1), 1215–1233. http://www.ijsom.com/article_2669.html
Hosseini, S. M. H., Sana, S. S., & Rostami, M. (2021). Assembly flow shop scheduling problem considering machine eligibility restrictions and auxiliary resource constraints. International Journal of Systems Science: Operations and Logistics, 1–17. https://doi.org/10.1080/23302674.2021.1942586
Kalczynski, P. J., & Kamburowski, J. (2007). On the NEH heuristic for minimizing the makespan in permutation flow shops. Omega, 35(1), 53–60.
Kasperski, A., Kurpisz, A., & Zieliński, P. (2012). Approximating a two-machine flow shop scheduling under discrete scenario uncertainty. European Journal of Operational Research, 217(1), 36–43. https://doi.org/10.1016/j.ejor.2011.08.029
Kazemi, H., Mazdeh, M. M., & Rostami, M. (2017). The two stage assembly flow-shop scheduling problem with batching and delivery. Engineering Applications of Artificial Intelligence, 63, 98–107. https://doi.org/10.1016/j.engappai.2017.05.004
Komaki, G. M., Teymourian, E., Kayvanfar, V., & Booyavi, Z. (2017). Improved discrete cuckoo optimization algorithm for the three-stage assembly flowshop scheduling problem. Computers & Industrial Engineering, 105, 158–173. https://doi.org/10.1016/j.cie.2017.01.006
Koulamas, C., & Kyparisis, G. j. (2001). The three-stage assembly flowshop scheduling problem. Computers & Operations Research, 28(7), 689–704. https://doi.org/10.1016/S0305-0548(00)00004-6
Kouvelis, P., Daniels, R. L., & Vairaktarakis, G. (2000). Robust scheduling of a two-machine flow shop with uncertain processing times. IIE Transactions (Institute of Industrial Engineers), 32(5), 421–432. https://doi.org/10.1023/A:1007640726040
Lan, S., Clarke, J. P., & Barnhart, C. (2006). Planning for robust airline operations: Optimizing aircraft routings and flight departure times to minimize passenger disruptions. Transportation Science, 40(1), 15–28. https://doi.org/10.1287/TRSC.1050.0134
Lee, C. Y., Cheng, T. C. E., & Lin, B. M. T. (1993). Minimizing the makespan in the 3-machine assembly-type flowshop scheduling problem. Management Science, 39(5), 616–625. https://doi.org/10.1287/MNSC.39.5.616
Lei, D., Su, B., & Li, M. (2020). Cooperated teaching-learning-based optimisation for distributed two-stage assembly flow shop scheduling. International Journal of Production Research, 1–14. https://doi.org/10.1080/00207543.2020.1836422
Li, Z., & Ierapetritou, M. (2008). Process scheduling under uncertainty: Review and challenges. Computers & Chemical Engineering, 32(4–5), 715–727. https://doi.org/10.1016/j.compchemeng.2007.03.001
Liao, W., & Fu, Y. (2020). Min–max regret criterion-based robust model for the permutation flow-shop scheduling problem. Engineering Optimization, 52(4), 687–700. https://doi.org/10.1080/0305215X.2019.1607848
Liu, Q., Ullah, S., & Zhang, C. (2011). An improved genetic algorithm for robust permutation flowshop scheduling. The International Journal of Advanced Manufacturing Technology, 56(1–4), 345–354. https://doi.org/10.1007/s00170-010-3149-6
Navaei, J., Ghomi, S. M. T. F., Jolai, F., Shiraqai, M. E., & Hidaji, H. (2013). Two-stage flow-shop scheduling problem with non-identical second stage assembly machines. The International Journal of Advanced Manufacturing Technology Volume, 69, 2215–2226. https://doi.org/10.1007/s00170-013-5187-3
Nawaz, M., Enscore, E., & Ham, I. (1983). A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, 11(1), 91–95. https://doi.org/10.1016/0305-0483(83)90088-9
Sabuncuoglu, I., & Goren, S. (2009). Hedging production schedules against uncertainty in manufacturing environment with a review of robustness and stability research. International Journal of Computer Integrated Manufacturing, 22(2), 138–157. https://doi.org/10.1080/09511920802209033
Sung, C. S., & Juhn, J. (2009). Makespan minimization for a 2-stage assembly scheduling problem subject to component available time constraint. International Journal of Production Economics, 119(2), 392–401. https://doi.org/10.1016/j.ijpe.2009.03.012
Sung, C. S., & Kim, A. H. (2008). A two-stage multiple-machine assembly scheduling problem for minimizing sum of completion times. International Journal of Production Economics, 113(2), 1038–1048. https://doi.org/10.1016/j.ijpe.2007.12.007
Tang, L., & Wang, X. (2008). A predictive reactive scheduling method for color-coating production in steel industry. The International Journal of Advanced Manufacturing Technology, 35, 633–645. https://link.springer.com/content/pdf/10.1007/s00170-006-0740-y.pdf
Torabzadeh, E., & Zandieh, M. (2010). Cloud theory-based simulated annealing approach for scheduling in the two-stage assembly flowshop. Advances in Engineering Software, 41(10–11), 1238–1243. https://doi.org/10.1016/j.advengsoft.2010.06.004
Verderame, P. M., Elia, J. A., Li, J., & Floudas, C. A. (2010). Planning and scheduling under uncertainty: A review across multiple sectors. Industrial and Engineering Chemistry Research, 49(9), 3993–4017. https://doi.org/10.1021/IE902009K
Wang, X., Wang, B., Zhang, X., Xia, X., & Pan, Q. (2021). Two-objective robust job-shop scheduling with two problem-specific neighborhood structures. Swarm and Evolutionary Computation, 61, 100805. https://doi.org/10.1016/j.swevo.2020.100805
Wu, C. C., Bai, D., Azzouz, A., Chung, I. H., Cheng, S. R., Jhwueng, D. C., Lin, W. C., & Said, L. Ben. (2020). A branch-and-bound algorithm and four metaheuristics for minimizing total completion time for a two-stage assembly flow-shop scheduling problem with learning consideration. Engineering Optimization, 52(6), 1009–1036. https://doi.org/10.1080/0305215X.2019.1632303
Yepes-Borrero, J. C., Villa, F., Perea, F., & Caballero-Villalobos, J. P. (2020). GRASP algorithm for the unrelated parallel machine scheduling problem with setup times and additional resources. Expert Systems with Applications, 141, 112959. https://doi.org/10.1016/j.eswa.2019.112959
Zhang, Z., & Tang, Q. (2021a). Integrating flexible preventive maintenance activities into two-stage assembly flow shop scheduling with multiple assembly machines. Computers & Industrial Engineering, 159, 107493. https://doi.org/10.1016/j.cie.2021.107493
Zhang, Z., & Tang, Q. (2021b). Integrating preventive maintenance to two-stage assembly flow shop scheduling: MILP model, constructive heuristics and meta-heuristics. Flexible Services and Manufacturing Journal, 1–48. https://doi.org/10.1007/S10696-021-09403-0
Zheng, P., Zhang, P., Wang, J., Zhang, J., Yang, C., & Jin, Y. (2020). A data-driven robust optimization method for the assembly job-shop scheduling problem under uncertainty. International Journal of Computer Integrated Manufacturing, 1–16. https://doi.org/10.1080/0951192X.2020.1803506
Ziaei, Z., & Jabbarzadeh, A. (2021). A multi-objective robust optimization approach for green location-routing planning of multi-modal transportation systems under uncertainty. Journal of Cleaner Production, 291(0959–6526), 125293. https://doi.org/10.1016/j.jclepro.2020.125293