Modelling and robust scheduling of two-stage assembly flow shop under uncertainty in assembling times

Subject Areas : Mathematical Optimization

Maryam seyedhamzeh ¹ , hossein amoozad khalili ² , Seyed Mohammad Hassan Hosseini ³ , mortaza honarmand azimi ⁴ , Kamaladdin Rahmani ⁵

1 - Department of Industrial Management, Tabriz Branch, Islamic Azad University, Tabriz, Iran.
2 - Department of Industrial Engineering, Nowshahr Branch, Islamic Azad University, Nowshahr, 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.
5 - Department of Management, Tabriz Branch, Islamic Azad University, Tabriz, Iran.

Received: 2021-08-08 Accepted : 2021-11-04 Published : 2021-08-01

Keywords: Uncertainty, Scheduling, Robustness, assembly flow shop,

Abstract :

This paper focuses on robust scheduling for an assembly flow shop where assembling times are uncertain. The considered manufacturing environment is a two-stage production system that consists of a processing stage followed by an assembly stage. There are two parallel machines in the first stage to process the components followed by an assembly stage wherein, the components are assembled to products. The majority of scheduling research considers a deterministic environment with pre-known and fixed data. However, in real-world condition, several kinds of uncertainties should be considered. In this article, the scheduling problem is tackle under uncertainty and the assembling time of each product at the second stage is the source of uncertainty. The problem is described and formulated as a mixed-integer linear programing model under deterministic condition. After that, the uncertainty issue is discussed and the robust scheduling procedure is introduced to minimize the maximum completion time of all products based on the min–max regret approach. To solve the robust scheduling an exact method is proposed to solve the problem on the small scales. Moreover, two approximate methods are modified and used to solve this NP-hard problem on the small and practical scales. The performances of the proposed methods are evaluated by several numerical examples taken from valid references. Computational results indicate that the proposed robust scheduling methods provide effective hedges against processing time uncertainty while maintaining excellent expected makespan performance.

References:

[1] I. Hamdi and S. Toumi, “MILP models and valid inequalities for the two-machine permutation flowshop scheduling problem with minimal time lags,” J. Ind. Eng. Int., vol. 15, no. 1, pp. 223–229, Dec. 2019, doi: 10.1007/S40092-019-00331-1.

[2] R. Buddala and S. Mahapatra, S., “Improved teaching–learning-based and JAYA optimization algorithms for solving flexible flow shop scheduling problems,” J. Ind. Eng. Int., vol. 14, no. 3, pp. 555–570, Sep. 2018, doi: 10.1007/S40092-017-0244-4.

[3] M. Afzalirad and J. Rezaeian, “Resource-constrained unrelated parallel machine scheduling problem with sequence dependent setup times, precedence constraints and machine eligibility restrictions,” Comput. Ind. Eng., vol. 98, pp. 40–52, Aug. 2016, doi: 10.1016/J.CIE.2016.05.020.

[4] F. Daneshamooz, P. Fattahi, and S. M. H. Hosseini, “Scheduling in a flexible job shop followed by some parallel assembly stations considering lot streaming,” Eng. Optim., pp. 1–20, 2021, doi: 10.1080/0305215X.2021.1887168.

[5] P. Fattahi, S. M. H. Hosseini, and F. Jolai, “A mathematical model and extension algorithm for assembly flexible flow shop scheduling problem,” Int. J. Adv. Manuf. Technol., vol. 65, no. 5–8, pp. 787–802, 2013, Accessed: Aug. 07, 2021. [Online]. Available: https://doi.org/10.1007 /s00170-012-4217-x.

[6] T. Chaari, S. Chaabane, T. Loukil, and D. Trentesaux, “A genetic algorithm for robust hybrid flow shop scheduling,” Int. J. Comput. Integr. Manuf., vol. 24, no. 9, pp. 821–833, 2011, doi: 10.1080/0951192X.2011.575181.

[7] R. Montemanni, “A mixed integer programming formulation for the total flow time single machine robust scheduling problem with interval data,” J. Math. Model. Algorithms, vol. 6, no. 2, pp. 287–296, Jun. 2007, doi: 10.1007/S10852-006-9044-3.
[8] A. Allahverdi and H. Aydilek, “Heuristics for the two-machine flowshop scheduling problem to minimise makespan with bounded processing times,” Int. J. Prod. Res., vol. 48, no. 21, pp. 6367–6385, Nov. 2010, doi: 10.1080/00207540903321657.
[9] Z. Ziaei and A. Jabbarzadeh, “A multi-objective robust optimization approach for green  location-routing planning of multi-modal transportation systems under uncertainty,” J. Clean. Prod., vol. 291, no. 0959–6526, p. 125293, 2021, Accessed: Aug. 20, 2021. [Online]. Available:  https://doi.org/10.1016/j.jclepro.2020.125293.
[10]N. M. Matsveichuk, Y. Sotskov, N. G. Egorova, and T. C. Lai, “Schedule execution for two- machine flow-shop with interval processing times,” Math. Comput. Model., vol. 49, no. 5–6, pp. 991– 1011, 2009, [Online]. Available: doi.org/10.1016/j.mcm.2008.02.004.
[11]N. M. Matsveichuk, Y. N. Sotskov, and F. Werner, “The dominance digraph as a solution to the two-machine flow-shop problem with interval processing times,” Optimization, vol. 60, no. 12, pp. 1493–1517, Dec. 2011, doi: 10.1080/02331931003657691.
[12]X. Feng, F. Zheng, and Y. Xu, “Robust scheduling of a two-stage hybrid flow shop with uncertain interval processing times,” Int. J. Prod. Res., vol. 54, no. 12, pp. 3706–3717, Jun. 2016, doi: 10.1080/00207543.2016.1162341.
[13]G. M. Komaki, E. Teymourian, V. Kayvanfar, and Z. Booyavi, “Improved discrete cuckoo optimization algorithm for the three-stage assembly flowshop scheduling problem,” Comput. Ind. Eng., vol. 105, pp. 158–173, 2017, Accessed: Aug. 07, 2021. [Online]. Available: https://doi.org/10.1016/j.cie.2017.01.006.
[14]A. Allahverdi and F. S. Al-Anzi, “The two-stage assembly scheduling problem to minimize total completion time with setup times,” Comput. Oper. Res., vol. 36, pp. 2740–2747, 2009, doi: 10.1016/j.cor.2008.12.001.
[15]C. Y. Lee, T. C. E. Cheng, and B. M. T. Lin, “Minimizing the makespan in the 3-machine assembly-type flowshop scheduling problem,” Manage. Sci., vol. 39, no. 5, pp. 616–625, 1993, doi:
10.1287/MNSC.39.5.616.
[16]C. N. Potts, S. V. Sevast’janov, V. A. Strusevich, L. N. Van Wassenhove, and C. M. Zwaneveld, “The two-stage assembly scheduling problem: Complexity and approximation,” Comput. Oper.
Res., vol. 43, no. 2, pp. 346–355, Apr. 1995, doi: 10.1287/OPRE.43.2.346.
[17]X. Sun, K. Morizawa, and H. Nagasawa, “Powerful heuristics to minimize makespan in fixed, 3-machine, assembly-type flowshop scheduling,” Eur. J. Oper. Res., vol. 146, no. 3, pp. 498–516, 2003, Accessed: Aug. 07, 2021. [Online]. Available: https://doi.org/10.1016/S0377-2217(02)00245-X.
[18]C. Koulamas and G. j. Kyparisis, “The three-stage assembly flowshop scheduling problem,” Comput. Oper. Res., vol. 28, no. 7, pp. 689–704, 2001, Accessed: Aug. 22, 2021. [Online]. Available:
https://doi.org/10.1016/S0305-0548(00)00004-6.
[19]A. Maleki-Darounkolaei, M. Modiri, R. Tavakkoli-Moghaddam, and I. Seyyedi, “A three-stage assembly flow shop scheduling problem with blocking and sequence-dependent set up times,” J. Ind. Eng. Int., vol. 8, no. 1, pp. 1–7, Dec. 2012, doi: 10.1186/2251-712X-8-26.
[20]P. Fattahi, S. M. H. Hosseini, and F. Jolai, “A branch and bound algorithm for hybrid flow shop scheduling problem with setup time and assembly operations,” Appl. Math. Model., vol. 38, no. 1, pp. 119–134, 2014, Accessed: Aug. 08, 2021. [Online]. Available: https://doi.org/10.1016/j.apm.2013.06.005.
[21]J. M. Framinan and p. p. Gonzalez, “The 2-stage assembly flowshop scheduling problem with total completion time: Efficient constructive heuristic and metaheuristic,” Comput. Oper. Res., vol. 88, no. 0305– 0548, pp. 237–246, 2017, doi: 10.1016/j.cor.2017.07.012.
[22]G. M. Komaki, S. Sheikh, and B. Malakooti, “Flow shop scheduling problems with assembly operations: a review and new trends,” Int. J. Prod. Res., vol. 57, no. 10, pp. 2926–2955, May 2019, doi: 10.1080/00207543.2018.1550269.
[23]C. C. Wu et al., “A branch-and-bound algorithm and four metaheuristics for minimizing total completion time for a two-stage assembly flowshop scheduling problem with learning consideration,” Eng. Optim., vol. 52, no. 6, pp. 1009–1036, Jun. 2020, doi: 10.1080/ 0305215X.2019.1632303.
[24]J. Deng, L. Wang, S. Y. Wang, and X. L. Zheng, “A competitive memetic algorithm for the distributed two-stage assembly flow-shop scheduling problem,” Int. J. Prod. Res., vol. 54, no. 12, pp. 3561–3577, Jun. 2016, doi: 10.1080/00207543.2015.1084063.
[25]D. Lei, B. Su, and M. Li, “Cooperated teaching-learning-based optimisation for distributed two-stage assembly flow shop scheduling,” Int. J. Prod. Res., pp. 1–14, 2020, doi: 10.1080/
00207543.2020.1836422.
[26]J. Huang and X. Gu, “Distributed assembly permutation flow-shop scheduling problem with sequence-dependent set-up times using a novel biogeography-based optimization algorithm,” Eng. Optim., 2021, doi:10.1080/0305215X.2021.1886289.
[27]P. Kouvelis, R. L. Daniels, and G. Vairaktarakis, “Robust scheduling of a two-machine flow shop with uncertain processing times,” IIE Trans., vol. 32, no. 5, pp. 421–432, 2000, doi:  10.1023/A:1007640726040.
[28]M. T. Jensen, “Neighbourhood based robustness applied to tardiness and total flowtime job shops,” Parallel Probl. Solving from Nat. PPSN VI. PPSN 2000. Lect. Notes Comput. Sci., vol. 1917, pp. 283–292, 2000, doi: 10.1007/3-540-45356-3_28.
[29]J. C. Billaut, A. Moukrim, and E. Sanlaville, Flexibility and robustness in scheduling. John Wiley, 2008.
[30]J. Balasubramanian and I. E. Grossmann, “A novel branch and bound algorithm for scheduling flowshop plants with uncertain processing times,” Comput. Chem. Eng., vol. 26, no. 1, pp. 41–57, 2002, Accessed: Aug. 23, 2021. [Online]. Available: https://doi.org/10.1016/S0098- 1354(01)00735-9.
[31]Z. Li and M. Ierapetritou, “Process scheduling under uncertainty: Review and challenges,” Comput. Chem. Eng., vol. 32, no. 4–5, pp. 715–727, 2008, Accessed: Aug. 07, 2021. [Online]. Available: https://doi.org/10.1016/j.compchemeng.2007.03.001.
[32]P. M. Verderame, J. A. Elia, J. Li, and C. A. Floudas, “Planning and scheduling under uncertainty: A review across multiple sectors,” Ind. Eng. Chem. Res., vol. 49, no. 9, pp. 3993–4017, May 2010, doi: 10.1021/IE902009K.
[33]X. Xu, W. Cui, J. Lin, and Y. Qian, “Robust makespan minimisation in identical parallel machine scheduling problem with interval data,” Int. J. Prod. Res., vol. 51, no. 12, pp. 3532–3548, Jun. 2013, doi: 10.1080/00207543.2012.751510.
[34]M. González-Neira, E., R. Montoya-Torres, j., and D. Barrera, “Flowshop scheduling problem under uncertainties: Review and trends,” Int.J. Ind. Eng. Comput., vol. 8, no. 4, pp. 399–426, 2017.
[35]S. Tadayonirad, H. Seidgar, H. Fazlollahtabar, and R. Shafaei, “Robust scheduling in two-stage assembly flow shop problem with random machine breakdowns: integrated meta-heuristic algorithms and simulation approach,” Assem. Autom., vol. 39, no. 5, pp. 944–962, Oct. 2019, doi: 10.1108/AA-10-2018-0165/FULL/HTML.
[36]M. F. Amiri and J. Behnamian, “Multi-objective green flowshop scheduling problem under uncertainty: Estimation of distribution algorithm,” J. Clean. Prod., vol. 251, 2020, Accessed: Aug. 07, 2021. [Online]. Available: https://www.sciencedirect.com/science/ article/pii/S0959652619346049.
[37]C.-C. Wu, J. N. D. Gupta, S. R. Cheng, B. M. T. Lin, S. H. Yip, and W. C. Lin, “Robust scheduling for a two-stage assembly shop with scenariodependent processing times,” Int. J. Prod. Res., vol. 59, no. 17, pp. 5372– 5387, 2021, doi: 10.1080/00207543.2020.1778208.
[38]P. Zheng, P. Zhang, J. Wang, J. Zhang, C. Yang, and Y. Jin, “A datadriven robust optimization method for the assembly job-shop scheduling problem under uncertainty,” Int. J. Comput. Integr. Manuf., pp. 1–16, 2020, doi: 10.1080/0951192X.2020.1803506.
[39]S. M. H. Hosseini, “Modelling and solving the job shop scheduling Problem followed by an assembly stage considering maintenance operations and access restrictions to machines,” J. Optim. Ind. Eng., vol. 12, no. 1, pp. 63–78, 2019, doi: 10.22094/joie.2018.760.1484.
[40]M. Inuiguchi and M. Sakawa, “Minimax regret solution to linear programming problems with an interval objective function,” Eur. J. Oper. Res., vol. 86, no. 3, pp. 526–536, 1995, Accessed: Aug. 08, 2021. [Online]. Available: https://doi.org/10.1016/0377-2217(94)00092-Q.
[41]H. E. Mausser and M. Laguna, “A new mixed integer formulation for the maximum regret problem,” Int. Trans. Oper. Res., vol. 5, no. 5, pp. 389–403, 1998, doi: 10.1111/J.1475-3995.1998.TB00122.X.
[42]H. E. Mausser and M. Laguna, “A heuristic to minimax absolute regret for linear programs with interval objective function coefficients,” Eur. J. Oper. Res., vol. 117, no. 1, pp. 157–174, 1999, Accessed: Aug. 07, 2021. [Online]. Available: https://doi.org/10.1016/S0377-2217(98)00118-0.
[43]J. Jozefowska, M. Mika, R. Rozycki, G. Waligora, and J. Weglarz, “Local search metaheuristics for discrete–continuous scheduling problems,” Eur. J. Oper. Res., vol. 107, no. 2, pp. 354–370, 1998, Accessed: Aug. 07, 2021. [Online]. Available: https://doi.org/10.1016/ S0377-2217(97)00345-7.