This study addresses multi-stage hybrid flow shop scheduling in which a job is reworked if the queue time between two arbitrary stages exceeds an upper limit. The problem is to determine the allocations of jobs to machines at each stage and the start times of jobs and rework setups/operations when incurred. A mixed integer programming model is proposed for each of the makespan and the total tardiness measures. Then, because the problem is NP-hard, a scheduling mechanism is proposed that consists of three phases: (a) filtering the jobs to be delayed; (b) searching the jobs to be reworked; and (c) dispatching non-delayed and delayed jobs sequentially. Simulation results show that the mechanism proposed in this study outperforms the conventional dispatching approach in the high rework setup time case for the makespan problem and low/high setup time cases for the tardiness problem. The best priority rules of the mechanism under each of the measures are also reported.
KimY-DLeeD-HKimJ-U, et al. A simulation study on lot release control, dispatching and batch scheduling in semiconductor wafer fabrication facilities. J Manuf Syst1998; 17(2): 107–117.
2.
ChoiH-SKimH-WLeeD-H, et al. Scheduling algorithms for two-stage reentrant hybrid flow shops: minimizing makespan under the maximum allowable due dates. Int J Adv Manuf Technol2009; 42(9): 963–973.
3.
KimH-WLeeD-H. Heuristics for reentrant hybrid flow shops with unrelated parallel machines. Proc IMechE, Part B: J Engineering Manufacture2009; 223(4): 433–442.
4.
ChoiH-SKimJ-SLeeD-H. Real-time scheduling for reentrant hybrid flow shops: a decision tree based mechanism and its application to a TFT-LCD line. Expert Syst Appl2011; 38(4): 3514–3521.
5.
ArimaSKobayashiAWangYF, et al. Optimization of re-entrant hybrid flows with multiple queue time constraints in batch processes of semiconductor manufacturing. IEEE Trans Semicond Manuf2015; 28(4): 528–544.
6.
LiuMYangXZhangJ, et al. Scheduling a tempered glass manufacturing system: a three-stage hybrid flow shop model. Int J Prod Res2017; 55(20): 6084–6107.
7.
WangSWangXChuF, et al. An energy-efficient two-stage hybrid flow shop scheduling problem in a glass production. Int J Prod Res2020; 58(8): 2283–2314.
8.
LongJZhengZGaoX, et al. Scheduling a realistic hybrid flow shop with stage skipping and adjustable processing time in steel plants. Appl Soft Comput2018; 64: 536–549.
9.
FuchigamiHYRangelS. A survey of case studies in production scheduling: analysis and perspectives. J Comput Sci2018; 25: 425–436.
10.
ChangXJiaXFuS, et al. Digital twin and deep reinforcement learning enabled real-time scheduling for complex product flexible shop-floor. Proc IMechE, Part B: J Engineering Manufacture2023; 237(8): 1254–1268.
11.
LinnRZhangW. Hybrid flow shop scheduling: a survey. Comput Ind Eng1999; 37(1–2): 57–61.
12.
RibasIRainerLFramiñanJM. Review and classification of hybrid flow shop scheduling problems from a production system and a solutions procedure perspective. Comput Oper Res2010; 37(8): 1439–1454.
LeeTLoongY. A review of scheduling problem and resolution methods in flexible flow shop. Int J Ind Eng Comput2019; 10(1): 67–88.
15.
ChenTLChengCYChouYH. Multi-objective genetic algorithm for energy-efficient hybrid flow shop scheduling with lot streaming. Ann Oper Res2020; 290(1): 813–836.
16.
LiYLiXGaoL, et al. A discrete artificial bee colony algorithm for distributed hybrid flowshop scheduling problem with sequence-dependent setup times. Int J Prod Res2021; 59(13): 3880–3899.
17.
BaiXGershwinSB. A manufacturing scheduler’s perspective on semiconductor fabrication. In: VLSI Memo. Cambridge, MA: Massachusetts Institute of Technology, 1989, pp.89–518.
18.
JooB-JKimY-D. A branch-and-bound algorithm for a two-machine flowshop scheduling problem with limited waiting time constraints. J Oper Res Soc2009; 60(4): 572–582.
19.
SchollWDomaschkeJ. Implementation of modeling and simulation in semiconductor wafer fabrication with time constraints between wet etch and furnace operations. IEEE Trans Semicond Manuf2000; 13(3): 273–277.
20.
PirovanoGCicculloFPeroM, et al. Scheduling batches with time constraints in wafer fabrication. Int J Oper Res2018; 37(1): 1–31.
21.
HarjunkoskiIGrossmannIE. A decomposition approach for the scheduling of a steel plant production. Comput Chem Eng2001; 25(11–12): 1647–1660.
22.
AkkermanRvan DonkDPGaalmanG. Influence of capacity-and time-constrained intermediate storage in two-stage food production systems. Int J Prod Res2007; 45(13): 2955–2973.
23.
GicquelCHegeLMinouxM, et al. A discrete time exact solution approach for a complex hybrid flow-shop scheduling problem with limited-wait constraints. Comput Oper Res2012; 39(3): 629–636.
24.
YangDLChernMS. A two-machine flowshop sequencing problem with limited waiting time constraints. Comput Ind Eng1995; 28(1): 63–70.
25.
WuKZhaoNGaoL, et al. Production control policy for tandem workstations with constant service times and queue time constraints. Int J Prod Res2016; 54(21): 6302–6316.
26.
SuLH. A hybrid two-stage flowshop with limited waiting time constraints. Comput Ind Eng2003; 44(3): 409–424.
27.
HamMLeeY-HAnJ-H. IP-based real time dispatching for two machine batching problem with time window constraints. IEEE Trans Autom Sci Eng2011; 8(3): 589–597.
28.
YuT-SKimH-JLeeT-E. Minimization of waiting time variation in a generalized two-machine flow shop with waiting time constraints and skipping jobs. IEEE Trans Semicond Manuf2017; 30(2): 155–165.
29.
WangFJuFKangN. Transient analysis and real-time control of geometric serial lines with residence time constraints. IISE Trans2019; 51(7): 709–728.
30.
LeeJ-Y. A genetic algorithm for a two-machine flowshop with a limited waiting time constraint and sequence-dependent setup times. Math Probl Eng2020; 2020: 8833645.
31.
HanJ-HLeeJ-Y. Heuristics for a two-stage assembly-type flow shop with limited waiting time constraints. Appl Sci2021; 11(23): 11240.
32.
JeongBHanJ-HLeeJ-Y. Metaheuristics for a flow shop scheduling problem with urgent jobs and limited waiting times. Algorithms2021; 14(11): 323.
33.
LiYDaiZ. A two-stage flow-shop scheduling problem with incompatible job families and limited waiting time. Eng Optim2020; 52(3): 484–506.
34.
ChenJSYangJS. Model formulations for the machine scheduling problem with limited waiting time constraints. J Inf Optim Sci2006; 27(1): 225–240.
35.
HamM. Integer programming-based real-time dispatching (i-RTD) heuristic for wet-etch station at wafer fabrication. Int J Prod Res2012; 50(10): 2809–2822.
36.
KlemmtAMönchL. Scheduling jobs with time constraints between consecutive process steps in semiconductor manufacturing. In: Proceedings of the winter simulation conference, Berlin, Germany, 2012, pp.2173–2182. New York: IEEE.
37.
WangMSrivathsanSHuangE, et al. Job dispatch control for production lines with overlapped time window constraints. IEEE Trans Semicond Manuf2018; 31(2): 206–214.
38.
KimH-ILeeD-H. Scheduling algorithms for multistage flow shops with reworks under overlapped queue time limits. Int J Prod Res. Epub ahead of print 07 November 2022. DOI: 10.1080/00207543.2022.2139004.
39.
BehnamianJZandiehM. A discrete colonial competitive algorithm for hybrid flowshop scheduling to minimize earliness and quadratic tardiness penalties. Expert Syst Appl2011; 38(12): 14490–14498.
40.
AttarSFMohammadiMTavakkoli-MoghaddamR. Hybrid flexible flowshop scheduling problem with unrelated parallel machines and limited waiting times. Int J Adv Manuf Technol2013; 68(5–8): 1583–1599.
41.
AttarSFMohammadiMTavakkoli-MoghaddamR, et al. Solving a new multi-objective hybrid flexible flowshop problem with limited waiting times and machine-sequence-dependent set-up time constraints. Int J Comput Integr Manuf2014; 27(5): 450–469.
42.
ChungT-PSunHLiaoC-J. Two new approaches for a two-stage hybrid flowshop problem with a single batch processing machine under waiting time constraint. Comput Ind Eng2017; 113: 859–870.
43.
HuangZShiZZhangC, et al. A note on two new approaches for a two-stage hybrid flowshop problem with a single batch processing machine under waiting time constraint. Comput Ind Eng2017; 110: 590–593.
44.
SantosaBSiswantoN. Discrete particle swarm optimization to solve multi-objective limited-wait hybrid flow shop scheduling problem. IOP Conf Ser Mater Sci Eng2018; 337(1): 012006.
45.
HongIHChouCCLeePK. Admission control in queue-time loop production-mixed integer programming with Lagrangian relaxation (MIPLAR). Comput Ind Eng2019; 129: 417–425.
46.
QinMWangRShiZ, et al. A genetic programming-based scheduling approach for hybrid flow shop with a batch processor and waiting time constraint. IEEE Trans Autom Sci Eng2021; 18(1): 94–105.
47.
PinedoML. Scheduling: theory, algorithms and systems. New York, NY: Springer, 2018.
48.
MainieriGBRonconiDP. New heuristics for total tardiness minimization in a flexible flowshop. Optim Lett2013; 7(4): 665–684.
Supplementary Material
Please find the following supplemental material available below.
For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.
For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.
