Elsevier

Computers & Operations Research

Volume 36, Issue 9, September 2009, Pages 2541-2545
Computers & Operations Research

Scheduling a maintenance activity and due-window assignment on a single machine

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

Abstract

We study a single machine scheduling and due-window assignment problem. In addition to the traditional decisions regarding sequencing the jobs and scheduling the due-window, we allow an option for performing a maintenance activity. This activity requires a fixed time interval during which the machine is turned off and no production is performed. On the other hand, after the maintenance time, the machine becomes more efficient, as reflected in the new shortened job processing times. The objective is to schedule the jobs, the due-window and the maintenance activity, so as to minimize the total cost consisting of earliness, tardiness, and due-window starting time and size. We introduce an efficient (polynomial time) solution for this problem.

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 λjPj(0<λj1) if it is scheduled after it, j=1,…,n. λj 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 O(nlogn), while the complexity of the solution procedure in Case 3 is O(n4).

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 λjPj.

A numerical example

A solution of an 8-job problem is demonstrated in the following. The job processing times and the modifying rates are: P1=15, P2=9, P3=26, P4=104, P5=10, P6=2, P7=25, P8=82 and λ1=0.6, λ2=0.42, λ3=0.16, λ4=0.39, λ5=0.7, λ6=0.36, λ7=0.51, λ8=0.11. The cost parameters are: α=2, β=25, γ=15 and δ=15.6. The duration of the maintenance activity is t=75.

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)

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

Cited by (76)

  • A survey on scheduling problems with due windows

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