# Minimizing the Makespan for Scheduling Problems with General Deterioration Effects

Authors: Xianyu Yu; Yulin Zhang; Kai Huang
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

This paper investigates the scheduling problems with general deterioration models. By the deterioration models, the actual processing time functions of jobs depend not only on the scheduled position in the job sequence but also on the total weighted normal processing times of the jobs already processed. In this paper, the objective is to minimize the makespan. For the single-machine scheduling problems with general deterioration effects, we show that the considered problems are polynomially solvable. For the flow shop scheduling problems with general deterioration effects, we also show that the problems can be optimally solved in polynomial time under the proposed conditions.


---

## Body

## 1. Introduction

In the last decade, there is a growing interest in the literatures to study the scheduling problems where the actual processing time of a job may be subject to change due to various possible changes of its starting time and/or its position in the scheduling sequence. In general, there are two main types of effects on actual processing time of jobs in the scheduling literature: position-based effect and sum-of-processing-time-based effect.Many studies modeled the actual processing times of jobs as specific exponential functions of the scheduled positions of jobs. Biskup [1] considered a scheduling problem with an exponential model of position-dependent effect where the actual processing time of job Ji is
(1)pir=pira
if job Ji is scheduled in position r of the job sequence, where pi and a (a<0) are the normal processing time and the learning rate of job Ji, respectively. The model in Biskup [1] was extended to be
(2)pir=pirai,
where the learning rates of the jobs are different; that is, the learning effects are job dependent in Mosheiov and Sidney [2]. Some recent studies (see, e.g., Kuo and Yang [3], Cheng et al. [4], Chang et al. [5], Yang et al. [6], and Browne and Yechiali [7]) have investigated this issue with exponential processing time models under different machine environments. Some other studies proposed different versions of linear processing time models of jobs. Zhao and Tang [8] considered a linear deterioration model in which the actual processing time of job Jj is
(3)pjA=pj+ajt,
where pj, aj, and t are the normal processing time, deterioration rate, and starting time of job Ji, respectively. Cheng and Wang [9] introduced an actual processing time model of Ji as follows:
(4)pj=ai-vimin{ni,n0i},i=1,2,…,n,
where pj and vi are the normal processing time of job Ji and the learning effect coefficient indicating the relative degree of learning, respectively. The notation ni is a nonnegative integer such that 0≤ni≤n-1 which indicates the number of jobs processed before job Ji in the schedule (i.e., ni+1 is the position of job Ji in the schedule), and the notation n0i is a nonnegative integer such that n0i≤n-1 indicating a threshold value. The scheduling problems with linear actual processing times of jobs were considered in many recent articles, which include Mosheiov [10], Bachman and Janiak [11], Li et al. [12], Cheng et al. [13], and Yin et al. [14].In the last decade, many researchers have devoted themselves to address different combinations of nonlinear models and linear models for actual processing times of jobs in scheduling studies. Alidaee and Womer [15] proposed a simple processing time model of job Jj as follows:
(5)pjr(t)=pj+αta,
where a>0 and α>0 are both parameters of the nonlinear deterioration effect. Lee et al. [16] considered the bicriterion single-machine scheduling problem with two job processing time models as follows:
(6)pjr(t)=αjtra,pjr(t)=(p0+αjt)ra,
where αj and t are the deterioration rate of job Jj and the starting time of job Jj, respectively.Several researchers addressed the combined effect of position-based effect and sum-of-processing-time-based effect into various scheduling problems. S.-J. Yang and D.-L. Yang [17] proposed a model in which the actual processing time of job Jj scheduled in position r of a sequence is
(7)pir=pi(1+∑k=1r-1‍p[k]∑k=1n‍pk)a1ra2,
where a1<0 and a2<0 denote the learning rates for sum-of-processing-times-based and position-based learning, respectively. In the model, the subscript [k] denotes the job in position k of a sequence, and p[i] denotes the normal processing time of job i. Yin et al. [18] extended the model in S.-J. Yang and D.-L. Yang [17] and proposed another learning model in which the actual processing time of job Jj scheduled in position r of a sequence is
(8)pir=pif(∑k=1r-1‍p[k])g(r),
where ∑k=10‍p[k]=0,f:[0,+∞)→(0,1] is a differentiable nonincreasing function where f is nondecreasing on [0,+∞), f(0)=1, and g:[0,+∞)→(0,1] is a nonincreasing function with g(1)=1. Many recent studies (see, e.g., Wang [19], Toksarı and Güner [20], Yang and Kuo [21], Cheng et al. [22, 23], Cheng et al. [24], Kuo [25], Yang [26], and Lee and Wu [27]) have been conducted to address the combined processing time models in scheduling problems.In a recent paper, J.-B. Wang and J.-J. Wang [28] proposed a new general learning effect model for both position-based effect and sum-of-processing-time-based effect, which can be described as
(9)pir=pif(∑l=1r-1‍βlp[l])g(r),
where ∑l=10‍βlp[l]∶=0,f:[0,+∞)→(0,1] is a differentiable nonincreasing function where f′ is nondecreasing on [0,+∞), g:[1,+∞)→(0,1] is a nonincreasing function with g(1)=1, and βl is the weight of position r. They showed that even with the introduction of a general learning effect to job processing times, some single-machine scheduling problems can be optimally solved in polynomial time. They also proved that some special cases of the flow shop scheduling problems are polynomially solvable under the proposed model.In this paper, we explore to consider scheduling problems with considerations of two general deterioration effects whose actual processing times functions of jobs are modified from the models in Lee and Wu [27] and J.-B. Wang and J.-J. Wang [28] with respect to deterioration effects. The motivation for our study stems from the hardware production line that cuts a class of products to proper sizes and shapes. The actual processing time of a product depends on the quality of the cutting tool in the manufacturing process. Due to tool blunting, the actual processing time of a product increases with respect to the sum of the processing time of products already processed by the cutting tool and the number of products already processed. The objective of our study is to find the optimal job sequence to minimize the makespan of all the jobs.The remaining part of this paper is organized as follows. In Section2, we consider two single-machine scheduling problems. In Section 3, we investigate the flow shop scheduling problems under proper given conditions. We conclude this paper and describe the possible extensions in the last section.


## 2. Single-Machine Scheduling

The formulation of the considered single-machine scheduling problems can be described as follows. At time zero, there aren independent jobs ready to be processed on a single-machine. Preemption is not allowed and a machine is only able to process one job at a time. Job j has a normal processing time pj(j=1,2,…,n).In this paper, we propose two general deterioration models with respect to both position-based effect and sum-of-processing-time-based effect. By the first model, if jobj is scheduled in the r position of the sequence, the actual processing time of job j is
(10)pjr=pj[f(∑l=1r-1‍βlp[l])+g(r)],
where ∑l=10‍βlp[i,l]∶=0,f:[0,+∞)→[1,+∞) is a differentiable nondecreasing function and f(0)=1, g:[1,+∞)→[1,+∞) is a nondecreasing function with g(1)=1, βl is the weight of position l, p[l] denotes the normal processing time of job i, and the subscript [l] denotes the job in position l of a sequence. In some actual processes, different jobs always have different complexities which lead to different experience to the worker in production line; thus, we assume that 0≤β1≤β2≤⋯βn.By the second model, if jobj is scheduled in the r position, its actual processing time is
(11)pjr=pjf(∑l=1r-1‍βlp[l])g(r),
where all the notations have the same means as those of the first model. Note that the function used in the model (11) is the same as the function used by J.-B. Wang and J.-J. Wang [28]. The difference between this model and the model in J.-B. Wang and J.-J. Wang [28] is that the former aims to study the deterioration effect while the latter (J.-B. Wang and J.-J. Wang [28]) considers learning effect.By using the three-field notation scheme for the scheduling problem introduced by Graham et al. [29], the single-machine scheduling problem with respect to the first model can be denoted as 1∣pjr=pj[f(∑l=1r-1βlp[l])+g(r)],DE∣Cmax, where DE denotes the deterioration effect. Similarly, the single-machine scheduling problem with respect to the second model can be denoted as 1∣pjr=pjf(∑l=1r-1βlp[l])g(r),DE∣Cmax.In the following, we first state two lemmas that will be used in the proofs of the following theorems in this section.Lemma 1.
Iff:[0,+∞)→[1,+∞) is nondecreasing and its derived function f′ is nonincreasing on [0,+∞),λ≥1,δ1≥1, and x≥0, then (1-λ)(f(A)δ2+1) + λ(f(A+x)δ2+δ1) - (f(a+λx)δ2+δ1)≥0.Proof.
We leth(x)=(1-λ)(f(A)δ2+1)+λ(f(A+x)δ2+δ1)-(f(A+λx)δ2+δ1). The first derivation of h(x) with respect to x can be obtained that h′(x)=λδ2[f′(A+x)-f′(A+λx)]≥0 under the condition that f:[0,+∞)→[1,+∞) is a differentiable nondecreasing function with f′ being nonincreasing on [0,+∞),λ≥1, and δ1≥1. Then, it is obvious that h(x) is an increasing function on x. Therefore, we have h(x)≥h(0)=(1-λ)(1-δ1)≥0 for λ≥1,δ1≥1.With a similar differentiation method, it is easy to obtain the following lemma.Lemma 2.
Iff:[0,+∞)→[1,+∞) is nondecreasing and its derived function f′ is nonincreasing on [0,+∞),λ≥1,δ≥1, and x≥0, then (1-λ)f(A)+λδf(A+x)-δf(A+λx)≥0.Theorem 3.
The problem1∣pjr=pj(f(∑l=1r-1βlp[l])+g(r)),DE∣Cmax can be optimally solved by the Longest Processing Time first rule of pj (the LPT rule) if f′ is nonincreasing on [0,+∞).Proof.
To prove this theorem, it is sufficient to prove that a schedule can be enhanced by scheduling the job with longer processing time into the earlier position of the schedule under the given condition in the theorem. Let the scheduleσ be [σ1,Jj,Jk,σi2,σ2] and let the schedule σ′ be [σ1,Jk,Jj,σ2], where σ1 and σ2 are partial job sequences, and the difference between σ and σ′ is a pairwise interchange of two adjacent jobs Jj and Jk in the schedule. Concretely, Jj and Jk are assumed to be assigned in the rth and r+1th position, respectively, in the schedule σ. In σ′, Jj and Jk are assigned in the r+1th and rth position, respectively. Without loss of generality, the normal processing times of Jj and Jk are assumed to satisfy pj≤pk. To show that σ′ dominates σ, it suffices to show that Ck(σ)≥Cj(σ′) and Cu(σ)≥Cu(σ′) for any job Ju in σ2. Let the completion time of the last job in partial schedule σ1 be Cσ1. In the schedule σ, the completion times of Jj and Jk are
(12)Cj(σ)=Cσ1+pj[f(∑l=1r-1‍βlp[l])+g(r)],(13)Ck(σ)=Cσ1+pj[f(∑l=1r-1‍βlp[l])+g(r)]+pk[f(∑l=1r-1‍βlp[l]+βrpj)+g(r+1)],
respectively. In the schedule σ′, the completion times of Jk and Jj are
(14)Ck(σ′)=Cσ1+pk[f(∑l=1r-1‍βlp[l])+g(r)](15)Cj(σ′)=Cσ1+pk[f(∑l=1r-1‍βlp[l])+g(r)]+pj[f(∑l=1r-1‍βlp[l]+βrpk)+g(r+1)],
respectively. Combining (13) and (15), we have
(16)Ck(σ)-Cj(σ′)=(pj-pk)[f(∑l=1r-1‍βlp[l])+g(r)]+pk[f(∑l=1r-1‍βlp[l]+βrpj)+g(r+1)]-pj[f(∑l=1r-1‍βlp[l]+βrpk)+g(r+1)]×pkpj[f(∑l=1r-1‍βlp[l])1g(r)+1]=pjg(r){(1-pkpj)[f(∑l=1r-1‍βlp[l])1g(r)+1]hhh+pkpj[f(∑l=1r-1‍βlp[l]+βrpj)hh×1g(r)+g(r+1)g(r)∑l=1r-1‍]hhh-[f(∑l=1r-1‍βlp[l]+βrpjpkpj)hhh×1g(r)+g(r+1)g(r)∑l=1r-1‍]}.
Let A=∑l=1r-1‍βlp[l],λ=pk/pj,δ1=(g(r+1)/g(r)),δ2=(1/g(r)), and x=βrpj. Based on the formulation of the considered problem, it is easy to obtain that A≥0,λ≥1,δ1≥1,0<δ2≤1, and x≥0. Based on Lemma 1 and (16), we have
(17)Ck(σ)-Cj(σ′)=pjg(r)[(1-λ)(f(A)δ2+1)hhhhhhhhhhh+λ(f(A+x)δ2+δ1)hhhhhhhhhhh-(f(a+λx)δ2+δ1)]≥0.
Assuming that Js is the job scheduled in the r+2 position of the job sequence, then the completion times of Js in σ and σ′ are
(18)Cs(σ)=Ck(σ)+ps[f(∑l=1r-1‍βlp[i,l]+βrpj+βr+1pk)+g(r+2)∑l=1r-1‍],(19)Cs(σ′)=Cj(σ′)+ps[f(∑l=1r-1‍βlp[i,l]+βrpk+βr+1pj)+g(r+2)∑l=1r-1‍],
respectively. Since pj≤pk and βr≤βr+1, it can be obtained that
(20)(βrpj+βr+1pk)-(βrpk+βr+1pj)=(βr-βr+1)(pj-pk)≥0.
Since f is a nondecreasing function, (20) is equivalent to
(21)f(∑l=1r-1‍βlp[i,l]+βrpj+βr+1pk)≥f(∑l=1r-1‍βlp[i,l]+βrpk+βr+1pj).
LetCs(σ) and Cs(σ′) denote the completion time of job Js in the schedule σ and σ′, respectively. From (17)–(19) and (21), we have Cs(σ)≥Cs(σ′). Thus, we show that Js starts earlier in σ′ than in σ and completes earlier in σ′ than in σ. With a similar proof method, it can be shown that Cu(σ)≥Cu(σ′) for any job Ju in σ2. By repeating the above argument, it is obvious to lead to the conclusion that a schedule can be enhanced by scheduling the job with longer processing time into the earlier position of the job sequence.Based on Lemma2, the following theorem can be obtained by using a similar proof method to that of Theorem 3.Theorem 4.
The problem1∣pjr=pj(f(∑l=1r-1βlp[l])g(r)),DE∣Cmax can be optimally solved by the Longest Processing Time first rule (the LPT rule) if f′ is nonincreasing on [0,+∞).
Ifg(r) is unchanged with respect to r, then two actual processing time models can be both simplified as pjr=pjf(∑l=1r-1βlp[l]). Similarly, if f(∑l=1r-1βlp[l]) is unchanged with respect to ∑l=1r-1βlp[l], then two actual processing time models can be both simplified as pjr=pjg(r). It is obvious that the single-machine problem with the above special models can be also optimally solved by the LPT rule.


## 3. Flow Shop Scheduling

The formulation of the flow shop scheduling problem can be described as follows. There aren independent jobs J1,J2,…,Jn ready to be processed on m machines M1,M2,…,Mm at time zero. Job Jj consists of m operations O1j,O2j,…,Omj. Preemption is not allowed and a machine is only able to process one operation at a time. All machines should process the operations of the jobs in the same order. Operation Oi+1,j may start only after operation Oij has been completed. Operation Oij has a normal processing time pij(i=1,2,…,m;j=1,2,…,n), and the actual processing time of operation Oij is pijr if it is scheduled in position r (r=1,2,…,n) in a sequence. In this paper, we propose two general deterioration models. By the first model, if operation Oij is scheduled in the r position of the sequence, the actual processing time of operation Oij is
(22)pijr=pij[f(∑l=1r-1‍βlp[il])+g(r)],
where ∑l=10‍βlp[i,l]∶=0,f:[0,+∞)→[1,+∞) is a differentiable nondecreasing function, and f(0)=1,g:[1,+∞)→[1,+∞) is a nonincreasing function with g(1)=1, and βl is the weight of position l; p[il] denotes the normal processing time of the operation scheduled in the rth position on machine Mi, where the subscript [i,l] denotes the job in position l of the sequence on Mi. In many real life scenarios, positions are characterized by a different grade of complexity; thus, each position can provide different complexity to the manufacturing process; hence, we assume that 0≤β1≤β2⋯βn.By the second model, if jobj is scheduled on the r position of machine i, its actual processing time is
(23)pijr=pijf(∑l=1r-1‍βlp[il])g(r),
where all the notations have the same means as those of the first model.In the following, we first introduce a new general deterioration model. The actual processing time of jobj on the r position of machine i is
(24)pijr=H[pij,f(∑l=1r-1‍βlp[il]),g(r)],
where pij1=H(pij,f(0),g(1))=pij and H is nondecreasing in pij,f(∑l=1r-1βlp[il]), and g(r). Obviously, model (22) and model (23) are both special cases of new model (24).Lemma 5.
The problemF∣pijr=H[pij,f(∑l=1r-1βlp[il]),g(r)],p2j=p2,DE∣Cmax has the same optimal schedule as the problem 1∣p1jr=H[p1j,f(∑l=1r-1βlp[1l]),g(r)],DE∣Cmax if p1j≥p2.Proof.
LetC[j] denote the completion time of the job scheduled in jth position of the job sequence. For j=1, we have C[1]=p[11]+p2.
Becausep2j=p2 and p1j≥p2, it can be obtained that p1jr=H[p1j,f(∑l=1r-1βlp[1l]),g(r)]≥p2 for j=1,2,…,n and r=1,2,…,n. The schedule is illustrated in Figure 1.
Then, we have the completion times for jobsj=2,3,…,n in the following:
(25)C[2]=max{C[1],p[11]+H[p[12],f(β1p[1,l]),g(2)]}p[11]+p2=p[11]+H(p[12],f[β1p[1,l]),g(2)]+p2,⋮C[k+1]=max{C[k],∑r=1k‍H[p[1r],f(∑l=1r-1‍βlp[1,l]),g(r)]}×p[11]+p2=∑r=1k‍H[p[1r],f(∑l=1r-1‍βlp[1,l]),g(r)]+p2,⋮Cmax=C[n]=max{C[k],∑r=1k‍H[p[1r],f(∑l=1r-1‍βlp[i,l]),g(r)]}×p[11]+p2=∑r=1n‍H[p[1r],f(∑l=1r-1‍βlp[1,l]),g(r)]+p2.
Since p2 is constant, an optimal schedule of minimizing the makespan for the problem F2∣p1jr=H[p1j,f(∑l=1r-1βlp[1l],g(r)],DE∣Cmax must be the optimal schedule of minimizing for the problem F2∣pijr=H[pij,f(∑l=1r-1βlp[1l]),g(r)],p2j=p2,DE∣Cmax.Figure 1
The illustration of the problemF∣pijr = H(pij,f(∑l=1r-1βlp[il]),g(r)),p2j = p2,DE∣Cmax.With a similar proof method of Lemma5, we can obtain the following theorem.Theorem 6.
The problemFm∣pijr = H[pij,f(∑l=1r-1βlp[il]),g(r)],p2jr = p3jr = ⋯=pmjr = p,DE∣Cmax has the same optimal schedule as the problem 1∣p1jr = H(p1j,f(∑l=1r-1βlp[1l],g(r)),DE∣Cmax if p1j≥p.Combining Theorems3 and 6, we have the following corollary.Corollary 7.
The problemFm∣pijr=pij[f(∑l=1r-1βlp[il])+g(r)],p2jr=p3jr=⋯=pmjr=p,DE∣Cmax can be optimally solved by the Longest Processing Time first rule of pj (the LPT rule) if f′ is nonincreasing on [0,+∞) and p1j≥p.Similarly, based on Theorems4 and 6, it is easy to get the following result.Corollary 8.
The problemFm∣pijr=pijf(∑l=1r-1βlp[il])g(r),p2jr=p3jr=⋯=pmjr=p,DE∣Cmax can be optimally solved by the Longest Processing Time first rule of pj (the LPT rule) if f′ is nonincreasing on [0,+∞) and p1j≥p.Theorem 9.
If a schedule simultaneously minimizesH(p[2n],f(∑l=1n-1‍βlp[2,l]),g(n)) and the makespan of the problem 1∣p1jr=H(p1j,f(∑l=1r-1βlp[1l],g(r)),DE∣Cmax, it must be the optimal schedule of the problem F2∣pijr=H(pij,f(∑l=1r-1βlp[il],g(r)),min(p1·)≥max(p2·),DE∣Cmax.Proof.
By using the same notation as that in the proof of Theorem6, we let C[j] denote the completion time of the job scheduled in jth position of the job sequence. For j=1, we have C[1]=p[11]+p2.
Becausemin(p1·)≥max(p2·), it can be obtained that
(26)H(p1j,f(∑l=1r-1‍βlp[1l]),g(r))≥H(p2j,f(∑l=1r-1‍βlp[2l]),g(r))
for j=1,2,…,n and r=1,2,…,n. Then, we have the completion times for jobs j=2,3,…,n in the following:
(27)C[2]=max{C[1],p[11]+H(p[12],f(β1p[1,l]),g(2))}+H(p[22],f(β1p[2,1]),g(2))=p[11]+H(p[12],f(β1p[1,l]),g(2))+H(p[22],f(β1p[2,1]),g(2)),⋮C[k+1]=max{C[k],∑r=1k+1‍H(p[1r],f(∑l=1r-1‍βlp[1,l]),g(r))}+H(p[2,k+1],f(∑l=1k‍βlp[2,l]),g(k+1))=∑r=1k+1‍H(p[1r],f(∑l=1r-1‍βlp[1,l]),g(r))+H(p[2,k+1],f(∑l=1k‍βlp[2,l]),g(k+1)),⋮Cmax=C[n]=max{∑r=1n‍C[n-1],∑r=1n‍H(p[1r],f(∑l=1r-1‍βlp[1,l]),g(r))}+H(p[2n],f(∑l=1n-1‍βlp[2,l]),g(n))=∑r=1n‍H(p[1r],f(∑l=1r-1‍βlp[1,l]),g(r))+H(p[2n],f(∑l=1n-1‍βlp[2,l]),g(n)).
Since∑r=1nH(p[1r],f(∑l=1r-1βlp[1,l]),g(r)) can be explained as the makespan of the problem 1∣p1jr=H(p1j,f(∑l=1r-1βlp[1l],g(r)),DE∣Cmax, the schedule minimizes H(p[2n],f(∑l=1n-1‍βlp[2,l]),g(n)) simultaneously and the makespan of the problem F2∣p1jr = H(p1j,f(∑l=1r-1βlp[1l],g(r)),DE∣Cmax is the optimal schedule of the problem F2∣pijr = H(pij,f(∑l=1r-1βlp[il],g(r)),min(p1·) ≥ max(p2·),DE∣Cmax.Combining Theorems3 and 9, we have the following corollary.Corollary 10.
The problemF2∣pijr=pij[f(∑l=1r-1βlp[il])+g(r)],min(p1·)≥max(p2·),DE∣Cmax can be optimally solved by the Longest Processing Time first rule of pj (the LPT rule) if f′ is nonincreasing on [0,+∞).Similarly, combining Theorems4 and 9, we can obtain the following result.Corollary 11.
The problemF2∣pijr=pijf(∑l=1r-1βlp[il])g(r),min(p1·)≥max(p2·),DE∣Cmax can be optimally solved by the Longest Processing Time first rule of pj (the LPT rule) if f′ is nonincreasing on [0,+∞).


## 4. Conclusions

This paper considered three scheduling problems with general deterioration models, where the actual processing time function of a job depends not only on the total weighted normal processing times of jobs already processed but also on the scheduled position in the job sequence. Firstly, for two single-machine scheduling problems with general deterioration models associated with both the total weighted normal processing times of the jobs and the scheduled position in the job sequence, we proved that two single-machine scheduling problems are both polynomially solvable under the condition that the derived actual processing time functions are nonincreasing, respectively. Secondly, based on the results of the single-machine problem, we also showed that four flow shop scheduling problems can be optimally solved in polynomial time under proposed conditions.Future works may focus on developing randomized algorithms for the scheduling problem without pregiven conditions. The variability of tool changes or maintenance activities is also worth considering in scheduling problems with general deterioration effects.



---

*Source: 218981-2013-12-21.xml*