# Single-Machine Group Scheduling Problems with General Deterioration and Linear Learning Effects

Authors: Lei Ning; Li Sun
Journal: Mathematical Problems in Engineering
 (2023)

---

## Abstract

In this paper, we introduce a group scheduling model with deterioration and a general linear learning effect. The group setup time is a linear deterioration function of its starting time. The general learning effect is time-dependent and position-dependent. The objectives are to minimize the makespan, total completion time, and total weighted completion time, respectively. We show the problems remain solvable in polynomial time under the proposed model.


---

## Body

## 1. Introduction

Machine scheduling problems with deterioration or learning effect have been paid more attention in recent years. Scheduling with deterioration was first independently introduced by Gupta and Gupta [1] and Browne and Yechiali [2]. Since then, related scheduling models with deterioration have been extensively studied from a variety of perspectives. Gao et al. [3] study a two-agent scheduling on a parallel-batch machine to minimize makespan. Kim and Kim [4] consider single scheduling problems incorporating a rate-modifying activity (RMA) and processing time deterioration rates. For more recent literature involving deterioration, readers can refer to Sánchez–Herrera et al. [5]; Wang et al. [6]; Ding et al. [7]; Zhang et al. [8]; Li et al. [9]; Soleimani et al. [10]; Cheng et al. [11]. Wright [12] and Biskup [13] are among the pioneers that brought the topic of learning into the field of scheduling. Since then, the learning effect has been widely employed in management science. Jemmali and Hidri [14] investigate a parallel machine scheduling model with DeJong’s learning effect. Bai et al. [15] address a flow shop scheduling problem with a learning effect to optimize maximum lateness. Cheng et al. [11] introduce the optimization scheduling problems of batch operations with batch-position-dependent learning effect and aging effect. For more recent scheduling papers with learning effect, the readers are suggested to refer to the studies by Yang and Lu [16]; Jiang et al. [17]; Rudek [18]; Jiang et al. [19]; Wu et al. [20]; Bai et al. [15]; Li et al. [9]; and Li et al. [21].In many manufacturing processes, the production efficiency can be increased by grouping various parts and products with similar designs or production processes. This phenomenon is known as group technology in the literature. Group technology layout is widely used in modern enterprise production layout, which is to use group technology to improve production efficiency. Many advantages have been claimed through the wide applications of group technology in industrial production, such as the studies by Yin et al. [22]; Zhang et al. [23]; Sun et al. [24]; Costa et al. [25]; Bai et al. [26], consider single-machine group scheduling problems with learning effect and deterioration at the same time. They show the makespan minimization problem can be solved polynomially. Under a certain assumption, they show the total completion time minimization problem can be solved polynomially too. In this paper, we study another group scheduling model with deterioration and general linear learning effects. In our model, the actual group setup time is followed as that in Bai et al. [26]; and the actual processing time of job Jij scheduled in the rth position is linear function of the general learning effect. We will give polynomial time algorithm for the makespan minimization problem. And, we will prove the total completion time minimization problem is also polynomially solvable under certain conditions.The remaining part is organized as follows: In Section2, a precise formulation of the problem is given. We consider the makespan minimization problem in Section 3. The total completion time minimization problem is discussed in Section 4. We study the total weighted completion time minimization problem in Section 5. Section 6 contains some conclusion.


## 2. Problem Formulation

There aren jobs which are classified into m groups and will be processed on a single-machine. All jobs are available at time t, t≥0 and jobs preemption is not allowed. A group setup time is required if the machine switches to process from one group to another group. Jobs in the same group are processed consecutively and need no setup time. The machine can handle one job at a time. We assume that the actual setup time of group Gi is si=θi+δit,i=1,2,…,m, where θi is the basic (normal) setup time, δi is the setup deterioration rate, and t is the starting setup time of group Gi. If job Jij in group Gi is scheduled in the r th position of group Gi, then the actual job processing time is(1)pijrA=pijαfi∑l=1r−1pil+βgir,i=1,2,…,m,j=1,2,3,…,ni,r=1,2,3,…,ni,where pij is the basic (normal) processing time, 0≤α≤1, 0≤β≤1, and α+β=1. fi:0,+∞⟶0,1 is a differentiable nonincreasing function and fi0=1. gi:1,+∞⟶0,1 is a nonincreasing function with gi1=1. It is the Wang [27] model if pijrA=pijαfi∑l=1r−1pil+βgir=pij1+∑l=1r−1pila, the Wang et al. [28] model if pijrA=pijαfi∑l=1r−1pil+βgir=pijra. The weight of Jij is wij. The objectives are to find the optimal job sequence in each group and the optimal group sequence so that the makespan, the total completion time, and the total weighted completion time are minimized, respectively. LEgl denotes the general linear learning effect. Using the three-field notation for scheduling problems, we denote our problems as(2)1GT,si=θi+δit,LEglCmax,1GT,si=θi+δit,LEgl∑Cij,1GT,si=θi+δit,LEgl∑wijCij.Before proving the problems, a lemma is introduced as follows.Lemma 1 (see [29]).
The sum of products∑j=1nxjyj is minimized if sequence x1,x2,…,xn is ordered in a nondecreasing manner and sequence y1,y2,…,yn is ordered in a nonincreasing manner or vice versa, and it is maximized if the sequences are ordered in the same way.


## 3. Makespan Minimization

In this section, we consider the group scheduling problem to minimize the makespan under the new model.Theorem 1.
For the1GT,si=θi+δit,LEglCmax problem, the optimal schedule is obtained by sequencing the jobs in each group in nondecreasing order of pij, i.e., pi1≤pi2≤,…,≤pini,i=1,2,3,…,m (the SPT rule).Proof.
Without loss of generality, we assume the starting time of groupGi in a sequence π is t0. Hence,(3)Ciniπ=θi+1+δit0+∑l=1nipilαfi∑r=1l−1pir+βgil.Here, the first part θi+1+δit0 is a constant. Therefore, to minimize the makespan is to minimize ∑r=1nipilαfi∑r=1l−1pir+βgil. ∑r=1nipilαfi∑r=1l−1pir+βgil can be viewed as the scalar product of two vectors, and ui=αfi∑l=1ni−1pil+βgini is already sorted in nonincreasing order. From Lemma 1, the pij should be sorted in nondecreasing order. Based on the above analysis, the optimal job sequence in each group can be obtained by the shortest normal processing time first (the SPT rule).Theorem 2.
For the1GT,si=θi+δit,LEglCmax problem, the groups are arranged in nondecreasing order of θi+∑l=1nipilαfi∑r=1l−1pir+βgil/δi,i=1,2,…,m.Proof.
LetS1 and S2 be two job schedules where the difference between S1 and S2 is a pairwise interchange of two adjacent groups Gi and Gj. That is, S1=π1,Gi,Gj,π2, S2=π1,Gj,Gi,π2, where π1 and π2 are partial sequences and π1 and π2 may be empty. Furthermore, we assume that t denote the completion time of the last job in π1. To show S1 dominates S2, it is sufficient to show CjnjS1≤CiniS2 and ChuS1≤ChuS2 for any job Jhu in π2. By definition, the job’s completion times of group Gi and group Gj in S1 are given by the following equation:(4)Ci1S1=θi+1+δit+pi1Ci2S1=θi+1+δit+pi1+pi2αfipi1+βgi2⋯CiniS1=θi+1+δit+∑l=1nipilαfi∑r=1l−1pir+βgil.
By substituting(5)Aik=∑l=1kpilαfi∑r=1l−1pir+βgil,k=1,2,…,ni,Ajk=∑l=1kpjlαfj∑r=1l−1pjr+βgjl,k=1,2,…,nj.
Hence,(6)CiniS1=θi+1+δit+AiniCj1S1=θj+1+δjCiniS1+pj1⋯CjnjS1=Cjnj−1S1+pjnjαfj∑l=1nj−1pjl+βgjnj=θj+1+δjθi+1+δit+Aini+Ajnj.
The job’s completion times of groupGj and group Gi in S2 are given by the following equation:(7)Cj1S2=θj+1+δjt+pj1⋯CjnjS2=Cjnj−1S2+pjnjαfj∑l=1nj−1pjl+βgjnj=θj+1+δjt+Ajnj,Ci1S2=θi+1+δiCjnjS2+pi1⋯CiniS2=Cini−1S2+pinifiα∑l=1ni−1pil+βgini=θi+1+δiθj+1+δjt+Ajnj+Aini.
Taking the difference between equations (6) and (7), the following is obtained:(8)CiniS2−CjnjS1=θi+1+δiθj+1+δjt+Ajnj+Aini−θj+1+δjθi+1+δit+Aini+Ajnj.
To haveCiniS2−CjnjS1≥0, if and only if(9)θj+Ajnjδj≥θi+Ainiδii.e.,θj+∑l=1njpjlαfj∑r=1l−1pjr+βgjlδj≥θi+∑l=1njpilαfj∑r=1l−1pirαfi+βgilδi.
Without loss of generality, supposeJh1 is the first job in π2.
Hence,(10)Ch1S1=θh+1+δhCjnjS1+ph1,Ch1S2=θh+1+δhCiniS2+ph1.
IfCiniS2≥CjnjS1, it is easy to obtain Ch1S2≥Ch1S1. Therefore, we have shown that the first job Jh1 in S1, which starts earlier in π2, completes earlier in π2. Similarly, we have ChuS1≤ChuS2 for any job Jhu in π2. This completes the proof.
From Theorems1 and 2, the problem 1GT,si=θi+δit,LEglCmax can be solved by Algorithm 1.Algorithm 1.
Step 1. Jobs in each group are scheduled in nondecreasing order of the normal processing time pij, i.e., pi1≤pi2≤,…,≤pini,i=1,2,3,…,m (the SPT rule)Step 2. Calculate λGi=θi+∑l=1nipilαfi∑r=1l−1pir+βgil/δi,i=1,2,…,mStep 3. Groups are scheduled in nondecreasing order of λGi, i.e. λG1≤λG2≤λG3≤,…,≤λGm
Obviously, it is easy to show that the total time complexity for Algorithm1 is Onlogn.Example 1.
We consider six jobs are divided into three groups andpijrA=pijαfi∑l=1r−1pil+βgir=pij1−∑l=1r−1pil/∑l=1nipilai, ai>1. The basic job and group processing times, the group deterioration rates, and job’s learning effect rates are given, respectively, as follows:(11)p11=5,p12=12,p21=6,p31=17,p32=2,p33=25,a1=1.1,a2=1.5,a3=1.3,θ1=5,θ2=10,θ3=2,δ1=0.3,δ2=0.7,δ3=0.5.
For the1GT,si=θi+δit,LEglCmax problem, we suppose the start time is t=0.Solution 1.
According to Algorithm1, we solve the example as follows:Step 1: in groupG1, the optimal job sequence is J11⟶J12.In groupG2, the optimal job sequence is J21.In groupG3, the optimal job sequence is J32⟶J31⟶J33.Step 2: calculateλG1=54.602, λG2=22.857, λG3=27.558. It is easy to say λG2<λG3<λG1. Therefore, the optimal group sequence is G2⟶G3⟶G1 and the optimal schedule is J21⟶J32⟶J31⟶J33⟶J11⟶J12. The completion times of the job are C21=16, C32=28, C31=33.215, C33=37.779, C11=59.113, and C12=65.493, and the makespan is Cmax=65.493.


## 4. Total Completion Time Minimization

In this section, we consider the group schedule to minimize total completion time. In our model, we will consider this problem with the agreeable condition.Theorem 3.
For the1GT,si=θi+δit,LEgl∑Cij problem, the optimal schedule is obtained by sequencing the jobs of each group in nondecreasing order of pij, i.e., pi1≤pi2≤,…,≤pini,i=1,2,…,m (the SPT rule).Proof.
Without loss of generality, we assume that the starting time of groupGi in a sequence π is t0. Hence,(12)∑l=1niCilπ=niθi+1+δit0+∑l=1nipilni−lαfi∑r=1l−1pir+βgil.Here, niθi+1+δit0 is a constant. Therefore, to minimize ∑l=1niCilπ is equivalent to minimize ∑l=1nipilni−lαfi∑r=1l−1pir+βgil. ∑l=1nipilni−lαfi∑r=1l−1pir+βgil can be viewed as the scalar product of two vectors. The ni−lαfi∑l=1l−1pil+βgil is already sorted in nonincreasing order. From Lemma 1, the pij should be sorted in nondecreasing order. Based on the above analysis, the optimal job sequence of each group can be obtained by the shortest normal processing time first (the SPT rule).Theorem 4.
For the1GT,si=θi+δit,LEgl∑Cij problem, the optimal group sequence are arranged in nondecreasing order of φGi, if φGi and ωGi are in agreeable condition, i.e., ωGi≥ωGj implies φGi≥φGj, φGi=θi+∑l=1nipilαfi∑r=1l−1pir+βgil/ni1+δi, and ωGi=δi/ni1+δi.Proof.
Here, we still use the same notations as that in the proof of Theorem2. To show S1 dominates S2, it suffices to show ∑l=1niCilS1+∑l=1njCjlS1≤∑l=1njCjlS2+∑l=1niCilS2 and ChuS1≤ChuS2 for any job Jhu in π2.
From Theorem2, the total completion times of group Gi and group Gj in S1 are obtained as follows:(13)∑l=1niCilS1+∑l=1njCjlS1=niθi+1+δit+∑l=1niAil+njθj+1+δjθi+1+δit+Aini+∑l=1njAjl,and the total completion times of group Gi and group Gj in S2 are obtained as follows:(14)∑l=1njCjlS2+∑l=1niCilS2=njθj+1+δjt+∑l=1njAjl+niθi+1+δiθj+1+δjt+Ajnj+∑l=1niAil.
Hence, we have the following equation:(15)∑l=1njCjlS2+∑l=1niCilS2−∑l=1niCilS1−∑l=1njCjlS1=ni1+δiδj−nj1+δjδit+ni1+δiθj+Ajnj−nj1+δjθi+Aini.
To obtain∑l=1njCjlS2+∑l=1niCilS2−∑l=1niCilS1−∑l=1njCjlS1≥0 when t≥0.
If and only if,(16)ni1+δiδj−nj1+δjδi≥0,(17)ni1+δiθj+Ajnj−nj1+δjθi+Aini≥0.
From the case of equation (16), we have δj/nj1+δj≥δi/ni1+δi, i.e., ωGj≥ωGi.
And, from the result of equation (17), we can obtain θj+Ajnj/nj1+δj≥θi+Aini/ni1+δi, i.e., φGj≥φGi. From Theorem 2, it is easy to have ChuS1≤ChuS2 for any job Jhu in π2. Therefore, if φGi and ωGi are under agreeable condition, the optimal sequence between groups are arranged in nondecreasing order of φGi. This completes the proof.
From Theorems3 and 4, if φGi and ωGi are under agreeable condition, the problem 1GT,si=θi+δit,LEgl∑Cij can be solved by Algorithm 2.Algorithm 2.
Step 1. Jobs in each group are scheduled in nondecreasing order of the normal processing time pij, i.e., pi1≤pi2≤,…,≤pini,i=1,2,…,m (the SPT rule)Step 2. Calculate φGi=θi+∑l=1nipilαfi∑r=1l−1pir+βgil/ni1+δi,i=1,2,…,mStep 3. Groups are scheduled in nondecreasing order of φGi, i.e., φG1≤φG2≤φG3≤,…,≤φGm
Obviously, it is easy to show that the total time complexity for Algorithm2 is Onlogn. We conjecture the general version of minimizing total completion time is NP-hard. Therefore, the two following special cases are shown to be polynomially solvable.Special case 1.
Suppose the numbers of jobs in each group and the setup deterioration rates of groups are the same, respectively, that is,ni=n¯, δi=δ,i=1,2,…,m.
The model reduces to1GT,si=θi+δt,ni=n¯,LEgl∑Cij. From Theorems 3 and 4, the problem can be solved by Algorithm 3.Algorithm 3.
Step 1. Jobs in each group are scheduled in nondecreasing order of the normal processing time pij, i.e., pi1≤pi2≤,…,≤pini,i=1,2,3,…,m (the SPT rule)Step 2. Calculate φ1Gi=θi+∑l=1nipilαfi∑r=1l−1pir+βgil,i=1,2,…,mStep 3. Groups are scheduled in nondecreasing order of φ1Gi, i.e., φ1G1≤φ1G2≤φ1G3≤,…,≤φ1Gm
Obviously, it is easy to show that the total time complexity for Algorithm3 is Onlogn.Special case 2.
Suppose the setup deterioration rates of groups are zero. The model reduces to1GT,si=θi,LEgl∑Cij. From Theorems 3 and 4, the problem can be solved by Algorithm 4.Algorithm 4.
Step 1. Jobs in each group are scheduled in nondecreasing order of the normal processing time pij, i.e., pi1≤pi2≤,…,≤pini,i=1,2,3,…,m (the SPT rule)Step 2. Calculate φ2Gi=θi+∑l=1nipilαfi∑r=1l−1pir+βgil/ni,i=1,2,…,mStep 3. Groups are scheduled in nondecreasing order of φ2Gi, i.e., φ2G1≤φ2G2≤φ2G3≤,…,≤φ2Gm
Obviously, it is easy to show that the total time complexity for Algorithm4 is Onlogn.Example 2.
We still consider the above example. For the1GT,si=θi+δit,LEgl∑Cij problem, we suppose the start time is t=0.Solution 2.
According to Algorithm2, we solve the example as follows:Step 1: in groupG1, the optimal job sequence is J11⟶J12.In groupG2, the optimal job sequence is J21.In groupG3, the optimal job sequence is J32⟶J31⟶J33.Step 2: calculate:ωG1=0.115, ωG2=0.412, and ωG3=0.111 and φG1=6.3, φG2=9.412, and φG3=3.062. Hence, ωG3<ωG1<ωG2 and φG3<φG1<φG2. Therefore, the optimal group sequence is G3⟶G1⟶G2 and the optimal schedule is J32⟶J31⟶J33⟶J11⟶J12⟶J21. The completion times of jobs are C32=4, C31=9.215, C33=13.779, C11=27.913, C12=34.293, and C21=74.299, and the sum of completion times is ∑Cij=4+9.215+13.779+27.913+34.293+74.299=163.498.


## 5. Total Weighted Completion Time Minimization

In this section, we consider the group scheduling problem to minimize the total weighted completion time. In our model, we will consider this problem with the agreeable condition.Theorem 5.
For the1GT,si=θi+δit,LEgl∑wijCij problem, if the jobs in each group have disagreeable weights, i.e., pij≥pik implies wij≤wik for the jobs Jij and Jik, the optimal schedule is obtained by sequencing the jobs of each group in nondecreasing order of pij/wij, i.e., pi1/wi1≤pi2/wi2≤,…,≤pini/wini, i=1,2,…,m (the WSPT rule).Proof.
The problem of job sequence in each group reduces to a single machine scheduling problem with a learning effect. By carrying out a pairwise interchange of adjacent jobs, the result can be easy to obtain. Therefore, we omit it.Theorem 6.
For the1GT,si=θi+δit,LEgl∑wijCij problem, if the jobs in each group have disagreeable weights, i.e., pij≥pik implies wij≤wik for the jobs Jij and Jik, and if μGi and ηGi are in agreeable condition for group Gi, i.e., μGi≥μGj implies ηGi≥ηGj, μGi=θi+∑l=1nipilαfi∑r=1l−1pir+βgil/∑l=1njwil1+δi, ηGi=δi/∑l=1niwil1+δi, i=1,2,…,m. the optimal group schedule is obtained by sequencing the groups in non-decreasing order of ηGi.Proof.
Here, we still use the same notations as in the proof of Theorem2. To show S1 dominates S2, it suffices to show that ∑l=1niwilCilS1+∑l=1njwjlCjlS1≤∑l=1njwjlCjlS2+∑l=1niwilCilS2 and ChuS1≤ChuS2 for any job Jhu in π2.
From Theorem2, we have the following equation:(18)∑l=1njwjlCjlS2+∑l=1niwilCilS2−∑l=1niwilCilS1−∑l=1njwjlCjlS1=∑l=1niwil1+δiδj−∑l=1njwjl1+δjδit+∑l=1niwil1+δiθj+Ajnj−∑l=1njwjl1+δjθi+Aini.
To obtain∑l=1njwjlCjlS2+∑l=1niwilCilS2−∑l=1niwilCilS1−∑l=1njwjlCjlS1≥0 when t≥0.
If and only if,(19)∑l=1niwil1+δiθj+Ajnj−∑l=1njwjl1+δjθi+Aini≥0,(20)∑l=1niwil1+δiδj−∑l=1njwjl1+δjδi≥0.
From the case of equation (19), we have the following equation:(21)θj+Ajnj∑l=1njwjl1+δj≥θi+Aini∑l=1niwil1+δi,i.e.,μGj≥μGi,and from equation (20), we can obtain the following equation:(22)δj∑l=1njwjl1+δj≥δi∑l=1niwil1+δi,i.e.,ηGj≥ηGi.
From Theorem2, it is easy to have ChuS1≤ChuS2 for any job Jhu in π2. Therefore, if μGi and ηGi are under agreeable condition, the optimal sequence between groups are arranged in nondecreasing order of ηGi. This completes the proof.
From Theorems5 and 6, if the jobs in each group have disagreeable weights and μGi and ηGi are under agreeable condition for group Gii=1,2,…,m, the problem 1GT,si=θi+δit,LEgl∑wijCij can be solved by Algorithm 5.Algorithm 5.
Step 1. Jobs in each group are scheduled in nondecreasing order of the normal processing time pij/wij, i.e., pi1≤pi2≤,…,≤pini,i=1,2,…,m (the WSPT rule)Step 2. Calculate ηGi=δi/∑l=1niwil1+δi,i=1,2,…,mStep 3. Groups are scheduled in nondecreasing order of ηGi, i.e., ηG1≤ηG2≤ηG3≤,…,≤ηGm
Obviously, it is easy to show that the total time complexity for Algorithm2 is Onlogn.Example 3.
We still consider the above-given example. Six jobs are divided into three groups andpijrA=pijαfi∑l=1r−1pil+βgir=pij1−∑l=1r−1pil/∑l=1nipilai, ai>1. The basic job and group processing times, the group deterioration rates, and job’s learning effect rates and weight are given, respectively, as follows:(23)p11=5,p12=12,p21=6,p31=17,p32=2,p33=25,a1=1.1,a2=1.5,a3=1.3,θ1=5,θ2=10,θ3=2,δ1=0.3,δ2=0.7,δ3=0.5,w11=6,w12=3,w21=4,w31=4,w32=9,w33=1.
For the1GT,si=θi+δit,LEgl∑wijCij problem, we suppose the start time is t=0. Obviously, the jobs in each group have disagreeable weights.Solution 3.
According to Algorithm5, we solve the example as follows:Step 1: in groupG1, the optimal job sequence is J11⟶J12.In groupG2, the optimal job sequence is J21.In groupG3, the optimal job sequence is J32⟶J31⟶J33.Step 2: calculateμG1=1.5539, μG2=2.3529, μG3=1.5234 and ηG1=0.0256, ηG2=0.1029, and ηG3=0.0238. Hence, μG3<μG1<μG2 and ηG3<ηG1<ηG2. Therefore, the optimal group sequence is G3⟶G1⟶G2 and the optimal schedule is J32⟶J31⟶J33⟶J11⟶J12⟶J21. The completion times of jobs are C32=11, C31=12.0489, C33=12.0813, C11=25.7057, C12=33.8863, and C21=73.6067, and the sum of completion times is ∑wijCij=709.5968.


## 6. Conclusions

In this paper, we study single-machine group scheduling problems with deterioration and general linear learning effect simultaneously. The objectives are to minimize the makespan, the total completion time, and the total weighted completion time. We first show that the makespan minimization problem is polynomially solvable for our model. Meanwhile, we prove the total completion time minimization and the total weighted completion time minimization remain polynomially solvable under agreeable conditions. Future research may investigate more general deteriorating and learning models under other environments or consider other objective functions.



---

*Source: 1455274-2023-01-17.xml*