Single-machine scheduling with periodic maintenance to minimize makespan
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 independent non-resumable jobs , 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 is . All the jobs are available at time zero. The amount of time to perform each maintenance activity is . Let the length of the time interval between two consecutive maintenance periods be . We assume that for every , for otherwise there is trivially no feasible schedule. We think of each interval between two consecutive maintenance activities as a batch with a capacity . Thus, a schedule can be denoted as , where is the ith maintenance activity, is the number of batches, and is the th batch of jobs. An illustration of the considered problem in the form of a Gantt chart is given in Fig. 1. Let be the completion time of job , then the objective is to minimize the makespan, which is defined as . Using the three-field notation of Graham et al. [3], we denote this scheduling problem as . 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 denote the makespan produced by an approximation algorithm , and the makespan produced by an optimal off-line algorithm. Then the worst-case ratio of algorithm is defined as the smallest number such that for any instance , .
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 , 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 . Sadfi et al. [7] proposed a modified algorithm MSPT with a worst-case ratio of . 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 ; 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
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 unless [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 for any , 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 ).
Conclusions
We showed that the worst-case ratio of the classical LPT algorithm is 2 for the problem . We also showed that 2 is the best possible for all the polynomial time approximation algorithms unless . 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)
- et al.
Single-machine scheduling with periodic maintenance and nonresumable jobs
Computers and Operations Research
(2003) - et al.
Optimization and approximation in deterministic sequencing and scheduling: a survey
Annals of Operations Research
(1979) - et al.
An improved approximation algorithm for the single machine total completion time scheduling problem with availability constraints
European Journal of Operational Research
(2005) Scheduling with limited machine availability
European Journal of Operational Research
(2000)- et al.
Some aspects of measuring maintenance in the process industry
Journal of Quality in Maintenance Engineering
(1998) Machine scheduling with an availability constraint
Journal of Global Optimization
(1996)
Cited by (160)
Scheduling with cardinality dependent unavailability periods
2024, European Journal of Operational ResearchRobust job-sequencing with an uncertain flexible maintenance activity
2023, Computers and Industrial EngineeringConstructive and composite heuristics for the 2-stage assembly scheduling problem with periodic maintenance and makespan objective
2022, Expert Systems with ApplicationsChance constrained dynamic optimization approach for single machine scheduling involving flexible maintenance, production, and uncertainty
2022, Engineering Applications of Artificial IntelligenceMinimizing total absolute deviation of job completion times on a single machine with maintenance activities using a Lion Optimization Algorithm
2022, Sustainable Operations and ComputersRobust and resilient joint periodic maintenance planning and scheduling in a multi-factory network under uncertainty: A case study
2022, Reliability Engineering and System Safety