Single-machine scheduling with periodic maintenance to minimize makespan

https://doi.org/10.1016/j.cor.2005.05.034Get rights and content

Abstract

We consider a single-machine scheduling problem with periodic maintenance activities. Although the scheduling problem with maintenance has attracted researchers’ attention, most of past studies considered only one maintenance period. In this research several maintenance periods are considered where each maintenance activity is scheduled after a periodic time interval. The objective is to find a schedule that minimizes the makespan, subject to periodic maintenance and nonresumable jobs. We first prove that the worst-case ratio of the classical LPT algorithm is 2. Then we show that there is no polynomial time approximation algorithm with a worst-case ratio less than 2 unless P=NP, which implies that the LPT algorithm is the best possible.

Introduction

Most literature on scheduling theory assumes that machines are continuously available. However, this assumption may not be valid in a real production situation due to preventive maintenance (a deterministic event) or breakdown of machines (a stochastic phenomenon). It is not uncommon to observe in practice that machines are awaiting maintenance while there are jobs waiting to be processed by these machines. This is due to a lack of coordination between maintenance planning and production scheduling. Uncertain machine breakdowns will make the shop behavior hard to predict, thus reducing the efficiency of the production system. Maintenance can reduce the breakdown rate with minor sacrifices in production time. The importance of maintenance has increasingly been recognized by decision makers. Therefore, scheduling the maintenance of manufacturing systems has gradually become a common practice in many companies. The work of periodic maintenance includes periodic inspections, periodic repairs, and preventive maintenance. With proper planning of periodic maintenance, the shop can improve production efficiency and safety, resulting in increased productivity and heightened safety awareness [1].

As maintenance is scheduled periodically in many manufacturing systems, there is a need to develop an approach to handle the scheduling of jobs for processing in systems with periodic maintenance, which usually have more than one maintenance period. However, to the best of our knowledge, only Liao and Chen [2] have considered such a scheduling problem for the objective of minimizing the maximum tardiness. They proposed a branch-and-bound algorithm to derive the optimal schedule and a heuristic algorithm for large-sized problems. They also provided computational results to demonstrate the efficiency of their heuristic. In this paper we consider the scheduling problem with periodic maintenance to minimize the makespan.

Formally, the considered problem can be described as follows: We are given n independent non-resumable jobs J={J1,J2,,Jn}, which are processed on a single machine. Here nonresumable means that if a job cannot be finished before a maintenance activity, it has to restart. The processing time of job Ji is pi. All the jobs are available at time zero. The amount of time to perform each maintenance activity is t. Let the length of the time interval between two consecutive maintenance periods be T. We assume that Tpi for every i=1,2,,n, for otherwise there is trivially no feasible schedule. We think of each interval between two consecutive maintenance activities as a batch with a capacity T. Thus, a schedule π can be denoted as π=(B1,M1,B2,M2,,ML-1,BL), where Mi is the ith maintenance activity, L is the number of batches, and Bi is the ith batch of jobs. An illustration of the considered problem in the form of a Gantt chart is given in Fig. 1. Let Ci be the completion time of job Ji, then the objective is to minimize the makespan, which is defined as Cmax=maxi=1,2,,nCi. Using the three-field notation of Graham et al. [3], we denote this scheduling problem as 1/nr-pm/Cmax. It can easily be shown that this problem is strongly NP-hard [4], but no approximation algorithm has been provided and analyzed in the literature.

We use the worst-case ratio to measure the quality of an approximation algorithm. Specifically, for the makespan problem, let CA denote the makespan produced by an approximation algorithm A, and COPT the makespan produced by an optimal off-line algorithm. Then the worst-case ratio of algorithm A is defined as the smallest number c such that for any instance I, CAcCOPT.

The single-machine scheduling problem with single maintenance and nonresumable jobs has been well studied. For the objective of minimizing the makespan, Lee [4] showed that the longest processing time (LPT) rule has a tight worst-case ratio of 43, and He et al. [5] presented a fully polynomial time approximation scheme. For the objective of minimizing the total completion time, Lee and Liman [6] proved that the worst-case ratio of the shortest processing time (SPT) rule is 97. Sadfi et al. [7] proposed a modified algorithm MSPT with a worst-case ratio of 2017. He et al. [8] presented a polynomial time approximation scheme. Moreover, Lee [4] presented heuristics for other objectives, such as minimizing the maximum lateness, the number of tardy jobs, and the total weighted completion time, etc. Graves and Lee [9] extended the problem to consider semiresumable jobs. For details on related research, the reader may refer to the survey paper [10].

In this paper we first show that the worst-case ratio of the classical LPT algorithm is 2. Then we prove that there is no polynomial time approximation algorithm with a worst-case ratio of less than 2, which implies that LPT is the best possible algorithm. Finally, we present some concluding remarks.

Section snippets

The LPT algorithm and its worst-case ratio

In this section we analyze the LPT algorithm, which is a classical heuristic for solving scheduling problems. It can be formally described as follows.

Algorithm LPT. Re-order all the jobs such that p1p2pn; then process the jobs consecutively as early as possible.

Note that if we take each batch as a bin, then the LPT algorithm is equivalent to the first fit decreasing (FFD) algorithm, which is a classical heuristic for solving the bin-packing problem. The worst-case ratio for the FFD is 32

Non-approximability

It is well known that it is impossible to have a polynomial time approximation algorithm for the bin-packing problem with a worst-case ratio of less than 32 unless P=NP [13]. However, for our problem, the lower bound can be larger. In fact, we show that if there is an approximation algorithm with a worst-case ratio of 2-ε for any 0<ε<1, then it can be used to establish a polynomial time algorithm for solving the PARTITION problem, which is NP-hard [13], leading to a contradiction (if PNP).

Conclusions

We showed that the worst-case ratio of the classical LPT algorithm is 2 for the problem 1/nr-pm/Cmax. We also showed that 2 is the best possible for all the polynomial time approximation algorithms unless P=NP. So in future research, it is worth considering the design of approximation algorithms with a lower time complexity than the LPT algorithm, while maintaining the worst-case ratio of 2. It is also worth considering the problem with respect to other objectives and in parallel-machine

Acknowledgements

This research was supported in part by the National Natural Science Foundation of China under Grant Numbers (10271110, 60021201); the Teaching and Research Award Program for Outstanding Young Teachers in Higher Education Institutions of the MOE, China; and The Hong Kong Polytechnic University under Grant Number G-T997.

References (13)

There are more references available in the full text version of this article.

Cited by (160)

  • Scheduling with cardinality dependent unavailability periods

    2024, European Journal of Operational Research
View all citing articles on Scopus
View full text