Flow shops with machine maintenance: Ordered and proportionate cases

Abstract

We consider the m-machine ordered flow shop scheduling problem with machines subject to maintenance and with the makespan as objective. It is assumed that the maintenances are scheduled in advance and that the jobs are resumable. We consider permutation schedules and show that the problem is strongly NP-hard; it remains NP-hard in the ordinary sense even in the case of a single maintenance. We show that if the first (last) machine is the slowest and if maintenances occur only on the first (last) machine, then sequencing the jobs in the LPT (SPT) order yields an optimal schedule for the m-machine problem. As a special case of the ordered flow shop, we focus on the proportionate flow shop where the processing times of any given job on all the machines are identical. We prove that the proportionate flow shop problem with two maintenance periods is NP-hard, while the problem with a single maintenance period can be solved in polynomial time. Furthermore, we show that the optimal algorithm for the single maintenance case is a $\frac{3}{2}$-approximation algorithm for the two maintenance case. In our conclusion we discuss also the computational complexity of other objective functions.

Introduction

We consider the m-machine, n-job flow shop problem with the machines subject to maintenance. Let p_ij 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 C_max, 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, p_hj < p_hk, then p_ij ⩽ p_ik for i = 1, … , m.

• If, for some 1 ⩽ k ⩽ n, p_ik < p_hk, then p_ij ⩽ p_hj 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 p_j, i.e., p_ij = p_j, 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 p_ij refer to the processing requirement of job j on machine i. Let C_i,j and B_i,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 C_max(σ) denote the makespan of σ. Let M_i,k ≡ [s_i,k, f_i,k] be the kth maintenance which has been scheduled to start at time s_i,k and finish at time f_i,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:

• The jobs are sorted in non-decreasing order of their processing times, i.e. p_i,1 ⩽ p_i,2 ⩽ ⋯ ⩽ p_i,n, i = 1, 2, … , m.

• The machine is resumable, i.e., a job interrupted by maintenance can be continued after completion of the maintenance without any additional processing.

• 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.