# Minimizing Total Weighted Completion Time  on Single Machine with Past-Sequence-Dependent Setup Times and Exponential Time-Dependent  and Position-Dependent Learning Effects

Authors: Kaibiao Sun; Hongxing Li
Journal: Discrete Dynamics in Nature and Society
 (2009)

---

## Abstract

This paper addresses a single-machine problem in which the past-sequence-dependent (p-s-d) setup times and exponential time-dependent and position-dependent learning effects are considered. By the exponential time-dependent learning effect, it means that the processing time of a job is defined by an exponent function of the total actual processing time of the already processed jobs. The setup times are proportional to the length of the already processed jobs. The aim is to minimize the total weighted completion time, this is an NP-hard problem. Under certain conditions, it is shown that the classical WSPT rule is optimal for the problem.


---

## Body

## 1. Introduction

In classical scheduling problems, the processing time of a job is assumed to be a constant. However, in many realistic problems of operations management, both machines and workers can improve their performance by repeating the production operations. Therefore, the actual processing time of a job is shorter if it is scheduled later in a sequence. This phenomenon is known as the “learning effect” in literature (see [1]). During the last few years, learning effect has attracted growing attention from the scheduling research community on account of its significance. Concerning the learning effects, two different approaches in scheduling environments have been suggested. The first one can be best described as position-dependent learning, which was first introduced into the field of scheduling by Biskup in [2] and Cheng and Wang in [3], meaning that learning is affected by the pure number of jobs being processed. Many references have studied such a learning effect model thereafter, a sample of these papers can be seen in [4–13]. However, the position-dependent learning effects neglect the processing times of the jobs already processed. If human interactions have a significant impact during the processing of jobs, the processing time will add to the employees' experience and cause learning effects. For situations like this, Kuo and Yang in [14] introduced a time-dependent learning effect, that is, the sum of processing time dependent learning, and showed that the shortest processing time (SPT) rule is optimal for the objective of minimizing the total completion time. For more papers about this time-dependent learning model, the reader is referred to the papers [15–17]. Besides, Koulamas and Kyparisis in [18] introduced a general sum of processing time-dependent learning effect model in which employees learn more if they perform a job with a longer processing time. Recently, Wu and Lee in [19] proposed a new learning model where the actual job processing time not only depends on its scheduled position but also depends on the sum of the processing times of jobs already processed. Let pjr denote the actual processing time job Jj scheduled in rth position, then pjr=(1+∑k=1r-1p[k]/∑k=1npk)a1ra2, where p[k] is the normal processing time of the kth job in a sequence and a1≤0,a2≤0. Under this model they showed that the SPT sequence is optimal for minimizing makespan and total completion time on single machine under the proposed learning model. In addition, they showed that the WSPT sequence is optimal for minimizing the sum of the weighted completion times if jobs have agreeable weights. Cheng et al. in [20] consider another learning model, in which the learning effect is given as pjr=(1-∑k=1r-1p[k]/∑k=1npk)a1ra2, where a1≥1,a2≤0. Under this learning model, they obtained the same results as that in [19]. Further, they showed that the EDD sequence is optimal for the maximum lateness if jobs have agreeable due dates. For a recent state-of-the-art review on scheduling models and problems with learning effects, the readers are referred to [21].On the other hand, it is reasonable and necessary to consider scheduling problems with setup times (see [22]). There are two types of setup time or setup cost, namely, sequence-independent and sequence-dependent. In the first case, the setup time/cost depends solely on the task to be processed, regardless of its preceding task. While in the sequence-dependent type, setup time/cost depends on both the task and its preceding task. For recent results and trends in scheduling problems with setup times or costs, the reader may refer to the recent review paper [23]. Koulamas and Kyparisis in [24] first introduced a scheduling problem with past-sequence-dependent (p-s-d) setup times, that is, the setup time is dependent on all already scheduled jobs. They showed that the standard single-machine scheduling problems with p-s-d setup times to minimize makespan, total completion time and the total absolute differences in completion times are polynomially solvable. They also extended their results to nonlinear p-s-d setup times. Subsequently, Kuo and Yang in [25], Wang in [26], Biskup and Herrmann [27], Wang et al. in [28] studied different single-machine scheduling problems with time-dependent learning effect and setup times considerations.From the learning models mentioned earlier, it is not hard to see that the actual processing time of, say, therth job is affected by the sum of the normal processing times of the preceding r-1 jobs. This learning effect model is based on the assumption that the number of operating processes in a job depends on the repetitions of the same operation. However, in many situations, the operating processes of a job are different, for example, car repair or maintenance and patient diagnosis and treatment. The conditions of cars or patients are different. Hence, there are no identical repetitions of operating processes in the job. Nevertheless, there still exists a certain learning effect after operating the job. In such situations, the learning effect is due to the experiences of operating jobs, that is, the total actual processing time of jobs. To the best of our knowledge, apart from the recent paper [29], it has not been investigated the scheduling models considering the actual time-dependent learning effect. In this paper, we consider a single machine total completion time minimization problem with past-sequence-dependent setup times and learning effect where the actual processing time of a job is not only an exponential function of the total actual processing times of the jobs already processed but also a function of the job's scheduled position.


## 2. Problem Formulation

The model is described as follows. There are given a single machine andn independent and nonpreemptive jobs that are immediately available for processing. The normal processing time of job Jj is pj (1≤j≤n). Associated with each job Jj(1≤j≤n) is a weight wj and a due-date dj. Let p[k] and p[k]A be the normal processing time and the actual processing time of a job when it is scheduled in the kth position in a sequence, respectively. Let pjrA be the actual processing time of job Jj when it is scheduled in position r in a sequence. Then(2.1)pjrA=pjα-β(∑k=1r-1p[k]A/∑k=1np[k])rτ,
where p[1]A=p[1], p[s]A=p[s]α-β(∑k=1s-1p[k]A/∑k=1np[k])sτ (1<s≤r-1), α≥1, β≥0, and τ≤0. For convenience, we denote this actual time-dependent and job-position dependent learning effect defined in (2.1) by LEat-p.As in [24, 26], we assume that the p-s-d setup time of a job if it is scheduled in position r is given by(2.2)s[1]=0,s[r]=∑k=1r-1bp[k]A,
where b≥0 is a normalizing constant, and we denote the p-s-d setup given in (2.2) by spsd.For a given scheduleS, let Cj(S) denote the completion time of job Jj and C[r](S) represent the complete time of the job scheduled in the rth position in π. For single-machine scheduling with past-sequence-dependent setup times and time-dependent learning effect, Wang in [26] showed that the completion time of the rth job in a given sequence S is given by(2.3)C[r](S)=∑k=1r(b(r-k)+1)p[k]A.
Similarly, the completion time of the rth job in a given sequence S under (2.1) is(2.4)C[r](S)=∑k=1r(b(r-k)+1)p[k]α-β(∑l=1k-1p[l]A/∑l=1np[l])kτ.LetCmax denote the makespan, where Cmax=max{C1,C2,…,Cn}. Let ∑wjCj represent the weighted sum of completion times. In the remaining part of the paper, the problem will be denoted using the three-field notation scheme 1/LEat-p,spsd/∑wjCj introduced by Graham et al. in [30].


## 3. Total Completion Time Minimization Problem

In this section, we consider the total completion time minimization problems with past-sequence-dependent setup times defined in (2.2) and the learning effect defined in (2.1).First, we give three lemmas, which are useful for the following theorem.Lemma 3.1.
It holds that,tλ((r+1)/r)τ-λt((r+1)/r)τ+λ-1>0forλ>1,0≤t≤1,τ≤0,andr=1,2,…,n-1.Proof.
Let(3.1)F(t)=tλ(r+1r)τ-λt(r+1r)τ+λ-1.
Taking the first derivative of F(t) with respect to t, we have
(3.2)F′(t)=λtλ-1(r+1r)τ-λ(r+1r)τ=λ(r+1r)τ(tλ-1-1).
Since λ>1 and 0≤t≤1, we have F′(t)≤0. This implies that F(t) is nonincreasing on 0≤t≤1. Hence,
(3.3)F(t)≥F(1)=(r+1r)τ-λ(r+1r)τ+λ-1=(λ-1)(1-(r+1r)τ)>0
for λ>1, τ≤0 and r=1,2,…,n-1. This completes the proof.Lemma 3.2.
It holds that,1-λ1t((r+1)/r)τ+λ2tlnt((r+1)/r)τ≥0for0<t≤1,τ≤0,0≤λ1≤λ2≤1,andr=1,2,…,n-1.Proof.
Let(3.4)F(t,λ1,λ2)=1-λ1t(r+1r)τ+λ2tlnt(r+1r)τ.
Then ∂F/∂λ1=-t((r+1)/r)τ<0,∂F/∂λ2=tlnt((r+1)/r)τ≤0, thus we have
(3.5)F(t,λ1,λ2)≥F(t,1,1)=1-t(r+1r)τ+tlnt(r+1r)τ.
Let
(3.6)f(t)=1-t(r+1r)τ+tlnt(r+1r)τ.
Then f′(t)=((r+1)/r)τlnt≤0, hence f(t) is nonijncreasing on t and f(t)≥f(1)=1-((r+1)/r)τ≥0 for 0<t≤1. Therefore, F(t,λ1,λ2)≥0 for 0<t≤1, τ≤0, 0≤λ1≤λ2≤1, and r=1,2,…,n-1. This completes the proof.Lemma 3.3.
It holds that,μ[1-λ1t((r+1)/r)τ]-[1-λ2tμ((r+1)/r)τ]≥0 forμ≥1,0<t≤1,τ≤1, 0≤λ1≤λ2≤1, and r=1,2,…,n-1.Proof.
Let(3.7)h(μ)=μ[1-λ1t(r+1r)τ]-[1-λ2tμ(r+1r)τ].
To take the first and second derivatives of (3.7) with respect to μ, we have
(3.8)h′(μ)=1-λ1t(r+1r)τ+λ2tμlnt(r+1r)τ,h′′′(μ)=λ2tμln2t(r+1r)τ≥0.
Hence, h′(μ) is nondecreasing on μ≥1, that is, h′(μ)≥h′(1) for μ≥1. By Lemma 3.2, we have
(3.9)h′(1)=1-λ1t(r+1r)τ+λ2tlnt(r+1r)τ≥0.
Therefore, h′(μ)≥h′(1)≥0. Hence, h(μ) is nondecreasing on μ, that is, h(μ)≥h(1)=(λ2-λ1)t((r+1)/r)τ≥0 for t≥0,τ≤0, 0≤λ1≤λ2≤1 and r=1,2,…,n-1. This completes the proof.Theorem 3.4.
For the total completion time minimization problem1/LEat-p,spsd/∑wjCj when pjrA is given by (2.1), an optimal schedule can be obtained by sequencing jobs in the WSPT rule if pl≤((b+1)/3τβlnα)∑k=1npk(l=1,…,n) and jobs have reversely agreeable weights, that is, pi<pj implies wi≥wj for all jobs Ji and Jj.Proof.
Consider an optimal scheduleS that does not follow the WSPT rule. Then in this schedule there must be at least two adjacent jobs, say job Jj followed by job Ji such that pj/wj>pi/wi which implies that pj≥pi by reversely agreeable weights. If pj>pi, then wi≥wj; if pi=pj, then wi>wj. Assume that job Jj is scheduled in position r. By performing an adjacent pair-wise interchange of jobs Jj and Ji and remaining all the other jobs in their original positions, we can obtain a new schedule, denoted by S′. Whereas under the original schedule Jj is scheduled in position r and Ji is scheduled in position r+1, under S′, Ji is scheduled in position r, and Jj is scheduled in position r+1. Denote S=(σ1,Jj,Ji,σ2), let Cσ1 be the completion time of the last job in σ1, and let Jk be the first job in σ2.
The completion times of the jobs processed before jobsJj and Ji are not affected by the interchange. In the following we will show that wiCi(S′)+wjCj(S′)≤wiCi(S)+wjCj(S) and the completion times of the jobs processed after jobs Jj and Ji are not increased by the interchanging argument. Under S, the completion times of jobs Jj and Ji are
(3.10)Cj(S)=∑k=1r-1(b(r-k)+1)p[k]A+pjα-β(∑k=1r-1p[k]A/∑k=1np[k])rτ,Ci(S)=∑k=1r-1(b(r+1-k)+1)p[k]A+(b+1)pjα-β(∑k=1r-1p[k]A/∑k=1np[k])rτ+piα-β((∑k=1r-1p[k]A+pjrA)/∑k=1np[k])(r+1)τ.
whereas under S′, they are
(3.11)Ci(S′)=∑k=1r-1(b(r-k)+1)p[k]A+piα-β(∑k=1r-1p[k]A/∑k=1np[k])rτ,Cj(S′)=∑k=1r-1(b(r+1-k)+1)p[k]A+(b+1)piα-β(∑k=1r-1p[k]A/∑k=1np[k])rτ+pjα-β((∑k=1r-1p[k]A+pjrA)/∑k=1np[k])(r+1)τ.
So we have
(3.12)wiCi(S)+wjCj(S)-wiCi(S′)-wjCj(S′)=b(wi-wj)∑k=1r-1p[k]A+b(wipj-wjpi)α-β(∑k=1r-1p[k]A/∑k=1np[k])rτ+(wi+wj)(pj-pi)α-β(∑k=1r-1p[k]A/∑k=1np[k])rτ+wipiα-β((∑k=1r-1p[k]A+pjrA)/∑k=1np[k])(r+1)τ-wjpjα-β((∑k=1r-1p[k]A+pirA)/∑k=1np[k])(r+1)τ.
Let x=α-β(∑k=1r-1p[k]A/∑k=1np[k]), λ1=wj/(wi+wj), λ2=wi/(wi+wj), μ=pj/pi, and t=α-β(pirA/∑k=1npk). Clearly μ≥1, 0≤λ1≤λ2≤1, and t>0. Then the last three terms in (3.12) can be rewritten as
(3.13)wiCi(S)+wjCj(S)-wiCi(S′)-wjCj(S′)=pi(wi+wj)rτx{μ[1-λ1t(r+1r)τ]-[1-λ2tμ(r+1r)τ]}≥0(byLemma3.3).
From pj/wj>pi/wi, we have b(wipj-wjpi)α-β(∑k=1r-1p[k]A/∑k=1np[k])rτ>0. In addition, from pj≥pi, which implies that wi≥wj, we have b(wi-wj)∑k=1r-1p[k]A≥0. Hence,
(3.14)wiCi(S)+wjCj(S)>wiCi(S′)+wjCj(S′).
Next, we will show that the completion times of the jobs in σ2 are not increased by the interchanging argument. Firstly, we show that Cj(S′)≤Ci(S) after interchanging. Since
(3.15)Cj(S′)-Ci(S)pixrτ=(b+1)(1-pjpi)+pjpiα-β(pirA/∑k=1np[k])(r+1r)τ-α-β(pjrA/∑k=1np[k])(r+1r)τ,
then let t=α-β(pirA/∑k=1npk) and λ=pj/pi. It is clearly that t≥0 and λ>1. By substituting t and λ into (3.15), it is simplified to
(3.16)Cj(S′)-Ci(S)pixrτ={(b+1)(1-λ)+λt(r+1r)τ-tλ(r+1r)τ}.
By Lemma 3.1, we have Cj(S′)<Ci(S).
Secondly, we show that the completion times of the jobs inσ2 are not increased. Note that Jk is the first job in σ2, it is scheduled in (r+2)th position, let
(3.17)Λ1=piα-β(∑k=1r-1p[k]A/∑k=1np[k])rτ+pjα-β(∑k=1rp[k]A/∑k=1np[k])(r+1)τ,Λ2=pjα-β(∑k=1r-1p[k]A/∑k=1np[k])rτ+piα-β(∑k=1rp[k]A/∑k=1np[k])(r+1)τ.
Then we have
(3.18)Λ1-Λ2pixrτ=(1-λ)+λt(r+1r)τ-tλ(r+1r)τ.
By Lemma 3.1 we have Λ1<Λ2. Since
(3.19)Ck(S′)=Cj(S′)+b(∑l=1r-1p[l]A+pirA+pjr+1A)+pkα-β((∑l=1r-1p[l]A+pirA+pjr+1A)/∑l=1np[l])(r+2)τ=∑k=1r-1(b(r+2-k)+1)p[k]A+(2b+1)piα-β(∑k=1r-1p[k]A/∑k=1np[k])rτ+(b+1)pjα-β((∑k=1r-1p[k]A+pirA)/∑k=1np[k])(r+1)τ+pkα-β((∑l=1r-1p[l]A+pirA+pjr+1A)/∑l=1np[l])(r+2)τ,Ck(S)=Ci(S)+b(∑l=1r-1p[l]A+pjrA+pir+1A)+pkα-β((∑l=1r-1p[l]A+pjrA+pir+1A)/∑l=1np[l])(r+2)τ=∑k=1r-1(b(r+2-k)+1)p[k]A+(2b+1)pjα-β(∑k=1r-1p[k]A/∑k=1np[k])rτ+(b+1)piα-β((∑k=1r-1p[k]A+pjrA)/∑k=1np[k])(r+1)τ+pkα-β((∑l=1r-1p[l]A+pjrA+pir+1A)/∑l=1np[l])(r+2)τ.
Then we have
(3.20)Ck(S′)-Ck(S)=b(pi-pj)α-β(∑k=1r-1p[k]A/∑k=1np[k])rτ+(b+1)(Λ1-Λ2)+pk(r+2)τ(α-β((Λ+Λ1)/P)-α-β((Λ+Λ2)/P))<(b+1)(Λ1-Λ2)+pk(r+2)τ(-βlnαPα-β((Λ+ξ)/P))(Λ1-Λ2)=(Λ2-Λ1)[pk(r+2)τ(βlnαPα-β((Λ+ξ)/P))-(b+1)]<[(β3τlnα)pkP-(b+1)](Λ2-Λ1).
For any job Jl, by assumption pl≤(b+1)/3τβlnα∑k=1npk for α≥1 and β≥0. Then (3.20) is not larger than zero, that is, Ck(S′)≤Ck(S). Similarly, we have Ch(S′)≤Ch(S) for any Jh in σ2.
Repeating this interchange argument for all jobs not sequenced in the WSPT rule yields the theorem.Corollary 3.5.
For the problem1/LEat-p,spsd/Cmax when pjrA is given by (2.1), if pl≤∑k=1npk/3τβlnα(l=1,…,n), then there exists an optimal schedule in which the job sequence is determined by the SPT rule.Proof.
it can be directly from the proof of Theorem3.4.Corollary 3.6.
For the problem1/LEat-p,spsd/∑Cj when pjrA is given by (2.1), if  pl≤∑k=1npk/3τβlnα(l=1,…,n), then there exists an optimal schedule in which the job sequence is determined by the SPT rule.Corollary 3.7.
For the problem1/LEat-p,spsd/∑Cjk when pjrA is given by (2.1), if pl≤∑k=1npk/3τβlnα(l=1,…,n), then there exists an optimal schedule in which the job sequence is determined by the SPT rule.Proof.
Here, we still use the same notations as in the proof of Theorem3.4. In order to show S′ dominates S, it suffices to show that (i) Cj(S′)≤Ci(S), (ii) Cl(S′)≤Cl(S) for any job Jl (l≠i,j) and (iii) Cik(S′)+Cjk(S′)≤Cik(S)+Cjk(S).
The proof of part (i) and part (ii) are given in Theorem3.4. In addition, from pi≤pj, we have Ci(S′)≤Cj(S). Since k is a positive real number, we have Cik(S′)+Cjk(S′)≤Cik(S)+Cjk(S). This completes the proof.Corollary 3.8.
For the problem1/LEat-p,spsd,pj=p/∑wjCj when pjr is given by (2.1), an optimal schedule can be obtained by sequencing jobs in non-increasing order of wj.Corollary 3.9.
For the problem1/LEat-p,spsd,wj=kpj/∑wjCjwhen pjr is given by (2.1), if pl≤((b+1)/3τβlnα)∑k=1npk(l=1,…,n), then an optimal schedule can be obtained by sequencing jobs in SPT rule.Remark 3.10.
In this paper, the learning effect is defined in (2.1) and p-s-d setup times is defined in (2.2), where the α≥1, β≥0, τ≤0, and b≥0 are controlled parameters. In practises, even human interactions have a significant impact during the processing of jobs, the impact should be limited. In general, half of the decreasing on the processing time is impossible. So the parameters should have practical meaning and properly given. If there parameters satisfy that ((b+1)/3τβlnα)<1, then for any job pl(l=1,2,…,n) we have pl≤((b+1)/3τβlnα)∑k=1npk. Thus, Theorem 3.4 holds under agreeable condition .


## 4. Conclusions

In this paper we investigated the single machine total weighted completion time minimization problem with p-s-d setup times and learning effect where the actual processing time of a job is not only an exponential function of the total actual processing times of the jobs already processed but also a function of the job's scheduled position. We show that the classical WSPT rule is optimal under certain conditions. It is suggested for future research to investigate other efficient heuristic algorithm to the problem or extend this kind of learning into the context of other more complicated scheduling settings, or propose more general and practical models.



---

*Source: 970510-2009-10-27.xml*