# Single-Machine Scheduling Problems with a Sum-of-Processing-Time-Based Learning Function

Authors: Xingong Zhang; Guangle Yan
Journal: International Journal of Combinatorics
 (2009)

---

## Abstract

Recently, learning scheduling problems have received increasing
attention. However, the majority of the research assume that the
actual job processing time is a function of its position. This paper
deals with the single-machine scheduling problem with a
sum-of-processing-time-based learning effect. By the effect of
sum-of-processing-time-based learning, we mean that the processing
time of a job is defined by total normal processing time of jobs in
front of it in the sequence. We show that the single-machine
makespan problem remains polynomially solvable under the proposed
model.  We show that the total completion time minimization problem
fora≥1 remains polynomially solvable under the proposed
model.  For the case of 0<a<1, we show that an optimal schedule of
the total completion time minimization problem is V-shaped with respect to normal job processing times.


---

## Body

## 1. Introduction

Scheduling problems are very important in the fields of manufacturing systems. Hence numerous scheduling problems have been studied for many years. In the classical scheduling theory, most research assumes that processing times of jobs are constant over the entire planning horizon. However, in many realistic situations, the efficiency of the production facility (e.g., a machine or a worker) improves continuously over time [1–4]. As a result, the production time of a given product is shorter if it is scheduled (and so processed) later. The processing times of jobs may be subject to change due to learning phenomena by Pinedo [5].During the last few years, learning effect has attracted growing attention in the scheduling community on account of its significance. There have been many attempts to formulate learning effect in a quantitative form as a function of learning variables, called a learning curve. Most of the concepts assume that the learning curve is a nonincreasing function which depends on the jobs already performed. For a survey on learning curves, the reader is refereed to Jaber and Bonney [6].Biskup [7] and Cheng and Wang [8] were one of the pioneers who brought the concept of learning into the field of scheduling. Recently Biskup [9] discusses the questions why and when learning effects in scheduling environments might occur and should be regarded from a planning perspective. Afterwards he gives a concise overview on the literature on scheduling with learning effects. He classifies the learning models in scheduling into two types, namely position-based learning and sum-of-processing-times-based learning.In the classical position-dependent learning effect model (Biskup [7]), the actual processing time pir of job Ji when it is scheduled in the rth position in a processing sequence is defined as pjr=pjra, where a is a nonpositive learning index and pi denotes the normal processing time of job Ji. Biskup [7] indicated that the learning effect has been observed in numerous practical situations in different sectors of industry and for a variety of corporate activities. He proposed a position-based learning model and showed that two single-machine scheduling problems remain polynomially solvable. Since then, many researchers have paid more attention on the relatively young but very vivid area. Mosheiov [10] found that under Biskup's learning effect model the optimal schedules for some classical scheduling problems remain valid, but they require much greater computational effort to obtain. In addition, he gave some counterexamples to show that the optimal schedules for scheduling problems with learning effects may be different from those for the corresponding classical scheduling problems. Many researchers have studied such a learning effect model and its variants thereafter; a sample of these papers include [11–20].Note that position-dependent learning effects neglect the processing times of the jobs already processed. If human interactions have significant impacts during the processing of jobs, the processing times will be added to theemployees′ experience and thus cause learning effects. For situations like this it might be more appropriate to consider a time-dependent learning effect [9]. Kuo and Yang [21] considered a sum-of-job-processing-times-based learning effect model. They provided the optimal solution of the total completion time problem. For more papers about this time-dependent learning effect model, the reader is refereed to [22–27].In this paper, we propose a sum-of-processing-time-based learning effect model where the learning effect is expressed as a function of the normal processing times of jobs already processed. This model is adopted from Cheng et al. [28] They consider some machine scheduling problems with deteriorating jobs and learning effect. The actual processing time of a job depends on not only the processing times of the jobs already processed but also its scheduled position. They derive polynomial-time optimal solutions for the problems to minimize makespan and total completion time in the single-machine case.Specifically, we consider two single-machine scheduling problems with a sum-of-processing-time-based learning effect. The objectives are to minimize the makespan and the total completion time of all jobs, respectively. The rest of the paper is organized as follows. In the next section, we give the problem description. In Section3, we consider two single-machine scheduling problems. The last section is the conclusion.


## 2. Problem Description

In this section, we first define the notation that is used throughout this paper, followed by the description of the problem. There aren jobs ready to be processed on a single machine. All jobs are available at time zero. Let pj denote the normal processing time of job j for j=1,2,…,n. In addition, let p[r] denote the normal processing time of the job scheduled in the rth position in a job sequence. If job j is scheduled in the rth position in a sequence, then its actual processing time is(2.1)pjr=pj(p0+∑l=1r-1p[l]p0+∑l=1npl)a,
where p0>0 is a given parameter, a denotes the learning rate where a>0 and ∑l=10p[l]=0. Under this learning effect model, the actual processing time of job j is affected by the previous (r-1) jobs. In the remaining part of the paper, all the problems considered will be denoted using the three-field notation scheme α|β|γ introduced by Graham et al. [29]


## 3. Single-Machine Scheduling Problems

First, we give two lemmas; they are useful for the following theorems. The proofs of the lemmas can be obtained by differentiation.Lemma 3.1.
One has[1-(1+λx)a]-λ[1-(1+x)a]≥0ifλ≥1,x≥0,0<a<1.Lemma 3.2.
One has[1-(1+λx)a]-λ[1-(1+x)a]≤0ifλ≥1,x≥0,a≥1.Theorem 3.3.
For the problem1∣pjr=pj((p0+∑l=1r-1p[l])/(p0+∑l=1npl))a∣Cmax,(1)
if0<a<1, then an optimal schedule can be obtained by sequencing the jobs in non-increasing order of pj (the longest processing time (LPT) rule).(2)
ifa≥1, then an optimal schedule can be obtained by sequencing the jobs in nondecreasing order of pj (the shortest processing time (SPT) rule).Proof.
The proof follows directly from the pairwise interchange analysis. Letπ and π′ be two job schedules where the difference between π and π′ is a pairwise interchange of two adjacent jobs Ji and Jj, that is, π=[S1,Ji,Jj,S2], π′=[S1,Jj,Ji,S2], where S1 and S2 are partial sequences. Furthermore, we assume that there are r-1 jobs in S1. Thus, Ji and Jj are the rth and (r+1)th jobs, respectively, in π. Likewise, Jj and Ji are scheduled in the rth and the (r+1)th positions in π′. To further simplify the notation, let A denote the completion time of the last job in S1. Under π, the completion times of jobs Ji and Jj are
(3.1)Ci(π)=A+pi(p0+∑l=1r-1p[l]p0+∑l=1npl)a,(3.2)Cj(π)=A+pi(p0+∑l=1r-1p[l]p0+∑l=1npl)a+pj(p0+∑l=1r-1p[l]+pip0+∑l=1npl)a.
Under π′, the completion times of jobs Jj and Ji are
(3.3)Cj(π)=A+pj(p0+∑l=1r-1p[l]p0+∑l=1npl)a,(3.4)Ci(π)=A+pj(p0+∑l=1r-1p[l]p0+∑l=1npl)a+pi(p0+∑l=1r-1p[l]+pjp0+∑l=1npl)a.
After taking the difference between (3.2) and (3.4), it is obtained that
(3.5)Cj(π)-Ci(π′)=(pi-pj)(p0+∑l=1r-1p[l]p0+∑l=1npl)a+pj(p0+∑l=1r-1p[l]+pip0+∑l=1npl)a-pi(p0+∑l=1r-1p[l]+pjp0+∑l=1npl)a.
By substituting t=(p0+∑l=1r-1p[l])/(p0+∑l=1npl), λ=pj/pi, w=pi/(p0+∑l=1npl), and x=w/t into (3.5), it is simplified to
(3.6)Cj(π)-Ci(π′)=pita{[1-(1+λx)a]-λ[1-(1+x)a]}.(1)
Supposepi≤pj, then we have λ≥1 and x≥0. From Lemma 3.1, we have Cj(π)-Ci(π′)≥0. This completes the proof of (1).(2)
From case (1) and Lemma 3.2, the result can be easily obtained.Theorem 3.4.
The problem1∣pjr=pj((p0+∑l=1r-1p[l])/(p0+∑l=1npl))a,a≥1∣∑Cj, can be solved optimally by sequencing jobs in nondecreasing order of pj (the SPT rule).Proof.
It is similar to the proof of Theorem3.3 except what follows.
Supposepi≤pj, then
(3.7)Ci(π)+Cj(π)-Ci(π′)-Cj(π′)=2(pi-pj)(p0+∑l=1r-1p[l]p0+∑l=1npl)a+pj(p0+∑l=1r-1p[l]+pip0+∑l=1npl)a-pi(p0+∑l=1r-1p[l]+pjp0+∑l=1npl)a.
By substituting t=(p0+∑l=1r-1p[l])/(p0+∑l=1npl), λ=pj/pi, w=pi/(p0+∑l=1npl) and x=w/t into the (3.7), it is simplified to
(3.8)Ci(π)+Cj(π)-Ci(π′)-Cj(π′)=pita{1-λ+[1-(1+λx)a]-λ[1-(1+x)a]}.
Since λ≥1, x≥0 and Lemma 3.2, (3.8) is nonpositive. Then we have
(3.9)Ci(π)+Cj(π)≤Ci(π′)+Cj(π′).
This completes the proof.However, in spite of increasing efforts to tackle the problem1∣pjr=pj((p0+∑l=1r-1p[l])/(p0+∑l=1npl))a,0<a<1∣∑Cj, it cannot be solved optimally by sequencing jobs in nondecreasing order of pj (the SPT rule) or by sequencing jobs in nonincreasing order of pj (the LPT rule).Example 3.5.
n=3, p0=1, p1=1, p2=2, p3=3, and the learning rate index a=0.5. The SPT sequence is {J1,J2,J3}, ∑Cj(SPT)=3.716. The LPT sequence is {J3,J2,J1}, ∑Cj(LPT)=3.572. However, the optimal sequence is {J3,J1,J2}, ∑Cj(OPT)=3.569.From Example3.5, if 0<a<1, we know that the classical SPT rule or LPT rule cannot give an optimal solution for the total completion time minimization problem. It remains an open problem. Now, we prove that the problem 1∣pjr=pj((p0+∑l=1r-1p[l])/(p0+∑l=1npl))a,0<a<1∣∑Cj, has an important property, that is, the optimal schedule is V-shaped with respect to the normal job processing times. Before the proof, we first present the definition of the V-shaped policy.Definition 3.6 (see [30]).
Schedule isV-shaped with respect to normal job processing times if jobs are arranged in descending order if they are placed before the job with the smallest pj but in ascending order if placed after it.Theorem 3.7.
For the problem1∣pjr=pj((p0+∑l=1r-1p[l])/(p0+∑l=1npl))a,0<a<1∣∑Cj, an optimal schedule exists, which is V-shaped with respect to the normal job processing times.Proof.
Consider a scheduleπ with three consecutive jobs, Ji, Jj, and Jj, that is, π=[S1,Ji,Jj,Jk,S2], where S1 and S2 are partial sequences, such that pj>pi and pj>pk. We show that an interchange between Ji and Jj or between Jj and Jk reduces the value of total completion time. Let π1 be the schedule obtained from π by interchanging Ji and Jj, that is, π1=[S1,Jj,Ji,Jk,S2]. Similarly, let π2 be the schedule obtained from π by interchanging Jj and Jk, that is, π2=[S1,Ji,Jk,Jj,S2]. Furthermore, we assume that there are r-1 jobs in S1. Thus, Ji, Jj, and Jk are the rth, (r+1)th and (r+2)th jobs, respectively, in π. Likewise, Jj, Ji, and Jk(Ji, Jk and Jj) are scheduled in the rth, (r+1)th, and (r+2)th positions in π1(π2). To further simplify the notation, let A denote the completion time of the last job in S1. Then the contribution of the three jobs to the total completion time is
(3.10)Δ(π)=3A+3pi(p0+∑l=1r-1p[l]p0+∑l=1npl)a+2pj(p0+∑l=1r-1p[l]+pip0+∑l=1npl)a+pk(p0+∑l=1r-1p[l]+pi+pjp0+∑l=1npl)a.
Similar expressions are easily obtained for π1 and π2:
(3.11)Δ(π1)=3A+3pj(p0+∑l=1r-1p[l]p0+∑l=1npl)a+2pi(p0+∑l=1r-1p[l]+pjp0+∑l=1npl)a+pk(p0+∑l=1r-1p[l]+pi+pjp0+∑l=1npl)a,Δ(π2)=3A+3pi(p0+∑l=1r-1p[l]p0+∑l=1npl)a+2pk(p0+∑l=1r-1p[l]+pip0+∑l=1npl)a+pj(p0+∑l=1r-1p[l]+pi+pkp0+∑l=1npl)a.
It follows that
(3.12)Δ(π)-Δ(π1)=3(pi-pj)(p0+∑l=1r-1p[l]p0+∑l=1npl)a+2pj(p0+∑l=1r-1p[l]+pip0+∑l=1npl)a-2pi(p0+∑l=1r-1p[l]+pjp0+∑l=1npl)a,(3.13)Δ(π)-Δ(π2)=2(pj-pk)(p0+∑l=1r-1p[l]+pip0+∑l=1npl)a+pk(p0+∑l=1r-1p[l]+pi+pjp0+∑l=1npl)a-pj(p0+∑l=1r-1p[l]+pi+pkp0+∑l=1npl)a.
Let λ=pj/pi, t=(p0+∑l=1r-1p[l])/(p0+∑l=1npl), w=pi/(p0+∑l=1npl), and x=w/t, then we have λ≥1 and x≥0. From (3.12) we have
(3.14)Δ(π)-Δ(π1)pita=3(1-λ)+2λ(1+x)a-2(1+λx)a.
Let μ=pj/pk, s=(p0+∑l=1r-1p[l]+pi)/(p0+∑l=1npl), v=pk/(p0+∑l=1npl), and θ=v/s, then we have μ≥1 and θ≥0. From (3.13) we have
(3.15)Δ(π)-Δ(π2)pksa=2(μ-1)+(1+μθ)a-μ(1+θ)a.
Now, let Δ(π)-Δ(π1) be negative; from (3.14) and Lemma 3.1, we have
(3.16)3(1-λ)+2λ(1+x)a-2(1+λx)a<0⇒2(1-λ)+λ(1+x)a-(1+λx)a+(1-λ)+λ(1+x)a-(1+λx)a<0⇒2(1-λ)+λ(1+x)a-(1+λx)a<0⇒2(μ-1)-μ(1+θ)a+(1+μθ)a>0.
Hence we haveΔ(π)-Δ(π2)>0.
Now, letΔ(π)-Δ(π2) be negative; from (3.15) and Lemma 3.1, we have
(3.17)2(μ-1)-μ(1+θ)a+(1+μθ)a<0⇒2(μ-1)-μ(1+θ)a+(1+μθ)a+(μ-1)-μ(1+θ)a+(1+μθ)a<0⇒3(μ-1)-2μ(1+θ)a+2(1+μθ)a<0⇒3(1-λ)+2λ(1+x)a-2(1+λx)a>0.
Hence we haveΔ(π)-Δ(π1)>0.
We conclude that an optimal schedule exists, which isV-shaped with respect to the normal job processing times.


## 4. Conclusion

The main contribution of this paper is that we develop a learning effect model where the actual job processing time is a function of jobs already processed. We show that the single-machine makespan problem remains polynomially solvable under the proposed model. We also show that the total completion time minimization problem fora≥1 remains polynomially solvable under the proposed model. Moreover, for the case of 0<a<1, we show that an optimal schedule of the total completion time minimization problem is V-shaped with respect to normal job processing times. It is suggested that, for future research to investigate this open problem, the sum-of-processing-time-based learning effect should be considered in the context of other scheduling problems, including multimachine and job-shops settings.



---

*Source: 624108-2010-01-31.xml*