# Single-Machine Scheduling with Accelerating Learning Effects

Authors: T. C. E. Cheng; Shih-Chang Tseng; Peng-Jen Lai; Wen-Chiung Lee
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

Scheduling with learning effects has been widely studied. However, there are situations where the learning effect might accelerate. In this paper, we propose a new model where the learning effect accelerates as time goes by. We derive the optimal solutions for the single-machine problems to minimize the makespan, total completion time, total weighted completion time, maximum lateness, maximum tardiness, and total tardiness.


---

## Body

## 1. Introduction

In classical scheduling, the processing times of the jobs are assumed to be constant over the entire planning horizon [1]. However, this assumption may not be appropriate for all the cases [2–5]. In many realistic situations, because the employees do the same job repeatedly, they learn how to do similar jobs more efficiently. As a result, the actual processing time of a job is shorter if it is scheduled later, rather than earlier in the sequence. This phenomenon is known as the “learning effect” and has been applied in scheduling problems. Dondeti and Mohanty [6], Biskup [7], Cheng and Wang [8], and Gawiejnowicz [9] are among the pioneers that incorporate the learning effect into scheduling problems. Dondeti and Mohanty [6] consider a single-machine scheduling problem in which the machine experiences learning as it continues to work. Biskup [7] points out that the learning effect in scheduling may arise in firms that produce similar jobs. Cheng and Wang [8] study a single-machine scheduling problem in which the job processing times will decrease as a result of learning. Since then, a number of researchers have considered the effects of learning in different scheduling settings, including single-machine scheduling, two-machine flowshop scheduling, and parallel machine scheduling. Cheng et al. [10], Gawiejnowicz [11], Biskup [12], and Rustogi and Strusevich [13] provide comprehensive reviews of scheduling models with time-dependent processing times.Recently, Janiak and Rudek [14] introduce a new learning effect model into the scheduling field where learning is generalized in two ways. First, they allow each job to have a different learning effect to the operator. Second, they assume that the job processing time is a nonincreasing k-stepwise function, which in general is not restricted to a certain learning curve; hence, it can accurately fit every possible shape of a learning function. Wang et al. [15] consider some single-machine problems with a time-dependent learning effect. They find the optimal solutions or derive the worst-case error bounds for some proposed heuristic algorithms. Janiak and Rudek [16] consider and analyze a learning effect model in which the learning curve is S-shaped. They provide the NP-hard proofs for two cases of the problem to minimize the makespan. Lee and Wu [17] observe that robots with neural networks are used in computers, motor vehicles, and many assembly lines. The actions of a robot are constantly modified through self-learning in processing jobs. On the other hand, the operators in the control centre learn how to give commands efficiently through work experience. This motivates the consideration of both “position-based” and “sum-of-processing-time-based” learning effects simultaneously. Combining the models of Biskup [7] and Koulamas and Kyparisis [18], Cheng et al. [19] introduce a model with position-based and sum-of-processing-timed-based learning effects in which the actual processing time of a job is a function of the total normal processing times of the jobs already processed and of the job position in a schedule. Wu and Lee [20] study the problem with learning effects to minimize the total completion time in a multiple machine permutation flowshop. Janiak and Rudek [21] suggest a new approach, called multiability learning, which generalizes the existing ones and models more precisely real-life settings. They focus on the problem with the proposed learning model to minimize the makespan and provide optimal polynomial time algorithms for some special cases. Cheng et al. [22] develop a learning effect model where the actual job processing time is a logarithm function of the normal processing time of jobs already processed. They provide the optimal solutions for some single-machine problems. Lee et al. [23] consider a single-machine bi-criterion problem with learning effects and job release times. Wang et al. [24] study some single-machine problems with past-sequence-dependent setup times. Lee et al. [25] investigate a single-machine problem with the learning effect and release times to minimize the makespan. Ji and Cheng [26] consider a scheduling problem with job-dependent learning effects and multiple rate-modifying activities. They show that the problem to minimize the total completion time remains polynomially solvable. Wu and Lee [27] and Yin et al. [28] further generalize the model proposed by Cheng et al. [19]. Zhang and Yan [29] modify the models of Cheng et al. [19] and Wu and Lee [27] and provide the optimal solutions for some single-machine and flowshop problems. Wang et al. [30] and Wang and Wang [31] provide the optimal solutions for some single-machine problems with an exponential sum-of-actual-processing-time-based learning effect. Okołowski and Gawiejnowicz [32] consider a parallel-machine scheduling problem with DeJong’s learning effect. For the makespan problem, they propose a sequential branch-and-bound algorithm and a parallel branch-and-bound algorithm. Wang et al. [33] consider resource allocation scheduling with learning effects where the processing time of a job is a function of the job’s position in a sequence and its resource allocation. They provide a polynomial algorithm to find the optimal job sequence and resource allocation. Hsu et al. [34] and Kuo et al. [35] study the total completion time problem on unrelated parallel machines with past-sequence-dependent setup times and learning effects. Zhu et al. [36] investigate some single-machine group scheduling problems with resource allocation and learning effects. Rudek [37] provide the computational complexity and solution algorithms for flowshop scheduling problems with the learning effect. Lai and Lee [38] propose a learning effect model where the actual processing time of a job is a general function of the normal processing times of the jobs already processed and the job’s own scheduled position.Biskup [12] classifies the existing models into two different approaches, namely, position-based learning effect and sum-of-processing-time-based learning effect models. He points out that position-based learning corresponds to situations where learning arises from processing-time independent operations like setting up machines. This is a realistic assumption for the case because the actual processing times of the jobs are mainly machine-driven. The sum-of-processing-time-based approach takes into account the experience that workers gain from producing the jobs. This might, for example, be the case for offset printing, where running the press itself is a highly complicated and error-prone process. In some precision manufacturing environments, such as the aircraft manufacturing industry, new employees must spend long time to become skilled workers. In this case, the learning effect is not evident in the early stage because of the low learning rate at that stage, but the learning rate will gradually increase as employees become skilled. In other words, the learning rate accelerates over time. This phenomenon also exists in labour-intensive industries, such as hand-made umbrellas, fans, and embroidery, in which craftsmen need to learn and perfect their crafts over a long period of time practising their skills. In this study we propose a scheduling model with the learning effect that might accelerate.The remainder of this paper is organized as follows. We present the solution procedures for the single-machine problems to minimize the makespan, total completion time, total weighted completion time, maximum lateness, maximum tardiness, and total tardiness in Section2. We conclude the paper in Section 3.


## 2. Some Single-Machine Problems

There aren jobs ready to be processed on a single machine. For each job j, there is a normal processing time pj, a due date dj, and a weight wj. Due to the learning effect as in [39], the actual processing time of job j if it is scheduled in the rth position of a sequence is
(1)pj[r]=pj(1+∑k=1r-1αr,kp[k])a,
for r=1,2,…,n, where a<0, p[k] denotes the normal processing time of the job scheduled in the kth position of the sequence and αr,i≤αr,j if i<j and αr,j≥αr′,j≥0 if r>r′. Throughout the paper, let Cj, Lj=Cj-dj, and Tj=max{0,Cj-dj} denote the completion time, lateness, and tardiness of job j, respectively. In addition, we let Cmax=max{Cj}, Lmax=max{Lj}, and Tmax=max{Tj}. Using the well-known three-field notation for describing scheduling problems, we denote the problems under study as 1|pj[r]=pj(1+∑k=1r-1αr,kp[k])a|Cmax, 1|pj[r]=pj(1+∑k=1r-1αr,kp[k])a|∑Ci, 1|pj[r]=pj(1+∑k=1r-1αr,kp[k])a|∑wiCi, 1|pj[r]=pj(1+∑k=1r-1αr,kp[k])a|Lmax, 1|pj[r]=pj(1+∑k=1r-1αr,kp[k])a|Tmax, and 1|pj[r]=pj(1+∑k=1r-1αr,kp[k])a|∑Ti, respectively.Before presenting the main results, we first state some lemmas that will be used in the proofs in the sequel.Lemma 1.
(
θ
-
1
)
(
1
+
c
+
u
)
a
-
θ
(
1
+
u
+
λ
t
)
a
+
(
1
+
u
+
λ
θ
t
)
a
≥
0 for a<0, θ≥1, λ≥0, c<0, t≥0, u>0, and 1+c+u≥0.Proof.
LetF(t)=(θ-1)(1+c+u)a-θ(1+u+λt)a+(1+u+λθt)a. Taking the first derivative of F(t) with respect to t, we have
(2)F′(t)=aλθ{(1+u+λθt)a-1-(1+u+λt)a-1}≥0.
Since a<0 and θ≥1, F(t) is a nondecreasing function so F(t)≥F(0)≥0. This completes the proof.Lemma 2.
(
1
+
u
+
c
)
a
(
1
-
θ
)
+
λ
2
θ
(
1
+
u
+
λ
t
)
a
-
λ
1
(
1
+
u
+
λ
θ
t
)
a
≤
0 for a<0, θ≥1, λ≥0, c<0, t≥0, 0≤λ2≤λ1≤1, u>0, and 1+c+u≥0.Proof.
LetF(θ)=(θ-1)(1+u+c)a+λ1(1+u+θt)a-λ2θ(1+u+t)a. To show that F(θ) is nonnegative, it suffices to show that F′(θ)≥0 because F(1)=(1+u+t)a(λ1-λ2)≥0. Taking the first derivative of F(θ) with respect to θ, we have
(3)F′(θ)=(1+u+c)a+aλ1t(1+u+θt)a-1-λ2(1+u+t)a.
Since a<0, u>0, t≥0, and λ1≥0, we have
(4)F′(θ)≥(1+u+c)a+aλ1t(1+u+t)a-1-λ2(1+u+t)a=F′(1).
To show that F′(1)≥0, we define the following function:
(5)G(ξ,η)=(1+u+c)a+atη(1+u+t)a-1-ξ(1+u+t)a.
First, we claim that G(1,1)≥0. We have
(6)G(1,1)=(1+u+c)a+at(1+u+t)a-1-(1+u+t)a=(1+u+c)a-(1+u)a+(1+u)a-(1+u+t)a+at(1+u+t)a-1.
By the mean value theorem, there exists a σ with 0≤σ≤1 such that
(7)(1+u)a-(1+u+t)a=-ta(1+u+σt)a-1.
It follows that
(8)G(1,1)=(1+u+c)a-(1+u)a-ta(1+u+σt)a-1+at(1+u+t)a-1.
Since a<0, we have (1+u+c)a≥(1+u)a and (1+u+σt)a-1≥(1+u+t)a-1 for 0≤σ≤1. Thus, G(1,1)≥0 and the claim is proved.
SinceG(ξ,η) is nonincreasing with respect to ξ and η, we have G(ξ,η)≥G(1,1)≥0. This implies that F′(1)=G(λ2,λ1) is nonnegative. Thus, we have F′(θ)≥F′(1)≥0 and the proof is completed.We prove the following properties using the pairwise job interchange technique. Suppose thatS and S′ are two job schedules and the difference between S and S′ is a pairwise interchange of two adjacent jobs i and j. That is, S=(π,i,j,π′) and S′=(π,j,i,π′), where π and π′ each denote a partial sequence. Furthermore, we assume that there are r-1 jobs in π. In addition, let A denote the completion time of the last job in π. Under the proposed model, the completion times of jobs i and j in S and S′ are
(9)Ci(S)=A+pi(1+∑k=1r-1αr,kp[k])a,(10)Cj(S)=A+pi(1+∑k=1r-1αr,kp[k])a+pj(1+∑k=1r-1αr+1,kp[k]+αr+1,rpi)a,(11)Cj(S′)=A+pj(1+∑k=1r-1αr,kp[k])a,(12)Ci(S′)=A+pj(1+∑k=1r-1αr,kp[k])a+pi(1+∑k=1r-1αr+1,kp[k]+αr+1,rpj)a.Property 1.
An optimal schedule for the1|pj[r]=pj(1+∑k=1r-1αr,kp[k])a|Cmax problem is obtained by sequencing the jobs in the shortest processing time (SPT) order.Proof.
Suppose thatpj≥pi. To show that S dominates S′, it suffices to show that Cj(S)≤Ci(S′). Taking the difference between (10) and (12), we have
(13)Ci(S′)-Cj(S)=(pj-pi)(1+∑k=1r-1αr,kp[k])a+pi(1+∑k=1r-1αr+1,kp[k]+αr+1,rpj)a-pj(1+∑k=1r-1αr+1,kp[k]+αr+1,rpi)a.
Substituting u=∑k=1r-1αr+1,kp[k], θ=pj/pi, c=∑k=1r-1(αr,k-αr+1,k)p[k], t=pi, and λ=αr+1,r into (13), we have from Lemma 1 that Cj(S′)≥Ci(S). This completes the proof.Similar to the proof of Property1, we have the following result.Property 2.
An optimal schedule for the problem1|pj[r]=pj(1+∑k=1r-1αr,kp[k])a|∑Ci is obtained by sequencing the jobs in the SPT order.Rudek [40] shows that the total weighted completion time problem with sum-of-processing-time-based learning effects is at least NP-hard. Since it is a special case of our proposed model, the problem to minimize the total weighted completion time under the proposed model is at least NP-hard. Thus, the weighted shortest processing time first (WSPT) rule does not yield the optimal solution under the proposed model. However, we show in the next property that the WSPT rule provides an optimal solution for the total weighted completion time problem if the normal processing times and the weights are agreeable; that is, pi≤pj implies that wi≥wj for all jobs i and j.Property 3.
An optimal schedule for the1|pj[r]=pj(1+∑k=1r-1αr,kp[k])a|∑wiCi problem is obtained by sequencing the jobs in the WSPT order if the normal processing times and the weights are agreeable.Proof.
Suppose thatpi≤pj. From Property 1, we have Cj(S)≤Ci(S′). Thus, to show that S dominates S′, it suffices to show that
(14)wiCi(S)+wjCj(S)≤wjCj(S′)+wiCi(S′).
From (9) to (12), we have
(15)wiCi(S)+wjCj(S)-[wjCj(S′)+wiCi(S′)]=wi(A+pi(1+∑k=1r-1αr,kp[k])a)-wj(A+pj(1+∑k=1r-1αr,kp[k])a)+wj(A+pi(1+∑k=1r-1αr,kp[k])a+pj(1+∑k=1r-1αr+1,kp[k]+αr+1,rpi)a)-[wi(A+pj(1+∑k=1r-1αr,kp[k])a+pi(1+∑k=1r-1αr+1,kp[k]+αr+1,rpj)a)]=(wi+wj)pi[(1+∑k=1r-1αr,kp[k])a(1-pjpi)+wjwi+wjpjpi×(1+∑k=1r-1αr+1,kp[k]+αr+1,rpi)a-wiwi+wj×(1+∑k=1r-1αr+1,kp[k]+αr+1,rpj)a].
Substituting θ=pj/pi, λ1=wi/(wi+wj), λ2=wj/(wi+wj), u=∑k=1r-1αr+1,kp[k], t=pi, c=∑k=1r-1(αr,k-αr+1,k)p[k], and λ=αr+1,r into (15), we have
(16)wiCi(S)+wjCj(S)-[wiCi(S′)+wjCj(S′)]=(wi+wj)pi[(1+u+c)a(1-θ)+λ2θ(1+u+λt)a-λ1(1+u+λθt)a].
From Lemma 2, we have wiCi(S)+wjCj(S)-[wiCi(S′)+wjCj(S′)]≤0. Therefore, repeating this job interchange argument for all the jobs not sequenced in the WSPT order completes the proof for the 1|pj[r]=pj(1+∑k=1r-1αr,kp[k])a|∑wiCi problem.Next, we show that the earliest due date (EDD) rule yields an optimal solution under the proposed models if the normal processing times and due dates are agreeable; that is,di≤dj implies that pi≤pj for all jobs i and j.Property 4.
An optimal schedule for the1|pj[r]=pj(1+∑k=1r-1αr,kp[k])a|Lmax problem is obtained by sequencing the jobs in the EDD order if the normal processing times and due dates are agreeable.Proof.
Suppose thatdi≤dj, which implies that pi≤pj. The maximum lateness among the first r-1  jobs is the same since they are processed in the same order. Since the makespan is minimized by the SPT rule (Property 1), the maximum lateness in the partial sequence π′ of S will not be greater than that in the partial sequence π′ of S′. Thus, to prove that the maximum lateness of S is less than or equal to that of S′, it suffices to show that max{Li(S),Lj(S)}≤Li(S′).
From (9) to (12), we can derive that the lateness of jobs i and j in S is
(17)Li(S)=A+pi(1+∑k=1r-1αr,kp[k])a-di,Lj(S)=A+pi(1+∑k=1r-1αr,kp[k])a+pj(1+∑k=1r-1αr+1,kp[k]+αr+1,rpi)a-dj.
Similarly, the lateness of jobs j and i in S′ is
(18)Lj(S′)=A+pj(1+∑k=1r-1αr,kp[k])a-dj,Li(S′)=A+pj(1+∑k=1r-1αr,kp[k])a+pi(1+∑k=1r-1αr,kp[k]+αr+1,rpj)a-di.
Thus, Li(S)≤Li(S′) since pi≤pj and pi(1+∑k=1r-1αr,kp[k]+αr+1,rpj)a≥0. From Property 1 and di≤dj, we see that Lj(S)≤Li(S′). Thus, S dominates S′. Therefore, repeating this job interchange argument for all the jobs not sequenced in the EDD order completes the proof of the result for the 1|pj[r]=pj(1+∑k=1r-1αr,kp[k])a|Lmax problem.Similar to the proof of Property4, we have the following result.Property 5.
An optimal schedule for the1|pj[r]=pj(1+∑k=1r-1αr,kp[k])a|Tmax problem is obtained by sequencing the jobs in the EDD order if the normal processing times and due dates are agreeable.Property 6.
An optimal schedule for the1|pj[r]=pj(1+∑k=1r-1αr,kp[k])a|∑Ti problem is obtained by sequencing the jobs in the EDD order if the normal processing times and due dates are agreeable.Proof.
Suppose thatdi≤dj, which implies pi≤pj. The total tardiness of the first r-1 jobs is the same since they are processed in the same order. Since the makespan is minimized by the SPT rule (Property 1), the total tardiness of the partial sequence π′ in S will not be greater than that of the partial sequence π′ in S′. Thus, to prove that the total tardiness of S is less than or equal to that of S′, it suffices to show that
(19)Ti(S)+Tj(S)≤Tj(S′)+Ti(S′).
From (9) to (12), we can derive that the tardiness of jobs i and j in S is
(20)Ti(S)=max{A+pi(1+∑k=1r-1αr,kp[k])a-di,0},Tj(S)=max{A+pi(1+∑k=1r-1αr,kp[k])a+pj(1+∑k=1r-1αr+1,kp[k]+αr+1,rpi)a-dj,0}.
Similarly, the tardiness of jobs j and i in S′ is
(21)Tj(S′)=max{A+pj(1+∑k=1r-1αr,kp[k])a-dj,0},Ti(S′)=max{A+pj(1+∑k=1r-1αr,kp[k])a+pi(1+∑k=1r-1αr,kp[k]+αr+1,rpj)a-di,0}.
To compare the total tardiness of jobsi and j in S and S′, we consider two cases. In the first case where A+pj(1+∑k=1r-1αr,kp[k])a≤dj, the total tardiness of jobs i and j in S and in S′ is
(22)Ti(S)+Tj(S)=max{A+pi(1+∑k=1r-1αr,kp[k])a-di,0}+max{A+pi(1+∑k=1r-1αr,kp[k])a+pj(1+∑k=1r-1αr+1,kp[k]+αr+1,rpi)a-dj,0},Tj(S′)+Ti(S′)=max{A+pj(1+∑k=1r-1αr,kp[k])a+pi(1+∑k=1r-1αr,kp[k]+αr+1,rpj)a-di,0}.
Suppose that neitherTi(S) nor Tj(S) is zero. Note that this is the most restrictive case since it comprises the case where either one or both Ti(S) and Tj(S) are zero. From Property 1 and di≤dj, we have
(23){Tj(S′)+Ti(S′)}-{Ti(S)+Tj(S)}=(pj-pi)(1+∑k=1r-1αr,kp[k])a+pi(1+∑k=1r-1αr,kp[k]+αr+1,rpj)a-pj(1+∑k=1r-1αr+1,kp[k]+αr+1,rpi)a+dj-A-pi(1+∑k=1r-1αr,kp[k])a≥0.
Thus, {Tj(S′)+Ti(S′)}-{Ti(S)+Tj(S)}≥0 in the first case. In the second case where A+pj(1+∑k=1r-1αr,kp[k])a>dj, the total tardiness of jobs i and j in S and S′ is
(24)Ti(S)+Tj(S)=max{A+pi(1+∑k=1r-1αr,kp[k])a-di,0}×max{A+pi(1+∑k=1r-1αr,kp[k])a+pj(1+∑k=1r-1αr+1,kp[k]+αr+1,rpi)a-dj,0(1+∑k=1r-1αr,kp[k])a},Tj(S′)+Ti(S′)=2A+2pj(1+∑k=1r-1αr,kp[k])a+pi(1+∑k=1r-1αr,kp[k]+αr+1,rpj)a-di-dj.
Suppose that neitherTi(S) nor Tj(S) is zero. From Property 1, di≤dj and pi≤pj, we have
(25){Tj(S′)+Ti(S′)}-{Ti(S)+Tj(S)}=2(pj-pi)(1+∑k=1r-1αr,kp[k])a+pi(1+∑k=1r-1αr,kp[k]+αr+1,rpj)a-pj(1+∑k=1r-1αr+1,kp[k]+αr+1,rpi)a≥0.
Thus, {Tj(S′)+Ti(S′)}-{Ti(S)+Tj(S)}≥0 in the second case. Thus, S dominates S′. Therefore, repeating this job interchange argument for all the jobs not sequenced in the EDD order completes the proof of the result for the 1|pj[r]=pj(1+∑k=1r-1αr,kp[k])a|∑Ti problem.


## 3. Conclusions

In this paper, we propose a new scheduling model where the learning effect accelerates. We derive the optimal solutions for some single-machine problems. For the makespan and the total completion time problems, we show that the SPT rule yields the optimal schedules. For the total weighted completion time problem, we show that the WSPT rule yields the optimal schedule if the normal processing times and weights are agreeable. Furthermore, we prove that the EDD rule yields the optimal schedules for the maximum lateness, maximum tardiness, and the total tardiness problems if the normal processing times and due dates are agreeable.



---

*Source: 816235-2013-11-14.xml*