# Group Scheduling Problems with Time-Dependent and Position-Dependent DeJong’s Learning Effect

Authors: Li Sun; Lei Ning; Jia-zhen Huo
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

In this paper, we introduce a group scheduling model with time-dependent and position-dependent DeJong’s learning effect. The objectives of scheduling problems are to minimize makespan, the total completion time, and the total weighted completion time, respectively. We show that the problems remain solvable in polynomial time under the proposed model.


---

## Body

## 1. Introduction

In classical scheduling problems, the scheduling models routinely assume that job processing times are known and fixed throughout the period of production process. However, this assumption may be unrealistic in many situations that the processing time of jobs may be shortened due to learning effect over time. Production scheduling problems with learning effect have been paid much attention in recent years. To the best of our knowledge, there is little research that considers position-dependent and time-dependent processing time group scheduling model. Besides, the existing learning effect scheduling model suffers the drawback that when a job’s position or the starting processing time is sufficiently large in a schedule, its actual processing time is close to zero (infinity). This paper is to introduce a new scheduling model with position-dependent and time-dependent processing time, which overcomes the above shortcomings and is more general and realistic than the models existing in the literature.The remaining part of this paper is organized as follows. In Section2, we present a brief review of the existing scheduling model with learning effect. In Section 3, a precise formulation of the problem is given. Section 4 considers several single-machine scheduling problems with position-dependent and time-dependent DeJong’s learning effect to minimize makespan, the total completion time, and the total weighted completion time, respectively. The last section contains some conclusions of our model.


## 2. Review of Existing Models

Wright [1]; Biskup [2]; and Cheng and Wang [3] are among the pioneers that brought the learning effect into the field of scheduling research. Since then, learning effect has been widely employed in management science. To overcome the shortcoming associated with Wright’s [1] definition of learning effect that the improvement of learning effect is infinite, DeJong [4] introduced a new learning scheduling model, which is more realistic. Wang et al. [5] studied time-dependent DeJong’s learning effect model pjrA=pjαa∑i=1r−1pi+β, where α≥0, β≥0, and 0<a≤1 are the parameters obtained empirically and α+β=1. Other studies have validated DeJong’s learning model, e.g., Okolowski and Gawiejnowicz [6] and Ji et al. [7, 8]. More recent papers which have considered scheduling problems with learning effect include studies of Wang and Wang and Wang [9, 10]; Wang et al. [11]; Xu et al. [12]; Chen et al. [13]; Toksari and Arik [14]; Bai et al. [15]; Mustu and Eren [16]; Pei et al. [17]; Zhang et al. [18]; Wang and Wang [19, 20]; Wang et al. [21], and Przybylski [22].In many production processes, the efficiency can be improved by grouping various parts and products with similar designs. This phenomenon is known as group technology in the literature. Many advantages have been claimed through the wide applications of group technology, for instance, Ji et al. [23] and Wang and Liu [24]. For the latest results on group scheduling problems, we refer the reader to the studies of Zhang et al. [18, 25]; Wang and Wang [26]; and Lu et al. [27] among others.


## 3. Problem Formulation

We first define the notations which are used throughout this paper, followed by the descriptions of the problems:m: the number of groups m≥2ni: the number of jobs in group Gi, i=1,2,…,mn: the total number of jobs, i.e., n1+n2+⋯+nm=nGi: group Gi, i=1,2,…,mGi: group scheduled in the ith position in a sequence, i=1,2,…,mJij: the job scheduled in the jth position in group Gipij: the normal processing time of job Jij, i=1,2,…,m, j=1,2,3,…,nipij: the normal processing time of job Jij scheduled in the jth position of group Gi in a sequence, i=1,2,…,m and j=1,2,…,nisi: the sequence-independent setup time of group Gi, i=1,2,…,mpijA: the actual processing time of job Jij scheduled in the jth position of the ith group Gi in a sequence, i=1,2,…,m and j=1,2,3,…,niThere aren independent jobs. All jobs are classified into m groups G1,G2,…,Gm by the similarities and to be processed on a single machine. All the jobs are available at time zero, and job preemption is not allowed. A group setup time is required if the machine switches to process from one group to another. Jobs in the same group are processed consecutively and need no setup time. The machine can handle one job at a time. Each job Jij has a normal processing time pij. The actual processing time of job will be shorter than its normal processing time due to the learning effect.In this paper, we consider the following new time-dependent and position-dependent model:(1)pirA=pirM+1−Matirrb,i=1,2,…,m,r=1,2,3,…,ni,where 0<a<1, b<0 is the learning index, tir is the total normal processing times of all jobs scheduled before Jir in group Gi, i.e., tir=∑j=1r−1pij. M represents “the factor of incompressibility” (0≤M≤1). If M=0, the model simplifies to the classical learning model pjr=pjra. If M=1, the processing time of job is constant. The objectives are to find the optimal job sequence in each group and the optimal group sequence such that makespan, the total completion time, and the total weighted completion time are minimized, respectively. Using the three-field notation for scheduling problem, we denote our problems as(2)1GT,si,pirA=pirM+1−MatirrbCmax,1GT,si,pirA=pirM+1−Matirrb∑Cij,1GT,si,pirA=pirM+1−Matirrb∑wijCij.Before proving the problems, some lemmas are introduced as follows.Lemma 1.
LetFx,r=1−axr+1/rb/x, where r≥1, x>0, 0<a<1, and b<0. Then, Fx,r is a decreasing function for all x>0.Proof.
Taking the first derivative ofFx,r with respect to x, the following is obtained:(3)∂Fx,r∂x=axr+1/rb1−xlna−1x2.
Let(4)fx,r=axr+1rb1−xlna−1.
Taking the first derivative offx,r with respect to x, the following is obtained:(5)∂fx,r∂x=−axr+1rbln2a.
Sincer≥1, x>0, 0<a<1, and b<0, we have −axr+1/rbln2a<0. Hence, fx,r is a decreasing function for all x>0. Therefore, fx,r<f0,r. From f0,r=r+1/rb−1<0, we obtain fx,r<0. Hence, ∂Fx,r/∂x<0 and Fx,r is a decreasing function for all x>0.Lemma 2.
If the functionhx is a differentiable convex function for a<b<c, then(6)1hb−ha=h′ξ1b−a,a<ξ1<b,1hc−ha=h′ξ2c−a,a<ξ2<c,1h′ξ1≤h′ξ2.Proof.
From the Lagrange mean value theorem, the lemma can be easily obtained.


## 4. Result of Optimization

In this section, we address the application of our model to solve the single-machine group scheduling problems involving makespan minimization, the total completion time minimization, and the total weighted completion time minimization.


### 4.1. Makespan Minimization

Theorem 1.
For the1GT,si,pirA=pirM+1−MatirrbCmax problem, the optimal schedule is obtained: (i) the job sequence in each group is in the smallest normal processing time order (SPT) and (ii) the groups can be sequenced in any order.Proof.
Suppose a sequence isG1,G2,…,Gm. Therefore, the makespan of the sequence is obtained as follows:(7)Cmax=∑i=1msi+∑i=1m∑j=1nipijM+1−Ma∑h=1j−1pihjb.
The first term of equation (7) is a constant. The value of the second term of equation (7) is determined by the job sequence in each group. Therefore, the makespan minimization of the studied model is independent of the sequence of group. Hence, the optimal group sequence can be scheduled in any order, so (ii) follows.
Next, we determine the optimal job sequence in each group to minimize the makespan by implementing the adjacent job exchange argument. Letπ1 and π1′ be two job schedules of a group Gi where the difference between π1 and π1′ is a pairwise interchange of two adjacent jobs Jik and Jil. That is, π1=S1,Jik,Jil,S2 and π1′=S1,Jil,Jik,S2, where S1 and S2 are the partial sequences. The positions of Jik and Jil in sequence π1 are r and r+1, respectively, which are reverse in sequence π1′. Furthermore, we assume that t denotes the completion time of the last job in S1 and pik≤pil. To prove π1 dominates π1′, it suffices to show that Cilπ1≤Cikπ1′ and Ciuπ1≤Ciuπ1′ for any job Jiu in S2. By definition, the completion time periods of jobs Jik and Jil in sequence π1 and π1′ are given by(8)Cikπ1=t+pikM+1−Ma∑h=1r−1pihrb,Cilπ1=t+pikM+1−Ma∑h=1r−1pihrb+pilM+1−Ma∑h=1r−1pih+pikr+1b,Cilπ1′=t+pilM+1−Ma∑h=1r−1pihrb,Cikπ1′=t+pilM+1−Ma∑h=1r−1pihrb+pikM+1−Ma∑h=1r−1pih+pilr+1b.
Thus, we can obtain(9)Cikπ1′−Cilπ1=1−Ma∑h=1r−1pihrbpikpil1−apikr+1/rbpik−1−apilr+1/rbpil.
Frompik≤pil and Lemma 1, it is easy to obtain that Cikπ1′−Cilπ1≥0. Hence, we have Cilπ1≤Cikπ1′.
SupposeJij is the first job in S2, we have(10)Cijπ1=Cilπ1+pijM+1−Ma∑h=1r−1pih+pil+pikr+2b,Cijπ1′=Cikπ1′+pijM+1−Ma∑h=1r−1pih+pil+pikr+2b.
FromCilπ1≤Cikπ1′, we have Cijπ1≤Cijπ1′ and Ciuπ1≤Ciuπ1′ for any job Jiu in S2.
Repeating the job interchange argument for all jobs in each group not sequenced in the SPT order yields part (i) of Theorem1 and we complete the proof of Theorem 1.
From Theorem1, the problem 1GT,si,pirA=pirM+1−MatirrbCmax can be solved by using Algorithm 1.Algorithm 1.
Step 1. Jobs in each group are scheduled in nondecreasing order of the normal processing time (the SPT order)Step 2. Groups are scheduled in any order
We address application of Algorithm1 in the following example.Example 1.
There are five jobs classified into two groupsG1 and G2. M=0.5, a=1/2, b=−1, G1=J11,J12, s1=8, p11=2, p12=6, G2=J21,J22,J23, s2=4, p21=10, p22=5, and p23=2.
For the problem1GT,si,pirA=pirM+1−MatirrbCmax, by Algorithm 1, we solve this example as follows:Step 1. In groupG1, the optimal job sequence is J11⟶J12. In group G2, the optimal job sequence is J23⟶J22⟶J21.Step 2. Groups are scheduled in any order. Therefore, the optimal schedule isJ11⟶J12⟶J23⟶J22⟶J21 or J23⟶J22⟶J21⟶J11⟶J12.
Hence, the minimum makespan is as follows:(11)Cmax=s1+p12A+p12A+s2+p21A+p22A+p23A=27.20.


### 4.2. Total Completion Time Minimization

Theorem 2.
For the1GT,si,pirA=pirM+1−Matirrb∑Cij problem, the optimal schedule is obtained: (i) the job sequence in each group is in the smallest normal processing time order (SPT) and (ii) the groups can be sequenced in nondecreasing order of θi, where(12)θi=si+∑l=1nipilM+1−Ma∑h=1l−1pihlbni.Proof.
We still use the notation of Theorem1 to prove the optimal job sequence in each group. From the proof of Theorem 1, we have Cikπ1≤Cilπ1′ and Cilπ1≤Cikπ1′. Hence, it is obtained that Cikπ1+Cilπ1≤Cilπ1′+Cikπ1′ and π1 dominates π1′. Therefore, we complete the proof of part (i).
Next, we determine the optimal group sequence. Letπ2 and π2′ be two schedules where the difference between π2 and π2′ is a pairwise interchange of two adjacent groups Gi and Gj and job sequence in each group of π2 and π2′ is in SPT order. That is, π2=δ1,Gi,Gj,δ2 and π2′=δ1,Gj,Gi,δ2, where δ1 and δ2 are the partial sequences. Furthermore, denote t as the completion time of the last job in δ1. To prove π2 dominates π2′, it suffices to address ∑l=1niCilπ2+∑l=1njCjlπ2≤∑l=1njCjlπ2′+∑l=1niCilπ2′. By definition, the completion times of jobs of groups Gi and Gj in π2 are given by(13)Ci1π2=t+si+pi1,Ci2π2=t+si+pi1+pi2M+1−Mapi12b,Ciniπ2=t+si+∑l=1nipilM+1−Ma∑h=1l−1pihlb,Cj1π2=Ciniπ2+sj+pj1,Cjnjπ2=Ciniπ2+sj+∑l=1njpjlM+1−Ma∑h=1l−1pihlb.
The completion times of jobs of groupsGj and Gi in π2′ are given by(14)Cj1π2′=t+sj+pj1,Cj2π2′=t+sj+pj1+pj2M+1−Mapj12b,Cjnjπ2′=t+sj+∑l=1njpjlM+1−Ma∑h=1l−1pjhlb,Ci1π2′=Cjnjπ2′+si+pi1,Ciniπ2′=Cjnjπ2′+si+∑l=1nipilM+1−Ma∑h=1l−1pjhlb.
Thus, we have(15)∑l=1njCjlπ2′+∑l=1niCilπ2′−∑l=1niCilπ2−∑l=1njCjlπ2=nisj+∑l=1njpjlM+1−Ma∑h=1l−1pjhlb−njsi+∑l=1nipilM+1−Ma∑h=1l−1pjhlb.
We have∑l=1niCilπ2+∑l=1njCjlπ2≤∑l=1njCjlπ2′+∑l=1niCilπ2′, if and only if(16)si+∑l=1nipilM+1−Ma∑h=1l−1pihlbni≤sj+∑l=1njpjlM+1−Ma∑h=1l−1pihlbnj.
This completes the proof.
From Theorem2, the problem 1GT,si,pirA=pirM+1−Matirrb∑Cij can be solved by the following algorithm:Algorithm 2.
Step 1. Jobs in each group are scheduled in a nondecreasing order of the normal processing time (the SPT order).Step 2. To each group, calculate(17)θi=si+∑l=1nipilM+1−Ma∑h=1l−1pihlbni,i=1,2,…,m.Step 3. Groups are scheduled in the nondecreasing order ofθi.
Obviously, it is easy to show that the total time for Algorithm2 is Onlogn.
We show application of Algorithm2 in the following example.Example 2.
As seen in Example1, we change the objective to the total completion time minimization. By Algorithm 2, we solve the problem as follows:Step 1: In groupG1, the optimal job sequence is J11⟶J12. In group G2, the optimal job sequence is J23⟶J22⟶J21.Step 2: To groupsG1 and G2, calculate(18)θ1=8+2∗0.5+0.5∗1/20∗1−1+6∗0.5+0.5∗1/22∗2−12=6.69,θ2=4+2∗0.5+0.5∗1/20∗1−1+5∗0.5+0.5∗1/22∗2−1+10∗0.5+0.5∗1/27∗3−13=4.61.
Therefore, the optimal group sequence isG2⟶G1 and the optimal schedule is J23⟶J22⟶J21⟶J11⟶J12.
Hence, the minimum total completion time is∑Cij=79.65.


### 4.3. Total Weighted Completion Time Minimization

In our model, we consider the group scheduling to minimize the total weighted completion time if jobs in each group satisfy an agreeable condition.Theorem 3.
For the1GT,si,pirA=pirM+1−Matirrb∑wijCij problem, if jobs in each group have agreeable weighted normal processing time, i.e., pij≤pil implies wij≥wil, for all jobs Jij and Jil in Gi, i=1,2,…,m. The optimal schedule satisfies the following: (i) the job in each group is in nondecreasing order of pij/wij(the WSPT order) and (ii) the groups can be sequenced in the nondecreasing order of φi, where(19)φi=si+∑l=1nipilM+1−Ma∑h=1l−1pihlb∑h=1niwil.Proof.
First, we show the optimal job sequence in each group. Without loss of generality, we still use the notation of Theorem1. From Theorem 1 and pik≤pil, we have wik≥wil. Therefore,(20)wikCikπ1′+wilCilπ1′−wikCikπ1−wilCilπ1=wik+wilpil−pikM+1−Ma∑h=1r−1pihrb+wikpikM+1−Ma∑h=1r−1pih+pilr+1b−wilpilM+1−Ma∑h=1r−1pih+pikr+1b=wik+wilpil−pikM+1−Ma∑h=1r−1pihrb+wikpikM+1−Ma∑h=1r−1pih+pilr+1b−wikpikM+1−Ma∑h=1r−1pihr+1b−wilpilM+1−Ma∑h=1r−1pih+pikr+1b+wilpilM+1−Ma∑h=1r−1pihr+1b+wikpik−wilpilM+1−Ma∑h=1r−1pihr+1b≥wikpil−wilpikM+1−Ma∑h=1r−1pihr+1b+wikpikM+1−Ma∑h=1r−1pih+pilr+1b−wikpikM+1−Ma∑h=1r−1pihr+1b−wilpilM+1−Ma∑h=1r−1pih+pikr+1b+wilpilM+1−Ma∑h=1r−1pihr+1b=wikpil−wilpikM+1−Ma∑h=1r−1pihr+1b+wikh′ξ1−wilh′ξ2pikpil.
From Lemma2, it is easy to show h′ξ1≥h′ξ2. Since pik≤pil and wik≥wil, it can be obtained wikCikπ1+wilCilπ1≤wikCikπ1′+wilCilπ1′. From Theorem 1, we have Ciuπ1≤Ciuπ1′ for any job Jiu in S2. Hence, the job completion time of S2 in π1 is earlier than the same job completion time of S2 in π1′. Thus, the job in each group is in nondecreasing order of pij/wij(the WSPT order) in the optimal schedule. This completes the proof of part (i).
Next, determine the optimal group sequence. We still use the notation of Theorem2. To prove π2 dominates π2′, it suffices to show that(21)∑l=1niwilCilπ2+∑l=1njwjlCjlπ2≤∑l=1njwjlCjlπ2′+∑l=1niwilCilπ2′,For∑l=1njwjlCjlπ2′+∑l=1niwilCilπ2′−∑l=1niwilCilπ2−∑l=1njwjlCjlπ2=∑l=1niwilsj+∑l=1njpjlM+1−Ma∑h=1l−1pjhlb−∑l=1njwjlsi+∑l=1nipilM+1−Ma∑h=1l−1pjhlb.
We have∑l=1niwilCilπ2+∑l=1njwjlCjlπ2≤∑l=1njwjlCjlπ2′+∑l=1niwilCilπ2′, if and only if(22)si+∑l=1nipilM+1−Ma∑h=1l−1pihlb∑l=1niwil≤sj+∑l=1njpjlM+1−Ma∑h=1l−1pihlb∑l=1njwjl.
Hence, the optimal groups can be sequenced in the nondecreasing order ofφi, and this completes the proof of the theorem.
From Theorem3, if wij and pij for jobs in each group have agreeable weighted normal processing time, the problem 1GT,si,pirA=pirM+1−Matirrb∑wijCij can be solved by the following algorithm:Algorithm 3.
Step 1. Jobs in each group are scheduled in nondecreasing order ofpij/wij(the WSPT order).Step 2. Calculate(23)φi=si+∑l=1nipilM+1−Ma∑h=1l−1pihlb∑l=1niwil,i=1,2,…,m.Step 3. Groups are scheduled in nondecreasing order ofφi.
Obviously, it is easy to show that the total time for Algorithm3 is Onlogn.
We present application of Algorithm3 in the following example.Example 3.
Also turn to the Example1, change the objective to the total weighted completion time minimization (w11=2, w12=1, w21=1, w22=2, and w23=4). Obviously, jobs in each group of this instance have the agreeable weighted normal processing times in Theorem 3. By Algorithm 3, we solve the problem as follows:Step 1: In groupG1, the optimal job sequence is J11⟶J12. In group G2, the optimal job sequence is J23⟶J22⟶J21.Step 2: To groupsG1. and G2, calculate(24)φ1=8+2∗0.5+0.5∗1/20∗1−1+6∗0.5+0.5∗1/22∗2−13=4.46,φ2=4+2∗0.5+0.5∗1/20∗1−1+5∗0.5+0.5∗1/22∗2−1+10∗0.5+0.5∗1/27∗3−17=1.98.
Therefore, the optimal group sequence isG2⟶G1 and the optimal schedule is J23⟶J22⟶J21⟶J11⟶J12.
Hence, the minimum total weighted completion time is∑wijCij=122.28.


## 4.1. Makespan Minimization

Theorem 1.
For the1GT,si,pirA=pirM+1−MatirrbCmax problem, the optimal schedule is obtained: (i) the job sequence in each group is in the smallest normal processing time order (SPT) and (ii) the groups can be sequenced in any order.Proof.
Suppose a sequence isG1,G2,…,Gm. Therefore, the makespan of the sequence is obtained as follows:(7)Cmax=∑i=1msi+∑i=1m∑j=1nipijM+1−Ma∑h=1j−1pihjb.
The first term of equation (7) is a constant. The value of the second term of equation (7) is determined by the job sequence in each group. Therefore, the makespan minimization of the studied model is independent of the sequence of group. Hence, the optimal group sequence can be scheduled in any order, so (ii) follows.
Next, we determine the optimal job sequence in each group to minimize the makespan by implementing the adjacent job exchange argument. Letπ1 and π1′ be two job schedules of a group Gi where the difference between π1 and π1′ is a pairwise interchange of two adjacent jobs Jik and Jil. That is, π1=S1,Jik,Jil,S2 and π1′=S1,Jil,Jik,S2, where S1 and S2 are the partial sequences. The positions of Jik and Jil in sequence π1 are r and r+1, respectively, which are reverse in sequence π1′. Furthermore, we assume that t denotes the completion time of the last job in S1 and pik≤pil. To prove π1 dominates π1′, it suffices to show that Cilπ1≤Cikπ1′ and Ciuπ1≤Ciuπ1′ for any job Jiu in S2. By definition, the completion time periods of jobs Jik and Jil in sequence π1 and π1′ are given by(8)Cikπ1=t+pikM+1−Ma∑h=1r−1pihrb,Cilπ1=t+pikM+1−Ma∑h=1r−1pihrb+pilM+1−Ma∑h=1r−1pih+pikr+1b,Cilπ1′=t+pilM+1−Ma∑h=1r−1pihrb,Cikπ1′=t+pilM+1−Ma∑h=1r−1pihrb+pikM+1−Ma∑h=1r−1pih+pilr+1b.
Thus, we can obtain(9)Cikπ1′−Cilπ1=1−Ma∑h=1r−1pihrbpikpil1−apikr+1/rbpik−1−apilr+1/rbpil.
Frompik≤pil and Lemma 1, it is easy to obtain that Cikπ1′−Cilπ1≥0. Hence, we have Cilπ1≤Cikπ1′.
SupposeJij is the first job in S2, we have(10)Cijπ1=Cilπ1+pijM+1−Ma∑h=1r−1pih+pil+pikr+2b,Cijπ1′=Cikπ1′+pijM+1−Ma∑h=1r−1pih+pil+pikr+2b.
FromCilπ1≤Cikπ1′, we have Cijπ1≤Cijπ1′ and Ciuπ1≤Ciuπ1′ for any job Jiu in S2.
Repeating the job interchange argument for all jobs in each group not sequenced in the SPT order yields part (i) of Theorem1 and we complete the proof of Theorem 1.
From Theorem1, the problem 1GT,si,pirA=pirM+1−MatirrbCmax can be solved by using Algorithm 1.Algorithm 1.
Step 1. Jobs in each group are scheduled in nondecreasing order of the normal processing time (the SPT order)Step 2. Groups are scheduled in any order
We address application of Algorithm1 in the following example.Example 1.
There are five jobs classified into two groupsG1 and G2. M=0.5, a=1/2, b=−1, G1=J11,J12, s1=8, p11=2, p12=6, G2=J21,J22,J23, s2=4, p21=10, p22=5, and p23=2.
For the problem1GT,si,pirA=pirM+1−MatirrbCmax, by Algorithm 1, we solve this example as follows:Step 1. In groupG1, the optimal job sequence is J11⟶J12. In group G2, the optimal job sequence is J23⟶J22⟶J21.Step 2. Groups are scheduled in any order. Therefore, the optimal schedule isJ11⟶J12⟶J23⟶J22⟶J21 or J23⟶J22⟶J21⟶J11⟶J12.
Hence, the minimum makespan is as follows:(11)Cmax=s1+p12A+p12A+s2+p21A+p22A+p23A=27.20.


## 4.2. Total Completion Time Minimization

Theorem 2.
For the1GT,si,pirA=pirM+1−Matirrb∑Cij problem, the optimal schedule is obtained: (i) the job sequence in each group is in the smallest normal processing time order (SPT) and (ii) the groups can be sequenced in nondecreasing order of θi, where(12)θi=si+∑l=1nipilM+1−Ma∑h=1l−1pihlbni.Proof.
We still use the notation of Theorem1 to prove the optimal job sequence in each group. From the proof of Theorem 1, we have Cikπ1≤Cilπ1′ and Cilπ1≤Cikπ1′. Hence, it is obtained that Cikπ1+Cilπ1≤Cilπ1′+Cikπ1′ and π1 dominates π1′. Therefore, we complete the proof of part (i).
Next, we determine the optimal group sequence. Letπ2 and π2′ be two schedules where the difference between π2 and π2′ is a pairwise interchange of two adjacent groups Gi and Gj and job sequence in each group of π2 and π2′ is in SPT order. That is, π2=δ1,Gi,Gj,δ2 and π2′=δ1,Gj,Gi,δ2, where δ1 and δ2 are the partial sequences. Furthermore, denote t as the completion time of the last job in δ1. To prove π2 dominates π2′, it suffices to address ∑l=1niCilπ2+∑l=1njCjlπ2≤∑l=1njCjlπ2′+∑l=1niCilπ2′. By definition, the completion times of jobs of groups Gi and Gj in π2 are given by(13)Ci1π2=t+si+pi1,Ci2π2=t+si+pi1+pi2M+1−Mapi12b,Ciniπ2=t+si+∑l=1nipilM+1−Ma∑h=1l−1pihlb,Cj1π2=Ciniπ2+sj+pj1,Cjnjπ2=Ciniπ2+sj+∑l=1njpjlM+1−Ma∑h=1l−1pihlb.
The completion times of jobs of groupsGj and Gi in π2′ are given by(14)Cj1π2′=t+sj+pj1,Cj2π2′=t+sj+pj1+pj2M+1−Mapj12b,Cjnjπ2′=t+sj+∑l=1njpjlM+1−Ma∑h=1l−1pjhlb,Ci1π2′=Cjnjπ2′+si+pi1,Ciniπ2′=Cjnjπ2′+si+∑l=1nipilM+1−Ma∑h=1l−1pjhlb.
Thus, we have(15)∑l=1njCjlπ2′+∑l=1niCilπ2′−∑l=1niCilπ2−∑l=1njCjlπ2=nisj+∑l=1njpjlM+1−Ma∑h=1l−1pjhlb−njsi+∑l=1nipilM+1−Ma∑h=1l−1pjhlb.
We have∑l=1niCilπ2+∑l=1njCjlπ2≤∑l=1njCjlπ2′+∑l=1niCilπ2′, if and only if(16)si+∑l=1nipilM+1−Ma∑h=1l−1pihlbni≤sj+∑l=1njpjlM+1−Ma∑h=1l−1pihlbnj.
This completes the proof.
From Theorem2, the problem 1GT,si,pirA=pirM+1−Matirrb∑Cij can be solved by the following algorithm:Algorithm 2.
Step 1. Jobs in each group are scheduled in a nondecreasing order of the normal processing time (the SPT order).Step 2. To each group, calculate(17)θi=si+∑l=1nipilM+1−Ma∑h=1l−1pihlbni,i=1,2,…,m.Step 3. Groups are scheduled in the nondecreasing order ofθi.
Obviously, it is easy to show that the total time for Algorithm2 is Onlogn.
We show application of Algorithm2 in the following example.Example 2.
As seen in Example1, we change the objective to the total completion time minimization. By Algorithm 2, we solve the problem as follows:Step 1: In groupG1, the optimal job sequence is J11⟶J12. In group G2, the optimal job sequence is J23⟶J22⟶J21.Step 2: To groupsG1 and G2, calculate(18)θ1=8+2∗0.5+0.5∗1/20∗1−1+6∗0.5+0.5∗1/22∗2−12=6.69,θ2=4+2∗0.5+0.5∗1/20∗1−1+5∗0.5+0.5∗1/22∗2−1+10∗0.5+0.5∗1/27∗3−13=4.61.
Therefore, the optimal group sequence isG2⟶G1 and the optimal schedule is J23⟶J22⟶J21⟶J11⟶J12.
Hence, the minimum total completion time is∑Cij=79.65.


## 4.3. Total Weighted Completion Time Minimization

In our model, we consider the group scheduling to minimize the total weighted completion time if jobs in each group satisfy an agreeable condition.Theorem 3.
For the1GT,si,pirA=pirM+1−Matirrb∑wijCij problem, if jobs in each group have agreeable weighted normal processing time, i.e., pij≤pil implies wij≥wil, for all jobs Jij and Jil in Gi, i=1,2,…,m. The optimal schedule satisfies the following: (i) the job in each group is in nondecreasing order of pij/wij(the WSPT order) and (ii) the groups can be sequenced in the nondecreasing order of φi, where(19)φi=si+∑l=1nipilM+1−Ma∑h=1l−1pihlb∑h=1niwil.Proof.
First, we show the optimal job sequence in each group. Without loss of generality, we still use the notation of Theorem1. From Theorem 1 and pik≤pil, we have wik≥wil. Therefore,(20)wikCikπ1′+wilCilπ1′−wikCikπ1−wilCilπ1=wik+wilpil−pikM+1−Ma∑h=1r−1pihrb+wikpikM+1−Ma∑h=1r−1pih+pilr+1b−wilpilM+1−Ma∑h=1r−1pih+pikr+1b=wik+wilpil−pikM+1−Ma∑h=1r−1pihrb+wikpikM+1−Ma∑h=1r−1pih+pilr+1b−wikpikM+1−Ma∑h=1r−1pihr+1b−wilpilM+1−Ma∑h=1r−1pih+pikr+1b+wilpilM+1−Ma∑h=1r−1pihr+1b+wikpik−wilpilM+1−Ma∑h=1r−1pihr+1b≥wikpil−wilpikM+1−Ma∑h=1r−1pihr+1b+wikpikM+1−Ma∑h=1r−1pih+pilr+1b−wikpikM+1−Ma∑h=1r−1pihr+1b−wilpilM+1−Ma∑h=1r−1pih+pikr+1b+wilpilM+1−Ma∑h=1r−1pihr+1b=wikpil−wilpikM+1−Ma∑h=1r−1pihr+1b+wikh′ξ1−wilh′ξ2pikpil.
From Lemma2, it is easy to show h′ξ1≥h′ξ2. Since pik≤pil and wik≥wil, it can be obtained wikCikπ1+wilCilπ1≤wikCikπ1′+wilCilπ1′. From Theorem 1, we have Ciuπ1≤Ciuπ1′ for any job Jiu in S2. Hence, the job completion time of S2 in π1 is earlier than the same job completion time of S2 in π1′. Thus, the job in each group is in nondecreasing order of pij/wij(the WSPT order) in the optimal schedule. This completes the proof of part (i).
Next, determine the optimal group sequence. We still use the notation of Theorem2. To prove π2 dominates π2′, it suffices to show that(21)∑l=1niwilCilπ2+∑l=1njwjlCjlπ2≤∑l=1njwjlCjlπ2′+∑l=1niwilCilπ2′,For∑l=1njwjlCjlπ2′+∑l=1niwilCilπ2′−∑l=1niwilCilπ2−∑l=1njwjlCjlπ2=∑l=1niwilsj+∑l=1njpjlM+1−Ma∑h=1l−1pjhlb−∑l=1njwjlsi+∑l=1nipilM+1−Ma∑h=1l−1pjhlb.
We have∑l=1niwilCilπ2+∑l=1njwjlCjlπ2≤∑l=1njwjlCjlπ2′+∑l=1niwilCilπ2′, if and only if(22)si+∑l=1nipilM+1−Ma∑h=1l−1pihlb∑l=1niwil≤sj+∑l=1njpjlM+1−Ma∑h=1l−1pihlb∑l=1njwjl.
Hence, the optimal groups can be sequenced in the nondecreasing order ofφi, and this completes the proof of the theorem.
From Theorem3, if wij and pij for jobs in each group have agreeable weighted normal processing time, the problem 1GT,si,pirA=pirM+1−Matirrb∑wijCij can be solved by the following algorithm:Algorithm 3.
Step 1. Jobs in each group are scheduled in nondecreasing order ofpij/wij(the WSPT order).Step 2. Calculate(23)φi=si+∑l=1nipilM+1−Ma∑h=1l−1pihlb∑l=1niwil,i=1,2,…,m.Step 3. Groups are scheduled in nondecreasing order ofφi.
Obviously, it is easy to show that the total time for Algorithm3 is Onlogn.
We present application of Algorithm3 in the following example.Example 3.
Also turn to the Example1, change the objective to the total weighted completion time minimization (w11=2, w12=1, w21=1, w22=2, and w23=4). Obviously, jobs in each group of this instance have the agreeable weighted normal processing times in Theorem 3. By Algorithm 3, we solve the problem as follows:Step 1: In groupG1, the optimal job sequence is J11⟶J12. In group G2, the optimal job sequence is J23⟶J22⟶J21.Step 2: To groupsG1. and G2, calculate(24)φ1=8+2∗0.5+0.5∗1/20∗1−1+6∗0.5+0.5∗1/22∗2−13=4.46,φ2=4+2∗0.5+0.5∗1/20∗1−1+5∗0.5+0.5∗1/22∗2−1+10∗0.5+0.5∗1/27∗3−17=1.98.
Therefore, the optimal group sequence isG2⟶G1 and the optimal schedule is J23⟶J22⟶J21⟶J11⟶J12.
Hence, the minimum total weighted completion time is∑wijCij=122.28.


## 5. Conclusions

We study new group scheduling models with position-dependent and time-dependent learning effect. The actual processing time of a job is a function of the total normal processing time and the total number of jobs scheduled ahead of it, which is motivated by DeJong’s learning schedule model. We show that the models can be solved polynomially when the objectives are the makespan minimization and the total completion time minimization. The total weighted completion time minimization is proved to be solved in polynomial time under an agreeable condition. It is suggested for future research to extend to other more practical learning effect scheduling models in the other machine environment, including multimachine and job-shop settings.



---

*Source: 5161872-2020-02-17.xml*