# Single-Machine Scheduling with Workload-Dependent Maintenance Duration to Minimize Maximum Lateness

Authors: Ting Wang; Dehua Xu
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

A single-machine scheduling problem with a mandatory maintenance whose duration is workload-dependent is considered. The start time of the maintenance is restricted to a time window. The objective is to determine the start time of the maintenance and schedule all the jobs to the machine such that the maximum lateness is minimized. An approximation algorithm based on the classical Earliest Due Date first rule is proposed. It is showed that the proposed algorithm is optimal for some special cases and that it has a tight bound for the scheduling problem under consideration.


---

## Body

## 1. Introduction

Scheduling with due-date related criteria is an important issue in operations management. As is usually the case, if a job cannot be finished before the promised due date, there is a penalty for the producer. When this is the case, the credit standing of the producer also decreases at the same time. As a result, some costumers may turn to another producer in the future. Assume that there is a lateness tolerance for all the costumers. In order to avoid losing too many costumers, minimizingmaximum lateness, which measures the worst violation of the due dates, is usually selected as the objective in production scheduling.To the best of our knowledge, Jackson [1] is the first researcher that considers the maximum lateness objective in the field of scheduling. He shows that the Earliest Due Date first rule, which sequences the jobs in nondecreasing order of their due dates, is optimal for the maximum lateness objective in classical single-machine setting. Since then, numerous works have been done on the same objective for various machine settings and job parameters. For related papers published in recent years, see, for example, [2–7].Note that a machine may be unavailable sometimes in reality due to various reasons such as refueling, tool changing, and regular check. Taking this factor into consideration, one has to make a coordination between job processing and machine maintenance. In this paper, instead of taking the duration of a maintenance as a constant [8–12] or as a function of its start time [13–15], we assume that the duration of the maintenance is an nonnegative increasing function of its workload before the maintenance [16]. This maintenance duration model is more practical than the start time related model for the fact that the machine may not be always busy before the maintenance in some scenarios. In order to be more realistic, we further assume that the maintenance must be started within a time window.Formally, the problem under consideration can be described as follows. There aren independent nonpreemptive jobs J1,J2,…,Jn to be scheduled on a single-machine with a mandatory maintenance. All jobs are available at time zero. The processing time and due-date of job Jj are pj and dj, respectively, where j=1,2,…,n. The duration of the maintenance is a nonnegative increasing function f of the workload that is scheduled to be carried by the machine before the maintenance, which must be started within time window [u,v], where 0≤u≤v. The lateness of a job in a schedule is defined as its completion time in the schedule minus its due-date. The objective of the problem is to determine the start time of the maintenance and schedule all the jobs to the machine such that the maximum lateness is minimized.The rest of this paper is organized as follows. In the next section, we show that the problem under consideration is NP-hard. Then, in Section3, we propose an approximation algorithm with a worst-case analysis. Finally, in Section 4, we conclude the paper.


## 2. Computational Complexity

It is well-known that corresponding classical version of our problem, that is,1∥Lmax, can be solved optimally in polynomial time by the Earliest Due Date first rule [17]. However, as can be seen later, our problem is NP-hard.Theorem 1.
The scheduling problem under consideration is NP-hard.Proof.
Consider the restricted version of our scheduling problem wheref is a constant function greater than zero, u=v>0, and dj=0 for every j∈{1,2,…,n}. It is easy to see that the decision version of the restricted version of our scheduling problem is in NP. Note that the Partition Problem [17, 18] which is NP-complete is reducible to the decision version of the restricted version of our scheduling problem. Hence, the decision version of the restricted version of our scheduling problem is also NP-complete. This implies that the restricted version of our scheduling problem is NP-hard. And thus, our scheduling problem (i.e., the nonrestricted version) is NP-hard.


## 3. An Approximation Algorithm and Its Worst-Case Analysis

Note that the scheduling problem under consideration is NP-hard. So, there does not exist any polynomial time optimal algorithm for it unless P = NP. In what follows, we will present an approximation algorithm named EDDMW (Earliest Due Date first with Maximum Workload before the maintenance) based on the classical Earliest Due Date first rule. The underlying idea of the algorithm is to sort all the jobs according to nondecreasing order of their due dates first and then process as many jobs in this order as possible before maintenance.Algorithm EDDMW. Consider the following.Step 1.
Sort all the jobs such thatdj1≤dj2≤⋯≤djn, where (j1,j2,…,jn) is a permutation of (1,2,…,n).Step 2.
Letn′=max{k∣∑i=1k‍pji≤v and k≤n} and λ⋄=∑i=1n′‍pji.Step 3.
Ifn′≥1, then process the first n′ jobs in the sorted order consecutively from time zero. If λ⋄<u, then keep the machine idle for a time of u-λ⋄. Conduct the maintenance from time max{u,λ⋄} for a duration of f(λ⋄). If n′<n, then process the rest of the jobs in the sorted order consecutively from time max{u,λ⋄}+f(λ⋄).Note that Step1 takes O(nlogn) time while Step 2 takes O(n) time. Assume that the duration function f(x) is given by an oracle which for any given x returns f(x). Then, Step 3 also takes O(n) time. And hence, the running time of the algorithm EDDMW is O(nlogn).The following notations will be used throughout this paper:S⋄: the schedule produced by algorithm EDDMW for the scheduling problem under consideration;λ⋄: the workload (i.e., the total processing time of the jobs scheduled to be processed) before the maintenance in S⋄;Lj⋄: the lateness of job Jj in schedule S⋄;Lmax⋄: the maximum lateness of the jobs in schedule S⋄; that is, Lmax⋄=maxi=1,2,…,n⁡{Lji⋄};S∗: an optimal schedule for the scheduling problem under consideration;λ∗: the workload before the maintenance in S∗;Lj∗: the lateness of job Jj in schedule S∗;Lmax∗: the maximum lateness of the jobs in schedule S∗; that is, Lmax∗=maxj=1,2,…,n⁡{Lj∗};Jji⋄: the first job that achieves the maximum lateness in S⋄; that is, i⋄=min{k∣Ljk⋄=maxi=1,2,…,n⁡{Lji⋄}};Jjl: the last finished job among the jobs Jj1,…,Jji⋄ in S∗.Theorem 2.
Ifn′=n, then S⋄ is optimal.Proof.
Ifn′=n, then all the jobs are scheduled to be processed before the maintenance in nondecreasing order of their due date in S⋄, which means that our problem reduces to its classical version without maintenance. Note that Earliest Due Date first rule is optimal for the latter [17]. Therefore, S⋄ is optimal.Theorem 3.
If jobJji⋄ is scheduled to be processed before the maintenance in S⋄, then S⋄ is optimal.Proof.
It is easy to see that(1)Lmax⋄=Lji⋄⋄=∑i=1i⋄‍pji-dji⋄.
Now, consider the following two cases.
Case
1. Jjl is scheduled to be processedbefore the maintenance in S∗.
It is easy to see that(2)Lmax∗≥Ljl∗≥∑i=1i⋄‍pji-djl.Note that djl≤dji⋄. So we have (3)Lmax∗≥Ljl∗≥∑i=1i⋄‍pji-dji⋄.Combining this with (1), we have (4)Lmax∗≥Lmax⋄,which implies that S⋄ is also optimal.
Case
2. Jjl is scheduled to be processedafter the maintenance in S∗.
It is easy to see that(5)Lmax∗≥Ljl∗≥∑i=1i⋄‍pji+fλ∗-djl.Note that f is nonnegative and that djl≤dji⋄. So we have (6)Lmax∗≥Ljl∗≥∑i=1i⋄‍pji-dji⋄.Combining this with (1), we have (7)Lmax∗≥Lmax⋄,which implies that S⋄ is also optimal.
This completes the proof.Now, letg(x)=f(x)-x, gmax=max{g(x)∣0≤x≤u}, and gmin=min{g(x)∣0≤x≤u}.Theorem 4.
If jobJji⋄ is scheduled to be processed after the maintenance in S⋄, then (8)Lmax⋄≤Lmax∗+gmax-gminifλ⋄≤u,λ∗≤ugmax-guifλ⋄≤u,λ∗>ufv-u-gminifλ⋄>u,λ∗≤ufv-fuifλ⋄>u,λ∗>uand each of the bounds is tight.Proof.
We declare that jobJjl cannot be scheduled to be processedbefore the maintenance in S∗. To see this is the case, if Jjl is scheduled to be processedbefore the maintenance in S∗, then by the definition of Jjl, jobs Jj1,…,Jji⋄ must be scheduled to be processed before the maintenance too, which clearly contradicts the assumption of the theorem. So, in what follows, we assume that job Jjl is scheduled to be processedafter the maintenance in S∗.
Now, consider the following four cases.
Case
1. λ⋄≤u and λ∗≤u. It is easy to see that (9)Lmax⋄=Lji⋄⋄=∑i=1i⋄‍pji+u-λ⋄+fλ⋄-dji⋄,and that(10)Lmax∗≥Ljl∗=∑i=1i⋄‍pji+u-λ∗+fλ∗-djl.Combining (9) and (10) with the definitions of gmax and gmin, respectively, we have (11)Lmax⋄=Lji⋄⋄≤∑i=1i⋄‍pji+u+gmax-dji⋄,and that (12)Lmax∗≥Ljl∗≥∑i=1i⋄‍pji+u+gmin-djl.Recall that djl≤dji⋄. Combining this with (12), we have (13)Lmax∗≥Ljl∗≥∑i=1i⋄‍pji+u+gmin-dji⋄.Combining (13) with (11), we have (14)Lmax⋄≤Lmax∗+gmax-gmin.
To see that this bound is tight, consider the following instance.
Instance 1. Consider n=3, p1=u/2-ϵ, p2=u/2, p3=v-u+2ϵ, d1=u/3, d2=u/2, d3=u, f(x)=2x+ϵ, and v=2u, where ϵ≤u/4.
It can be checked that for this instanceLmax⋄=L3⋄=3u+ϵ while Lmax∗=L3∗=2u+2ϵ (see Figure 1). Note that for this instance g(x)=f(x)-x=x, gmax=u, and gmin=0. So we have Lmax⋄→Lmax∗+gmax-gmin as ϵ→0 for Instance 1.
Case
2. λ⋄≤u and λ∗>u. It is easy to see that in this case we have (11) and (15)Lmax∗≥Ljl∗=∑i=1i⋄‍pji+fλ∗-djl.Recall that djl≤dji⋄. Combining this with (15), we have (16)Lmax∗≥Ljl∗=∑i=1i⋄‍pji+fλ∗-dji⋄.Note that λ∗>u and that f is increasing. So we have (17)Lmax∗≥Ljl∗≥∑i=1i⋄‍pji+fu-dji⋄.Combining this with (11), we have (18)Lmax⋄≤Lmax∗+u+gmax-fu.Note that g(x)=f(x)-x. So we have (19)Lmax⋄≤Lmax∗+gmax-gu.
To see that this bound is tight, consider the following instance.
Instance 2. Consider n=2, p1=ϵ, p2=u, d2=d1+ϵ/2, f(x)=x/2, and v=u, where ϵ≤u/4.
It can be checked that for this instanceLmax⋄=L2⋄=2u-d1 while Lmax∗=L1∗=3u/2+ϵ-d1 (see Figure 2). Note that for this instance g(x)=f(x)-x=-x/2, gmax=0, and g(u)=-u/2. So we have Lmax⋄→Lmax∗+gmax-g(u) as ϵ→0 for Instance 2.
Case
3. λ⋄>u and λ∗≤u. It is easy to see that in this case we have (13) and (20)Lmax⋄=Lji⋄⋄=∑i=1i⋄‍pji+fλ⋄-dji⋄.Note that λ⋄≤v. So, by (20), we have (21)Lmax⋄=Lji⋄⋄≤∑i=1i⋄‍pji+fv-dji⋄.Combining this with (13), we have (22)Lmax⋄≤Lmax∗+fv-u-gmin.
To see that this bound is tight, consider the following instance.
Instance 3. Consider n=2, p1=v, p2=ϵ, d2=d1+ϵ/2, f(x)=2x+ϵ, and v=u, where ϵ≤u/4.
It can be checked that for this instanceLmax⋄=L2⋄=3u+3ϵ/2-d1 while Lmax∗=L2∗=2u+3ϵ/2-d1 (see Figure 3). Note that for this instance g(x)=f(x)-x=x+ϵ, gmin=ϵ, and f(v)=2u+ϵ. So we have Lmax⋄→Lmax∗+f(v)-u-gmin as ϵ→0 for Instance 3.
Case
4. λ⋄>u and λ∗>u. Consider the following.
It is easy to see that in this case we have (16) and (21). And hence, (23)Lmax⋄≤Lmax∗+fv-fu.
To see that this bound is tight, consider the following instance.
Instance 4. Consider n=2, p1=v, p2=u, d2=d1+ϵ, and f(x)=x/2, where ϵ≤u/4.
It can be checked that for this instanceLmax⋄=L2⋄=u+3v/2-ϵ-d1 while Lmax∗=L1∗=3u/2+v-d1 (see Figure 4). Note that for this instance f(u)=u/2 and f(v)=v/2. So we have Lmax⋄→Lmax∗+f(v)-f(u) as ϵ→0 for Instance 4.
This completes the proof.Figure 1
Schedules for Instance 1.Figure 2
Schedules for Instance 2.Figure 3
Schedules for Instance 3.Figure 4
Schedules for Instance 4.Theorem 5.
(24)
L
m
a
x
⋄
≤
L
m
a
x
∗
+
m
a
x
⁡
g
m
a
x
-
g
m
i
n
,
g
m
a
x
-
g
u
,
m
m
m
m
m
m
m
m
f
v
-
u
-
g
m
i
n
,
f
v
-
f
uand the bound is tight.Proof.
If jobJji⋄ is scheduled to be processed before the maintenance in S⋄, then by Theorem 2, we know that S⋄ is optimal, which implies that (24) is true.
If jobJji⋄ is scheduled to be processed after the maintenance in S⋄, then according to Theorem 4, we have (8), which implies that we also have (24).
To see that this bound is tight, consider Instance 3 that is presented in the proof of Theorem4 again. It can be checked that for this instance gmax-gmin=u, gmax-g(u)=0, f(v)-u-gmin=u, and f(v)-f(u)=0. And hence, for this instance, we have max{gmax-gmin,gmax-g(u),f(v)-u-gmin,f(v)-f(u)}=f(v)-u-gmin.
Recall that, for the same instance, we haveLmax⋄→Lmax∗+f(v)-u-gmin as ϵ→0 according to the argument on Instance 3 in the proof of Theorem 4. Therefore, for the same instance, we have Lmax⋄→Lmax∗+max{gmax-gmin,gmax-g(u),f(v)-u-gmin,f(v)-f(u)} as ϵ→0.
This completes the proof.


## 4. Conclusions

In this paper, we considered a maximum lateness minimization scheduling problem on a single-machine with a mandatory maintenance whose duration is workload-dependent. The start time of the maintenance is restricted to a given time window. We showed that the problem is NP-hard and proposed an approximation algorithm for it.Further research may focus on designing some sophisticated approximation algorithms with lower absolute bounds. It is also interesting to study such a maintenance model in some other machine settings, such as parallel machine, flow shop, and job shop.



---

*Source: 732437-2015-07-28.xml*