# Single-Machine Group Scheduling Problems with Deterioration  to Minimize the Sum of Completion Times

Authors: Yong He; Li Sun
Journal: Mathematical Problems in Engineering
 (2012)

---

## Abstract

We consider two single-machine group scheduling problems with deteriorating group setup and job processing times. That is, the job processing times and group setup times are linearly increasing (or decreasing) functions of their starting times. Jobs in each group have the same deteriorating rate. The objective of scheduling problems is to minimize the sum of completion times. We show that the sum of completion times minimization problems remains polynomially solvable under the agreeable conditions.


---

## Body

## 1. Introduction

In classical scheduling problems, the scheduling models routinely assume that job processing times are known and fixed throughout the period of job processing. However, this assumption may be unrealistic in many situations that the processing times of jobs may be prolonged due to deterioration or shortened due to learning over time. Scheduling with deteriorating jobs was first independently introduced by J. N. D. Gupta and S. K. Gupta [1] and Browne and Yechiali [2]. Since then, related models of scheduling with deteriorating jobs have been extensively studied from a variety of perspectives. Cheng et al. [3] give a detailed review of scheduling problems with deteriorating jobs. More recent papers which have considered scheduling jobs with deteriorating jobs include Wang [4], Voutsinas and Pappis [5], Lee et al. [6], Wang et al. [7], Zhu et al. [8], Cheng et al. [9, 10], Cheng et al. [11], Sun et al. [12], Wei et al. [13], Zhao and Tang [14], and Yin et al. [15, 16].On the other hand, the production efficiency can be increased by grouping various parts and products with similar designs and/or production processes. This phenomenon is known as group technology in the literature. To the best of our knowledge, only a few results concerning scheduling problems with deteriorating effect under group technology are given. Wei and Wang [17] consider single-machine scheduling problems with group technology (GT) and deteriorating jobs. Yang [18] investigate group scheduling problems with simultaneous considerations of learning and deterioration effects on a single-machine setting. The learning phenomenon is implemented to model the setup time of groups. Three models of deteriorating for the job processing time within a group are examined. Bai et al. [19] consider single-machine group scheduling problems with effects of learning and deterioration at the same time. Lee and Lu [20] discuss a single-machine scheduling problem of minimizing the total weighted number of late jobs with deteriorating jobs and setup times. A branch-and-bound with several dominance properties and a lower bound is developed to solve the problem optimally. S. J. Yang and D. L. Yang [21] study two models of learning for the job processing time, they provide polynomial time solutions for the makespan minimization problems. Huang et al. [22] present a single-machine group scheduling problems with both learning effects and deteriorating jobs. Wu and Lee [23] consider a situation where both setup times and job-processing times are lengthened as jobs wait to be processed. Two single-machine group-scheduling problems are investigated where the group setup times and the job-processing times are both increasing functions of their starting times.In this paper, we study the group scheduling model proposed by Lee and Wu [24], who have considered the makespan problems. In our study, we investigate the sum of completion times minimization problem under the same model as Lee and Wu [24]. In addition, we suppose jobs in each group have the same deteriorating rate. Hence, the problems considered will be noted by 1/GTpij=aij±bit, si=θi±δit/∑‍Cij. We show that the problems remain polynomially solvable under the agreeable conditions.The remainder of this paper is organized in four sections. The solution procedure for the linear increasing function problem is given in the next section, and the solution procedure for the linear decreasing function is described in Section3. Then, some examples are offered in Section 4. The conclusion is given in the last section.


## 2. The1/GT, pij=aij+bit, si=θi+δit/∑‍Cij Problem

In this section, we consider the single-machine group scheduling problem with deterioration to minimize the sum of completion times of all jobs. In our model, we follow the notation and terminology used by Lee and Wu [24]. In addition, ai[j] is the basic (normal) processing time of job Ji[j] scheduled in the jth position of group Gi, and Ci[j] is the completion time scheduled in the jth position of group Gi. We suppose the jobs in each group have the same deterioration rate noted by bi.Theorem 2.1.
For the 1/GT,pij=aij+bit, si=θi+δit/∑‍Cij problem, the optimal schedule is obtained by sequencing the jobs in each group in nondecreasing order of ai[j], that is, ai[1]≤ai[2]≤ai[3]≤ai[4]≤⋯≤ai[ni], i=1,2,3,…m, (the SPT rule).Proof.
In the same group, the result can be easily obtained by using interchanging technology and is omitted.Theorem 2.2.
For the 1/GT,pij=aij+bit, si=θi+δit/∑‍Cij problem, the groups are arranged in nondecreasing order of ω(Gi), ω(Gi)=bi((1+bi)ni(1+δi)-1)/(1+bi)((1+bi)ni-1)(1+δi), if ω(Gi) and Bi/Ai have agreeable conditions, that is, ω(Gi)≥ω(Gj) if and only if Bi/Ai≥Bj/Aj, Ai=(1+bi)(1-(1+bi)ni)(1+δi)/(1-(1+bi)), Bi=∑k=1ni(1+bi)ni-kai[k]+(1+bi)niθi.Proof.
Letπ1 and π2 be two job schedules where the difference between π1 and π2 is a pairwise interchange of two adjacent groups Gi and Gj. That is, π1=[S1,Gi,Gj,S2], π2=[S1,Gj,Gi,S2], where S1 and S2 are partial sequences and S1 and S2 may be empty. Furthermore, we assume that t denotes the completion time of the last job in π1. To show π1 dominates π2, it suffices to show that
(2.1)∑l=1niCi[l](π1)+∑l=1njCj[l](π1)≤∑l=1njCj[l](π2)+∑l=1niCi[l](π2).
By definition, the completion times of jobs in π1 are given by
(2.2)Ci[1](π1)=ai[1]+(1+bi)θi+(1+bi)(1+δi)t,⋮Ci[ni](π1)=∑k=1ni(1+bi)ni-kai[k]+(1+bi)niθi+(1+bi)ni(1+δi)t,Cj[1](π1)=aj[1]+(1+bj)θj+(1+bj)(1+δj)Ci[ni](π1),⋮Cj[nj](π1)=∑k=1nj(1+bj)nj-kaj[k]+(1+bj)njθj+(1+bj)nj(1+δj)Ci[ni](π1).
And the completion times of jobs in π2 are given by
(2.3)Cj[1](π2)=aj[1]+(1+bj)θj+(1+bj)(1+δj)t,⋮Cj[nj](π2)=∑k=1nj(1+bj)nj-kaj[k]+(1+bj)njθj+(1+bj)nj(1+δj)t,Ci[1](π2)=ai[1]+(1+bi)θi+(1+bi)(1+δi)Cj[nj](π2),⋮Ci[ni](π2)=∑k=1ni(1+bi)ni-kai[k]+(1+bi)niθi+(1+bi)ni(1+δi)Cj[nj](π2).
Therefore, we have
(2.4)∑l=1nj‍Cj[l](π2)+∑l=1ni‍Ci[l](π2)-∑l=1ni‍Ci[l](π1)-∑l=1nj‍Cj[l](π1)=(1+bj)(1-(1+bj)nj)(1+δj)t1-(1+bj)+(1+bi)(1-(1+bi)ni)(1+δi)Cj[nj](π2)1-(1+bi)-(1+bi)(1-(1+bi)ni)(1+δi)t1-(1+bi)-(1+bj)(1-(1+bj)nj)(1+δj)Ci[ni](π1)1-(1+bj).
By substituting
(2.5)Ai=(1+bi)(1-(1+bi)ni)(1+δi)1-(1+bi),Aj=(1+bj)(1-(1+bj)nj)(1+δj)1-(1+bj),Bi=∑k=1ni‍(1+bi)ni-kai[k]+(1+bi)niθi,Bj=∑k=1nj‍(1+bj)nj-kaj[k]+(1+bj)njθj,
we can obtain
(2.6)∑l=1nj‍Cj[l](π2)+∑l=1ni‍Ci[l](π2)-∑l=1ni‍Ci[l](π1)-∑l=1nj‍Cj[l](π1)=(Ai((1+bj)nj(1+δj)-1)-Aj((1+bi)ni(1+δi)-1))t+AiBj-AjBi.
To have
(2.7)∑l=1nj‍Cj[l](π2)+∑l=1ni‍Ci[l](π2)-∑l=1ni‍Ci[l](π1)-∑l=1nj‍Cj[l](π1)≥0,
when t≥0, if and only if
(2.8)Ai((1+bj)nj(1+δj)-1)-Aj((1+bi)ni(1+δi)-1)≥0,(2.9)AiBj-AjBi≥0.
From the result of (2.8), we have ((1+bi)ni(1+δi)-1)/Ai≤((1+bj)nj(1+δj)-1)/Aj, that is to say ω(Gi)≤ω(Gj).
And from the case of (2.9), we can obtain Bi/Ai≤Bj/Aj.
Therefore, ifω(Gi) and Bi/Ai have agreeable conditions, the optimal sequence between groups are arranged in nondecreasing order of ω(Gi), This completes the proof.From Theorems2.1 and 2.2, if ω(Gi) and Bi/Ai have agreeable condition, the problem 1/GT, pij=aij+bit, si=θi+δit/∑‍Cij can be solved by the following algorithm.Algorithm 2.3.
Step  1. Jobs in each group are scheduled in nondecreasing order of the basic processing time ai[j], that is, ai[1]≤ai[2]≤ai[3]≤ai[4]≤⋯≤ai[ni], i=1,2,3,…m, (the SPT rule).
Step  2. Calculate ω(Gi)=bi((1+bi)ni(1+δi)-1)/((1+bi)(1+bi)ni-1)(1+δi).
Step  3. Groups are scheduled in nondecreasing order of ω(Gi), that is, ω(G1)≤ω(G2)≤ω(G3)≤⋯≤ω(Gm).
Obviously, It is easy to show that the total time for Algorithm2.3 is O(nlogn).


## 3. The1/GT, pij=aij-bit, si=θi-δit/∑‍Cij Problem

In order to discuss the problem1/GT, pij=aij-bit, si=θi-δit/∑‍Cij conveniently, we suppose 0≤bi≤1 and 0≤θi≤1.Theorem 3.1.
For the 1/GT,pij=aij-bit, si=θi-δit/∑‍Cij problem, the optimal schedule is obtained by sequencing the jobs in each group in nondecreasing order of basic processing time ai[j], that is, ai[1]≤ai[2]≤ai[3]≤ai[4]≤⋯≤ai[ni], i=1,2,3,…m, (the SPT rule).Proof.
In the same group, the result can be easily obtained by using interchanging technology and is omitted.Theorem 3.2.
For the 1/GT,pij=aij-bit, si=θi-δit/∑‍Cij problem, the groups are arranged in nondecreasing order of ω(Gi), ω(Gi)=bi((1-bi)ni(1-δi)-1)/(1-bi)(1-(1-bi)ni)(1-δi), if ω(Gi) and Bi/Ai have agreeable conditions, that is, Bi/Ai≥Bj/Aj if and only if ω(Gi)≥ω(Gj), Ai=(1-bi)(1-(1-bi)ni)(1-δi)/(1-(1-bi)), and Bi=∑k=1ni(1-bi)ni-kai[k]+(1-bi)niθi.Proof.
Here, we still use the same notations as that in Theorem2.2. To show π1 dominates π2, it suffices to show that
(3.1)∑l=1ni‍Ci[l](π1)+∑l=1nj‍Cj[l](π1)≤∑l=1nj‍Cj[l](π2)+∑l=1ni‍Ci[l](π2).
By definition, the completion times of jobs in π1 are given by
(3.2)Ci[1](π1)=ai[1]+(1-bi)θi+(1-bi)(1-δi)t,⋮Ci[ni](π1)=∑k=1ni‍(1-bi)ni-kai[k]+(1-bi)niθi+(1-bi)ni(1-δi)t,Cj[1](π1)=aj[1]+(1-bj)θj+(1-bj)(1-δj)Ci[ni](π1),⋮Cj[nj](π1)=∑k=1nj‍(1-bj)nj-kaj[k]+(1-bj)njθj+(1-bj)nj(1-δj)Ci[ni](π1).
And the completion times of jobs in π2 are given by
(3.3)Cj[1](π2)=aj[1]+(1-bj)θj+(1-bj)(1-δj)t,⋮Cj[nj](π2)=∑k=1nj‍(1-bj)nj-kaj[k]+(1-bj)njθj+(1-bj)nj(1-δj)t,Ci[1](π2)=ai[1]+(1-bi)θi+(1-bi)(1-δi)Cj[nj](π2),⋮Ci[ni](π2)=∑k=1ni‍(1-bi)ni-kai[k]+(1-bi)niθi+(1-bi)ni(1-δi)Cj[nj](π2).
Therefore, we have
(3.4)∑l=1nj‍Cj[l](π2)+∑l=1ni‍Ci[l](π2)-∑l=1ni‍Ci[l](π1)-∑l=1nj‍Cj[l](π1)=(1-bj)(1-(1-bj)nj)(1-δj)t1-(1-bj)+(1-bi)(1-(1-bi)ni)(1-δi)Cj[nj](π2)1-(1-bi)-(1-bi)(1-(1-bi)ni)(1-δi)t1-(1-bi)-(1-bj)(1-(1-bj)nj)(1-δj)Ci[ni](π1)1-(1-bj).
By substituting
(3.5)Ai=(1-bi)(1-(1-bi)ni)(1-δi)1-(1-bi),Aj=(1-bj)(1-(1-bj)nj)(1-δj)1-(1-bj),Bi=∑k=1ni‍(1-bi)ni-kai[k]+(1-bi)niθi,Bj=∑k=1nj‍(1-bj)nj-kaj[k]+(1-bj)njθj,
we can obtain
(3.6)∑l=1nj‍Cj[l](π2)+∑l=1ni‍Ci[l](π2)-∑l=1ni‍Ci[l](π1)-∑l=1nj‍Cj[l](π1)=(Ai((1-bj)nj(1-δj)-1)-Aj((1-bi)ni(1-δi)-1))t+AiBj-AjBi.
To have
(3.7)∑l=1nj‍Cj[l](π2)+∑l=1ni‍Ci[l](π2)-∑l=1ni‍Ci[l](π1)-∑l=1nj‍Cj[l](π1)≥0,
when t≥0 if and only if
(3.8)Ai((1-bj)nj(1-δj)-1)-Aj((1-bi)ni(1-δi)-1)≥0,(3.9)AiBj-AjBi≥0.
From the result of (3.8), we have
(3.10)(1-bi)ni(1-δi)-1Ai≤(1-bj)nj(1-δj)-1Aj,
that is to say ω(Gi)≤ω(Gj).
And from the case of (3.9), we can obtain Bi/Ai≤Bj/Aj.
Therefore, ifω(Gi) and Bi/Ai have agreeable conditions, the optimal sequence between groups are arranged in nondecreasing order of ω(Gi), This completes the proof.From Theorems3.1 and 3.2, if ω(Gi) and Bi/Ai have agreeable condition, the problem 1/GT, pij=aij-bit, si=θi-δit/∑‍Cij can be solved by the following algorithm.Algorithm 3.3.
Step  1. Jobs in each group are scheduled in nondecreasing order of the basic processing time ai[j], that is, ai[1]≤ai[2]≤ai[3]≤ai[4]≤⋯≤ai[ni], i=1,2,3,…m, (the SPT rule).
Step  2. Calculate ω(Gi)=bi((1-bi)ni(1-δi)-1)/(1-bi)(1-(1-bi)ni)(1-δi).
Step  3. Groups are scheduled in nondecreasing order of ω(Gi), that is, ω(G1)≤ω(G2)≤ω(G3)≤⋯≤ω(Gm).
Obviously, It is easy to show that the total time for Algorithm3.3 is O(nlogn).


## 4. Examples

Example 4.1.
For the1/GT, pij=aij+bit, si=θi+δit/∑‍Cij problem, we consider six jobs are divided into three groups. The basic job and group processing times, the job and group deterioration rates for each group are given, respectively, as follows:
(4.1)p11=5,p12=8,p21=4,p22=10,p23=6,p31=7,b1=0.04,b2=0.02,b3=0.01,θ1=5,θ2=4,θ3=6,δ1=0.01,δ2=0.05,δ3=0.04.Solution 1.
According to Algorithm2.3, 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→J23→J22.
In groupG3, the optimal job sequence is J31.Step 2.
calculate:B1/A1=8.683, B2/A2=7.483, B3/A3=12.483, and ω(G1)=0.043, ω(G2)=0.035, ω(G3)=0.048. It is easy to say B2/A2<B1/A1<B3/A3 and ω(G2)<ω(G1)<ω(G3). Therefore, the optimal group sequence is G2→G1→G3 and the optimal schedule is [J21→J23→J22]→[J11→J12]→[J31]. The completion times of jobs are C21=8.08, C23=14.242, C22=24.527, C11=35.963, C12=45.402, and C31=60.750, and the sum of completion times is ∑‍Cij=8.08+14.242+24.527+35.963+45.402+60.750=188.964.Example 4.2.
For the1/GT, pij=aij-bit, si=θi-δit/∑‍Cij problem, we consider six jobs are divided into three groups as Example 4.1, the job and group deterioration rates for each group are given, respectively, as follows:
(4.2)p11=9,p12=7,p13=5,p21=10,p31=8,p32=6,b1=0.03,b2=0.05,b3=0.02,θ1=4,θ2=8,θ3=5,δ1=0.15,δ2=0.01,δ3=0.1.Solution 2.
According to Algorithm2.3, we solve the example as follows.Step 1.
In groupG1, the optimal job sequence is J13→J12→J11.
In groupG2, the optimal job sequence is J21.
In groupG3, the optimal job sequence is J32→J31.Step 2.
calculate:B1/A1=10.060, B2/A2=18.713, B3/A3=10.700, and ω(G1)=-0.093, ω(G2)=-0.063, ω(G3)=-0.078. It is easy to say B1/A1<B3/A3<B2/A2 and ω(G1)<ω(G3)<ω(G2). Therefore, the optimal group sequence is G1→G3→G2 and the optimal schedule is [J13→J12→J11]→[J32→J31]→[J21]. The completion times of jobs are C13=8.88, C12=15.614, C11=24.146, C32=34.326, C31=41.639, C21=53.201, and the sum of completion times is ∑‍Cij=8.88+15.614+24.146+34.326+41.639+53.201=177.806.


## 5. Conclusions

In this paper, we investigate the single-machine group scheduling problems with deterioration which is studied by Lee and Wu [24]. We consider the sum of completion times minimization problem, and we show the problem to minimize total completion time of all jobs is polynomially solvable under agreeable conditions in our study.



---

*Source: 275239-2012-12-04.xml*