|
Article Excerpt
We consider the two-machine open shop and two-machine flow shop scheduling problems in which each machine has to be maintained exactly once during the planning period, and the duration of each of these intervals depends on its start time. The objective is to minimize the maximum completion time of all activities to be scheduled. We resolve complexity and approximability issues of these problems. The open shop problem is shown to be polynomially solvable for quite general functions defining the length of the maintenance intervals. By contrast, the flow shop problem is proved binary NP-hard and pseudopolynomially solvable by dynamic programming. We also present a fully polynomial approximation scheme and a fast 3/2-approximation algorithm.
Subject classifications: production/scheduling: approximations/heuristic; multiple machine; inventory/production: maintenance/replacement.
Area of review: Optimization.
1. Introduction
The main trend in the development of deterministic scheduling theory has always been that of increasing the complexity and practical relevance of the models. The so-called classical models are too ideal to handle various restrictions that may occur in practical scheduling; thus, their extensions that involve additional constraints (precedence, resource, transportation, etc.) are of permanent strong interest.
One of the extensions of standard scheduling models is related to the so-called machine nonavailability intervals and has received considerable attention since the beginning of the 1990s. In these models, a processing machine is not necessarily continuously available throughout the planning period. However, most prior research has concentrated on one type of nonavailability interval, namely, a pure deterministic situation when the start of an interval and its duration are known in advance; see the survey papers by Schmidt (2000) and Lee (2004). We refer to nonavailability intervals of this type as fixed. They can serve as modeling tools for planned breaks (lunch breaks, days off, holidays, etc.); however, they are not suitable for handling other types of breaks, such as periods of equipment breakdown or machine maintenance.
In equipment breakdown modeling, the decision maker is not aware when a breakdown occurs and for how long, so that the online rescheduling decisions have to be made. This direction of research is closely related to the area of disruption management and, despite its importance, so far has not been systematically studied.
Planning the intervals of preventive equipment maintenance gives the decision maker freedom to choose the start time for that maintenance; additionally, the length of the maintenance period may depend on its start time (the sooner the maintenance is started, the better the equipment conditions are, and the less time is needed for its maintenance). This calls for study of scheduling models with floating nonavailability intervals of controllable durations. This paper falls into that category.
The importance of preventive maintenance for production enterprises and service organizations has been widely recognized by both practitioners and management scientists; see, e.g., the paper by Gopalakrishnan et al. (1997), the Internet emporium at www.plant-maintenance.com, and the popular books by Nyman and Levitt (2002) and Palmer (1999).
In the scheduling literature there is a stream of papers dealing with finding a periodic schedule for fixed-length maintenance periods. Each machine incurs an operation cost that depends on the time of the last maintenance of the machine. The problem of scheduling maintenance intervals to reduce the average long-term cost of running the system is considered by Anily et al. (1998, 1999). An extended version of the problem with additional fixed maintenance cost involved is considered by Bar-Noy et al. (2002) and Grigoriev et al. (2006).
In another model there is an upper bound on how long a processing machine may work without maintenance. Qi et al. (1999) consider the problem of scheduling jobs and maintenance intervals of equal duration on a single machine to minimize various objective functions.
Graves and Lee (1999) consider the problem of scheduling jobs and two maintenance intervals of a fixed duration on a single machine to minimize either the total weighted completion time or the maximum lateness. If the processing of a job is interrupted because of the machine maintenance, the job requires some additional setup time to resume. Lee and Chen (2000) study the problem in which each parallel machine has to be maintained once during the planning period. The jobs are not allowed to be interrupted by machine maintenance. The goal is to minimize the total weighted completion times of the jobs. There are two different variations of the problem: (i) only one machine can be maintained at any time, and (ii) several machines can be maintained simultaneously.
The goal of this paper is to initiate research on scheduling models with maintenance periods of controllable length. In many manufacturing environments the length of machine maintenance depends on its start time. This happens when maintenance includes cleaning, recharging, refilling, or partial replacement of tools or parts that have been subject to essential wear. On the other hand, a maintenance period includes a series of standard tests that require a constant time that does not depend on the start time. Thus, in this paper we assume that the length of a maintenance period on a machine is of the form [alpha] + f(t), where t is the start time, [alpha] is a given positive constant (the duration of the standard tests), and f(t) is a given monotone non-decreasing function (the duration of maintenance activities that depend on the state of the equipment).
Unlike in the quoted papers on scheduling with maintenance, in this paper we turn to multistage scheduling systems, the flow shop and the open shop, in which the processing of a job requires several operations to be performed consecutively.
Recall that the open shop and the flow shop are classical scheduling processing systems. In the two-machine flow shop scheduling problem, we are given a set of n jobs and two machines, A and B. Each job has to be processed on machine A and then on machine B. We refer to the processing of a job on a machine as an operation. The processing times of all operations are known. It is assumed that every job is processed on at most one machine at a time, and each machine processes no more than one job at a time. In the open shop, the processing route of each job is not known in advance, i.e., the decision maker may assign some jobs to be processed on A and then on B, and schedule the other jobs to pass the machines in the opposite order.
In this paper, we study these two basic two-machine models and concentrate on the case that each machine has to be maintained once during the planning period, and the objective is to minimize the makespan. Unlike the classical scheduling models, here we define the makespan not as the completion time of the last job, but as the maximum completion time of all activities to be scheduled, including the maintenance periods. This modified definition of the makespan is due to the fact that the maintenance periods are mandatory, and the decision maker has to schedule them along with the jobs to be processed.
Our study is relevant not only to the scheduling models with fixed machine nonavailability intervals as discussed above, but also to the models with variable (or time-dependent) processing times. In the latter type of models, the durations of operations are not constants, but depend on the start time and are represented by functions similar to [alpha] + f(t). The case of nondecreasing functions f(t) has received special attention; the jobs of this type are normally called deteriorating. See a recent survey by Cheng et al. (2004) for a literature review on scheduling with variable processing times.
The models we consider can be given an additional meaningful interpretation in terms of multiagent scheduling recently studied by Agnetis et al. (2004). We may assume that the jobs belong to one agent and treat the maintenance periods as operations that belong to the second agent. The goal is to minimize the completion time of all jobs on all machines, provided that the processing times of the operations owned by the second agent are time dependent.
The remainder of this paper is organized as follows. Section 2 gives a formal description of the problem and its relations with other results from scheduling theory. In [section]3, we demonstrate that the two-machine open shop problem with one maintenance interval on each machine is poly-nomially solvable for quite general functions defining the length of these intervals. By contrast, the flow shop counterpart studied in [section]4 is proved binary NP-hard even if the length of the maintenance interval depends linearly on its starting time. We also give a pseudopolynomial dynamic programming algorithm and two approximation algorithms, including a fully polynomial approximation scheme. The obtained results resolve the issues of complexity and approximation for the problems under consideration. Section 5 contains concluding remarks.
2. Preliminaries
We start with the classical flow shop and open shop models, in which the two machines are continuously available throughout the planning period.
In a two-machine shop scheduling problem, we are given a set N = {1, 2,..., n} of jobs. Each job consists of two operations, [O.sub.jA] and [O.sub.jB], to be performed on machines A and B, respectively. We denote the processing time of operations [O.sub.jA] and [O.sub.jB] by [a.sub.j] and [b.sub.j], respectively.
For a nonempty set...
|
