Discrete OptimizationFlow shops with machine maintenance: Ordered and proportionate cases
Introduction
We consider the m-machine, n-job flow shop problem with the machines subject to maintenance. Let pij denote the processing time of job j on machine i. The objective is to find a sequence for the n jobs such that the overall completion time of the very last job, typically referred to as the makespan and denoted by Cmax, is minimized.
In this paper we assume that the following relationships hold between the processing times of the jobs on the machines:
- •
If, for some 1 ⩽ h ⩽ m, phj < phk, then pij ⩽ pik for i = 1, … , m.
- •
If, for some 1 ⩽ k ⩽ n, pik < phk, then pij ⩽ phj for j = 1, … , n.
A flow shop satisfying the above conditions is referred to as an ordered flow shop [29], [30]. If the processing times of job j on all m machines are equal to pj, i.e., pij = pj, then the flow shop is referred to as a proportionate flow shop [27]. Examples of job processing times in an ordered flow shop and in a proportionate flow shop are given below (see Table 1).
We assume that a number of maintenance periods for the machines have been scheduled in advance. The models considered are referred to in what follows, respectively, as ordered flow shops with machine maintenance and as proportionate flow shops with machine maintenance.
There are many applications of the models described above in practice. First, consider a manufacturing environment for semiconductor and liquid crystal display (LCD) panels, where wafers and glasses are delivered in batches (referred to as foups in semiconductor manufacturing and as cassettes in LCD manufacturing). The manufacturing line consists of a series of stages and the process at each stage is executed in a batch mode. In this setting, the number of wafers belonging to a foup affects the processing time of the foup on each machine. Specifically, the processing time of a batch is proportional to the number of wafers in the batch. Therefore, the larger the number of wafers in a foup, the longer the processing time of the foup at every stage. Furthermore, each stage has a unique time for the processing of a wafer and thus, the longer the processing time of a wafer at a particular stage, the longer the processing time of a foup at that stage. This characteristic can be regarded as the ordered property, as defined above. For some reason, the processing time of a wafer at each stage may be identical. When the material handling time of a wafer is dominant in comparison to the processing time of a wafer, then the previous wafer can be processed during the handling of the next wafer. Thus, the processing time of a foup is determined only by the number of wafers in a foup. This case may be considered a proportionate flow shop. Furthermore, consider a setting in which maintenance periods are scheduled in advance. In the semiconductor and LCD industries it typically is necessary to schedule maintenance periods in advance in order to ensure a stable quality of production.
We will use the following notation throughout this paper. Let n denote the number of jobs and m the number of machines. Let pij refer to the processing requirement of job j on machine i. Let Ci,j and Bi,j be the completion time and the starting time of job j on machine i, respectively. Let σ denote a job sequence, and let σ(j) refer to the job that is in the jth position in σ. Let Cmax(σ) denote the makespan of σ. Let Mi,k ≡ [si,k, fi,k] be the kth maintenance which has been scheduled to start at time si,k and finish at time fi,k on machine i.
The problems in this paper can be defined as follows.
The ordered flow shop with maintenances (OFSM) is defined as the problem of finding a schedule that minimizes the makespan in an n-job, m-machine ordered flow shop, in which the starting time and the finishing time of each maintenance period have been scheduled in advance. The proportionate flow shop with maintenances (PFSM) is defined similarly as above.
The following assumptions will be used throughout the paper:
- 1.
The jobs are sorted in non-decreasing order of their processing times, i.e. pi,1 ⩽ pi,2 ⩽ ⋯ ⩽ pi,n, i = 1, 2, … , m.
- 2.
The machine is resumable, i.e., a job interrupted by maintenance can be continued after completion of the maintenance without any additional processing.
- 3.
Only permutation schedules are considered in this paper.
In order to provide a clear overview of the paper, we summarize in Fig. 1. the problems under consideration and their computational complexity in accordance to the number of maintenance periods and when and where they occur.
The remainder of the paper is organized as follows. In Section 2, we discuss the related literature. In Section 3 we consider the OFSM and determine the computational complexity of the problem. In Section 4, we analyze the complexity of PFSM and present an approximation algorithm. In Section 5, we discuss the proportionate flow shop problems with other objectives, including the maximum lateness and the total completion time. Finally, we present some concluding remarks in the last section.
Section snippets
Literature review
Since Johnson’s seminal paper in 1954, which analyzed the minimization of the makespan in a two-machine flow shop [14], many researchers have studied flow shop problems. In the recent literature, Ng and Kovalyov [22] considered the problem of batching and scheduling in a flow shop environment with the makespan as objective, and Yuan et al. [32] investigated the complexity of two-machine flow shop scheduling with transportation constraints with the makespan as objective. Ng et al. [23]
The OFSM problem
In this section, we will show that the OFSM problem is strongly NP-hard, and it remains NP-hard with just a single maintenance. We verify that sequencing jobs according to LPT yields an optimal schedule if the first machine is the slowest and all maintenances occur on the first machine.
We will show the strong NP-hardness of the two-machine OFSM problem through a reduction from the 3-Partition Problem, which is defined as follows.
3-Partition: Given 3l integers a1, a2, … , a3l and b > 4 such that b/4 < aj
The PFSM problem
In this section, we consider the case with multiple maintenance periods, and show that the two-machine PFSM problem is NP-hard even if there are only two maintenance periods. Since the two-machine problem is polynomially solvable if both maintenances occur on the same machine, we will show that the three-machine problem is NP-hard if both maintenances occur on the second machine. Then we investigate approximability, and develop a 3/2-approximation algorithm for the problem with two maintenance
The proportionate flow shop problems with other objectives
In this section, we discuss the complexity of proportionate flow shop problems with other objective functions, namely the maximum lateness and total completion time.
Conclusions
In this paper we studied the computational complexity of ordered flow shops and proportionate flow shops with maintenances. We proved that certain cases are NP-hard while other cases are solvable in polynomial time. In addition, we present a -approximation algorithm for the m-machine proportionate flow shop problem with two maintenances. Furthermore, we present complexity results on problems with other objectives.
One result we obtained can also be applied to a model with random machine
References (32)
Two-machine proportionate flowshop scheduling with breakdown to minimize maximum lateness
Computers and Operations Research
(1996)A polynomial-time approximation scheme for the two-machine flow shop scheduling problem with an availability constraint
Computers and Operations Research
(2006)- et al.
An improved heuristic for tow-machine flowshop scheduling with an availability constraint
Operations Research Letters
(2000) - et al.
Minimizing maximum completion time in a proportionate flow shop with one machine of different speed
European Journal of Operational Research
(2007) - et al.
The three-machine proportionate flow shop with unequal machine speeds
Operations Research Letters
(2003) - et al.
A note on the proportional flow shop with a bottleneck machine
European Journal of Operational Research
(2009) - et al.
Two-machine flow shops with limited machine availability
European Journal of Operational Research
(2002) - et al.
Approximation results for flow shop scheduling problems with machine availability constraints
Computers and Operations Research
(2009) Minimizing the makespan in the two-machine flowshop scheduling problem with an availability constraint
Operations Research Letters
(1997)Two-machine flowshop scheduling with availability constraints
European Journal of Operational Research
(1999)
A branch-and-bound algorithm for solving a two-machine flow shop problem with deteriorating jobs
Computers and Operations Research
Cooperative metaheuristics for the permutation flowshop scheduling problem
European Journal of Operational Research
A note on the complexity of flow shop scheduling with transportation constraints
European Journal of Operational Research
An improved approximation algorithm for two-machine flow shop scheduling with an availability constraint
Information Processing Letters
A review of flowshop-scheduling research with set-up times
Production Operation Management
Minimizing the total weighted completion time in a two-machine proportionate flow shop with different machine speeds
International Journal of Production Research
Cited by (22)
An iterated greedy algorithm for distributed blocking flow shop with setup times and maintenance operations to minimize makespan
2022, Computers and Industrial EngineeringOptimizing distributed no-wait flow shop scheduling problem with setup times and maintenance operations via iterated greedy algorithm
2021, Journal of Manufacturing SystemsCitation Excerpt :The maintenance activity is scheduled inside to a given interval between [0, T]. Choi et al. [15] proved that the ordered m-machine permutation flow shop with maintenance operation greater than one is strongly NP-hard. The authors considered that jobs are resumable case and the maintenance operations are scheduled in advance.
Scheduling proportionate flow shops with preventive machine maintenance
2021, International Journal of Production EconomicsBi-objective optimization algorithms for joint production and maintenance scheduling under a global resource constraint: Application to the permutation flow shop problem
2020, Computers and Operations ResearchCitation Excerpt :Hadda et al. (2010) proposed an improved heuristic with a lower-bound analysis that was first introduced by Lee (1997). Choi et al. (2010) studied complexity properties of some special cases (ordered and proportionate flow shops) under a fixed unavailability constraint. Cui et al. (2016) studied the non-permutation flow shop with both a predefined maintenance plan and a flexible one and formulated both problems as mixed integer programs(MIP).
Integrating preventive maintenance activities to the no-wait flow shop scheduling problem with dependent-sequence setup times and makespan minimization
2019, Computers and Industrial EngineeringCitation Excerpt :Hadda (2015) extends the results found by Allaoui et al. (2008). Choi, Lee, Leung, and Pinedo (2010) consider the ordered flow shop where PM activities are scheduled in advance and jobs are resumable. Safari, Sadjadi, and Shahanaghi (2010) propose metaheuristics for the m-machine case under maintenance condition-based and non-resumable for makespan minimization.
Online scheduling of ordered flow shops
2019, European Journal of Operational ResearchCitation Excerpt :However, the machines may have different setup times. For other applications of ordered flow shops and proportionate flow shops with different speeds or different setup times, see Allahverdi and Savsar (2001); Estevez-Fernandez, Mosquera, Borm, and Hamers (2008) and Choi, Lee, Leung, and Pinedo (2010). This paper is organized as follows.
- 1
Work supported by the Korea Research Foundation Grant KRF-2008-357-D00289.
- 2
Work supported in part by the NSF Grant DMI-0556010.
- 3
Work supported in part by the NSF Grant DMI-0555999.