Scheduling a maintenance activity and due-window assignment on a single machine
Introduction
Liman et al. [1] considered the following scheduling and due-window assignment problem: n jobs need to be processed on a single machine around a common due-window; jobs completed within the due-window are considered as on-time jobs, whereas early and tardy jobs are penalized. There are four cost components: for earliness, tardiness, due-window starting time and due-window size. The objective is to schedule all jobs and to determine the due-window size and location such that the total cost is minimized. Liman et al. introduced an O(n log n) solution for this problem.
In this note we extend the above model to include an additional (optional) maintenance activity. This activity requires a fixed time interval during which the machine is turned off and production is stopped. On the other hand, after the maintenance time, the machine becomes more efficient, as reflected in the new shortened job processing times. Thus, in addition to the traditional job scheduling and due-window assignment decisions, our objective includes a decision regarding the time for scheduling the maintenance activity.
Scheduling a maintenance activity became a popular topic among researchers in the last decade. Among the recent papers, Ji et al. [2] studied a model of scheduling a periodic maintenance on a single machine, and Yang et al. [3] focused on a separated maintenance activity in flow-shops. Lee and Leon [4] introduced the basic scheduling model with a maintenance activity that improves the machine's efficiency (a rate-modifying activity). They studied several classic measures such as makespan, flow-time, weighted flow-time and maximum tardiness. Mosheiov and Oron [5] studied the same setting with a due-date assignment problem. Most other references considered either (i) a given fixed period of maintenance (i.e. a setting of non-availability time constraints—see e.g. Lee [6]), or (ii) a situation where the time of the maintenance activity is determined by the scheduler, but must be completed within a time interval and does not affect the machine efficiency (see e.g. Lee and Chen [7] and Kubzin and Strusevich [8]). Our problem includes scheduling decisions regarding (i) the jobs, (ii) the due-window, and (iii) the maintenance activity. We introduce a polynomial time solution requiring O(n4) time (where n is the number of jobs).
In the second section we provide the notation and the formulation of the problem. The third section contains the important properties of an optimal schedule. The (polynomial time) solution method is presented in Section 4, followed by a detailed numerical example given in the fifth section. Conclusion and ideas for future research are discussed in the last section.
Section snippets
Formulation
We study a non-preemptive, n-job, single-machine setting. The scheduler has an option to schedule a maintenance activity which lasts t units of time. During the maintenance no production is performed. The processing time of job j is denoted by Pj if the job is processed prior to the maintenance activity, and if it is scheduled after it, j=1,…,n. is the modifying rate of job j. For a given job sequence, the processing time of the job in the j-th position, and the modifying rate
Properties of an optimal schedule
We begin by introducing several properties of an optimal solution. One trivial property is that an optimal schedule starts at time zero and contains no idle time between consecutive jobs. Another trivial property is that an optimal schedule exists in which the maintenance activity is performed prior to the starting time of one of the jobs. (Otherwise, if the maintenance starts Δ units of time after the starting time of, say, job k, performing the maintenance activity Δ time units earlier does
A polynomial time solution
In this section we analyze separately the solution procedures for each of the three cases specified in Lemma 4. We show that the running time for the procedures in Cases 1 and 2 is , while the complexity of the solution procedure in Case 3 is .
Case 1 (The maintenance activity starts at time zero). Note that this case is a special case of Liman et al. [1], where the sequence starts at time t (at the completion time of the maintenance activity), and the job processing times are .
A numerical example
A solution of an 8-job problem is demonstrated in the following. The job processing times and the modifying rates are: , , , , , , , and , , , , , , , . The cost parameters are: , , and . The duration of the maintenance activity is .
We solve each case separately:
Case 1 (The maintenance activity starts at time zero). α(j−1)+γn=(120,122,124,126,128,130,132,134).
δn=(124.8, 124.8,
Conclusion
The option for performing a maintenance activity in scheduling problems has been studied by several researchers in recent years. We focus on a due-window assignment on a single machine, in which the objective is to minimize the costs of earliness, tardiness, due-window starting time, and due-window size. This classical problem is known to be solved in O(n log n) time. We extend this setting to allow a maintenance activity, after which the machine becomes more efficient. We introduce an O(n4)
Acknowledgement
This paper was supported in part by The Recanati Fund of The School of Business Administration, The Hebrew University, Jerusalem, Israel.
References (8)
- et al.
Single machine scheduling with periodic maintenance to minimize makespan
Computers & Operations Research
(2007) - et al.
A two machine flowshop scheduling problem with a separated maintenance constraint
Computers & Operations Research
(2008) - et al.
Machine scheduling with a rate modifying activity
European Journal of Operational Research
(2001) - et al.
Due-date assignment and maintenance activity scheduling problem
Mathematical and Computer Modeling
(2006)
Cited by (76)
Structural properties and algorithms for earliness and tardiness scheduling against common due dates and windows: A review
2020, Computers and Industrial EngineeringComparison of new metaheuristics, for the solution of an integrated jobs-maintenance scheduling problem
2019, Expert Systems with ApplicationsA hybrid genetic algorithm with two-stage dispatching heuristic for a machine scheduling problem with step-deteriorating jobs and rate-modifying activities
2016, Computers and Industrial EngineeringMinimizing tardiness and maintenance costs in flow shop scheduling by a lower-bound-based GA
2016, Computers and Industrial EngineeringA survey on scheduling problems with due windows
2015, European Journal of Operational ResearchGROUP DECISION MAKING APPROACH FOR RANKING AND SELECTING MAINTENANCE TASKS FOR JOINT SCHEDULING WITH PRODUCTION ORDERS
2024, International Journal for Quality Research