# Batch Scheduling with Proportional-Linear Deterioration and Outsourcing

Authors: Cuixia Miao; Fanxiao Meng; Juan Zou; Binglin Jia
Journal: Mathematical Problems in Engineering
 (2017)

---

## Abstract

We consider the bounded parallel-batch scheduling with proportional-linear deterioration and outsourcing, in which the actual processing time ispj=αj(A+Dt) or pj=αjt. A job is either accepted and processed in batches on a single machine by manufactures themselves or outsourced to the third party with a certain penalty having to be paid. The objective is to minimize the maximum completion time of the accepted jobs and the total penalty of the outsourced jobs. For the pj=αj(A+Dt) model, when all the jobs are released at time zero, we show that the problem is NP-hard and present a pseudo-polynomial time algorithm, respectively. For the pj=αjt model, when the jobs have distinct m (<n) release dates, we provide a dynamic programming algorithm, where n is the number of jobs.


---

## Body

## 1. Introduction

The parallel-batch scheduling is motivated by burn-in operations in semiconductor manufacturing; see Lee et al. [1] for more details of the background. By Brucker et al. [2], there are two distinct models: thebounded model, in which the bound b for each batch size is effective, that is, b<n, and theunbounded model, in which there is effectively no limit on the size of batch, that is, b≥n. The extensive survey of different models and results was provided both by Potts and Kovalyov [3] and Zhang and Cao [4].Scheduling with deterioration was first considered by J. N. D. Gupta and S. K. Gupta [5], and Browne and Yechiali [6]. From then on, this scheduling model has been extensively studied. The monograph by Gawiejnowicz [7] presents this scheduling from different perspectives and covers results and examples. Ji and Cheng [8], Liu et al. [9], and Miao [10] gave some new results for this scheduling.In classical scheduling literatures, all jobs must be processed. In the practical applications, however, this may not be true. Due to the limited resources, the scheduler can have the option to outsource or reject some jobs. However, outsourced jobs will incur penalties. The scheduling with outsourcing was first considered by Bartal et al. [11]. They studied both the offline and the online versions of scheduling with outsourcing on identical parallel machines, the objective is to minimize the maximum completion time of the accepted jobs and the total penalty of the outsourced jobs.Cao and Yang [12] presented a PTAS for the combined model of the parallel-batch and rejection where jobs arrive dynamically. The objective is to minimize the maximum completion time of the accepted jobs and the total penalty of the outsourced ones. Lu et al. ([13, 14]) considered the unbounded and bounded parallel-batch scheduling problems with outsourcing on a single machine. Cheng and Sun [15] considered the scheduling with linear deteriorating jobs and rejection on a single machine; they gave the proofs of the NP-hardness and presented some pseudo-polynomial time algorithms and FPTASs for some objectives. Miao [16] considered the bounded parallel-batch scheduling with rejection in the V chapter of her thesis.In this paper, we consider the bounded parallel-batch scheduling with proportional-linear deterioration and outsourcing on a single machine. The objective is to minimize the maximum completion time of the accepted jobs and the total penalty of the outsourced jobs. We analyze the NP-hardness and present pseudo-polynomial time dynamic programming algorithms for two deterioration models


## 2. Problem Description and Preliminaries

There aren independent nonpreemptive deteriorating jobs J={J1,…,Jn} to be processed on a single batch machine. The actual processing time of job Jj(j=1,…,n) is pj=αjt or pj=αj(A+Dt), where A,D>0, αj (≥0), and t denote the deteriorating rate and starting time, respectively. Jj has release date rj and outsourced penalty ej. Without loss of generality, we assume that the jobs’ parameters are integral, unless stated otherwise. Each job Jj is either accepted to be processed on the machine in batches or outsourced with a penalty ej having to be paid. The machine can process up to b jobs simultaneously as a batch, and the processing time of the batch is equal to the longest time of the job in the batch; in the deterioration model, the deteriorating rate of the batch is equal to the largest deteriorating rate of the job in the batch. Following Gawiejnowicz [7], we denote our problems as 1∣p-batch,pj=αj(A+Dt),rj=0,outsouring,b<n∣Cmax(S)+∑S-ej and 1∣p-batch,pj=αjt,rj,outsourcing,b<n∣Cmax(S)+∑S-ej.Lemma 1 (see [7]).
Problem1∣pj=αj(A+Dt)∣Cmax is solvable in O(n) time if A,D>0, αj>0 for 1≤j≤n, and the completion time of the jth job and the maximum completion time are Cj=(A/D)∏i=1j(1+Dαi)-A/D and Cmax=(A/D)∏j=1n(1+Dαj)-A/D, respectively.Lemma 2 (see [15]).
Problem1∣pj=αjt,rj=t0,rej∣Cmax(S)+∑S¯ej is NP-hard.Lemma 3 (see [17]).
For the single machine scheduling problem1∣pj=αjt∣Cmax, if a schedule π={J[1],J[2],…,J[n]}, and the starting time of job J[1] is t0, then the makespan is (1)Cmaxπ=t0∏j=1n1+αj.We list the following useful algorithm stated in Miao et al. [18].Algorithm FBLDR (fully batching longest deteriorating rate)Step
1. Reindex jobs in nonincreasing order of their deteriorating rates such that α1≥⋯≥αn.Step
2. Form batches by placing jobs Jjb+1 through J(j+1)b together in the same batch, for j=0,1,…,n/b.Step
3. Schedule the batches in any arbitrary order.The schedule contains at mostn/b+1 batches and all batches are full except possibly the last one, where n/b denotes the largest integer less than n/b.


## 3. The Case with Identical Release Dates

In this section, we discuss problem1∣p-batch,pj=αj(A+Dt),rj=0,outsouring,b<n∣Cmax(S)+∑S-ej.


### 3.1. NP-Hardness

From Lemma2 and Zhang and Miao [19], we can get the following theorem.Theorem 4.
Problem1∣p-batch,pj=αj(A+Dt),rj=0,outsouring,b<n∣Cmax(S)+∑S-ej is NP-hard.


### 3.2. Pseudo-Polynomial Time Algorithm

Theorem 5.
For problem1∣p-batch,pj=αj(A+Dt),rj=0,outsouring,b<n∣Cmax(S)+∑S-ej, there exists an optimal schedule in which the accepted jobs are assigned to the machine by Algorithm FBLDR.Assume that the jobs have been indexed so thatα1≥⋯≥αn.LetFj(bj,E) be the optimal value of the objective function satisfying the following conditions for problem 1∣p-batch,pj=αj(A+Dt),rj=0,outsouring,b<n∣Cmax(S)+∑S-ej:(i)
The jobs in consideration areJ1,…,Jj.(ii)
The number of processed jobs in the last batch isbj. If there is no such batch, we set bj=0.(iii)
The total penalty of outsourced jobs isE.We design an algorithm as follows.Algorithm
D
P
1Step
1 (initialization)F1(1,0)=Aα1 and Fj(bj,E)=+∞ for (bj,E)≠(1,0).F1(0,e1)=e1 and Fj(bj,E)=+∞ for (bj,E)≠(0,e1).Step
2 (iteration)Ifbj=1,Fj(bj,E)=min⁡{(1+Dαj)(Fj-1(b,E)-E)-Aαj+E,Fj-1(bj,E-ej)+ej}.Ifbj>1,Fj(bj,E)=min⁡{Fj-1(bj-1,E),Fj-1(bj,E-ej)+ej}.Step
3 (solution)Define the optimal value:F∗=min⁡{Fn(bn,E):0≤bn≤b,0≤E≤∑j=1nej}.In Step 2, when jobJj is accepted and bj=1, Jj has to start a new batch, combining with Lemma 1, we have Fj(bj,E)=(1+Dαj)(Fj-1(b,E)-E)-Aαj+E, when bj>1,Jj should be assigned to the last batch which has existed, and the makespan does not change; therefore, Fj(bj,E)=Fj-1(bj-1,E). When job Jj is outsourced, Fj(bj,E)=Fj-1(bj,E-ej)+ej.Theorem 6.
AlgorithmDP1 solves problem 1∣p-batch,pj=αj(A+Dt),rj=0,outsouring,b<n∣Cmax(S)+∑S-ej in O(nb(∑j=1nej)) time.


## 3.1. NP-Hardness

From Lemma2 and Zhang and Miao [19], we can get the following theorem.Theorem 4.
Problem1∣p-batch,pj=αj(A+Dt),rj=0,outsouring,b<n∣Cmax(S)+∑S-ej is NP-hard.


## 3.2. Pseudo-Polynomial Time Algorithm

Theorem 5.
For problem1∣p-batch,pj=αj(A+Dt),rj=0,outsouring,b<n∣Cmax(S)+∑S-ej, there exists an optimal schedule in which the accepted jobs are assigned to the machine by Algorithm FBLDR.Assume that the jobs have been indexed so thatα1≥⋯≥αn.LetFj(bj,E) be the optimal value of the objective function satisfying the following conditions for problem 1∣p-batch,pj=αj(A+Dt),rj=0,outsouring,b<n∣Cmax(S)+∑S-ej:(i)
The jobs in consideration areJ1,…,Jj.(ii)
The number of processed jobs in the last batch isbj. If there is no such batch, we set bj=0.(iii)
The total penalty of outsourced jobs isE.We design an algorithm as follows.Algorithm
D
P
1Step
1 (initialization)F1(1,0)=Aα1 and Fj(bj,E)=+∞ for (bj,E)≠(1,0).F1(0,e1)=e1 and Fj(bj,E)=+∞ for (bj,E)≠(0,e1).Step
2 (iteration)Ifbj=1,Fj(bj,E)=min⁡{(1+Dαj)(Fj-1(b,E)-E)-Aαj+E,Fj-1(bj,E-ej)+ej}.Ifbj>1,Fj(bj,E)=min⁡{Fj-1(bj-1,E),Fj-1(bj,E-ej)+ej}.Step
3 (solution)Define the optimal value:F∗=min⁡{Fn(bn,E):0≤bn≤b,0≤E≤∑j=1nej}.In Step 2, when jobJj is accepted and bj=1, Jj has to start a new batch, combining with Lemma 1, we have Fj(bj,E)=(1+Dαj)(Fj-1(b,E)-E)-Aαj+E, when bj>1,Jj should be assigned to the last batch which has existed, and the makespan does not change; therefore, Fj(bj,E)=Fj-1(bj-1,E). When job Jj is outsourced, Fj(bj,E)=Fj-1(bj,E-ej)+ej.Theorem 6.
AlgorithmDP1 solves problem 1∣p-batch,pj=αj(A+Dt),rj=0,outsouring,b<n∣Cmax(S)+∑S-ej in O(nb(∑j=1nej)) time.


## 4. The Case withm Distinct Release Dates

In this section, we present a dynamic programming algorithm for the case where the jobs have a constant number of release dates.From Theorem4, we have that 1∣p-batch,pj=αjt,rj,outsourcing,b<n∣Cmax(S)+∑S-ej is NP-hard. Assume that jobs have been indexed so that α1≥⋯≥αn and there are m distinct release dates denoted by t0=R1<R2<⋯<Rm, where m is a constant. We divide [R1,+∞) into m time intervals [R1,R2),[R2,R3),…,[Rm,Rm+1), where Rm+1=+∞.Given a scheduleπ, let J=⋃i=1mHi(π) and Hiπ∩Hj(π)=ϕ for 1≤i≠j≤m such that jobs in Hi(π) are started at or after Ri but strictly before Ri+1.We can locally rearrange the schedule of each subsetHi(π), without increasing its makespan, so that it follows AlgorithmFBLDR as the following lemma.Lemma 7.
For any scheduleπ for J to minimize Cmax, there exists a schedule π′ for J with Cmax′, such that Cmax(π′)≤Cmax(π), and Hi(π)=Hi(π′), and the schedule for Hi(π′) according to π′ follows AlgorithmFBLDR for i=1,2,…,m.Reindex jobs in nonincreasing order of their deteriorating rates so thatα1≥⋯≥αn. By the above lemma, we partition all jobs into a sequence of m disjoint subsets H1,…,Hm and can assume that each subset Hi is scheduled in time interval [Ri,Ri+1) according to algorithm FBLPT. If Hi≠ϕ, then there is a starting time t≥Ri at which the first batch of Hi is started. When the last batch of Hi-1 is delay, that is, being finished after Ri (even though it is started before time Ri), then t>Ri.LetFj(d1,…,dm;P1,…,Pm;b1,…,bm;E) be the optimal value of the objective function satisfying the following conditions:(i)
The jobs in consideration areJ1,…,Jj.(ii)
di(1≤i≤m) is the delay time of the first batch starting in [Ri,Ri+1) which is caused by the last batch starting in [Ri-1,Ri). Without loss of generality, we set d1=0.(iii)
Pi(1≤i≤m) is the total length of batches starting in [Ri,Ri+1). If there is no batch starting in [Ri,Ri+1), we set Pi=0.(iv)
bi(1≤i≤m) is the number of jobs in the last batch starting in [Ri,Ri+1). If there is no batch starting in time [Ri,Ri+1), then we set bi=0.(v)
The total penalty of the outsourced jobs isE.Finally, we define the makespan of a scheduleπ for jobs J1,…,Jj as Rm+dm+Pm. Hence, the makespan is always at least Rm.Now, we distinguish two cases.Case 1 (jobJj is outsourced).
In this case, we have(2)Fjd1,…,dm;P1,…,Pm;b1,…,bm;E=Fj-1d1,…,dm;P1,…,Pm;b1,…,bm;E-ej+ej.Case 2 (jobJj is accepted).
In this case, without loss of generality, we assume thatrj=Ri; then it can be scheduled in time interval [Rk,Rk+1)(i≤k≤m). We distinguish two subcases in the following.Case
2.1
(
b
k
=
1
). In this subcase, the last batch starting in [Rk,Rk+1) is either full or does not exist at all before inserting Jj. Without loss of generality, we assume that the batch is full.Fori≤k≤m, let x be the increasing time by inserting job Jj in [Rk,Rk+1). Then we have (Rk+dk+Pk-x)αj=x; then x=(Rk+dk+Pk)αj/(1+αj). Thus, the total length of batches starting in [Rk,Rk+1) before inserting Jj is Pk-x=Pk-(Rk+dk+Pk)αj/(1+αj).Therefore, fori≤k<m, if (Rk+dk+Pk)αj/(1+αj)∈Z+ and Pk≥(Rk+dk+Pk)αj/(1+αj), we have(3)Fjd1,…,dm;P1,…,Pm;b1,…,bm;E=Fj-1d1,…,dm;P1,…,Pk-1,Pk-Rk+dk+Pkαj1+αj,Pk+1,…,Pm;b1,…,bk-1,b,bk+1,…,bm;E.IfRk+dk+Pkαj/1+αj∈¯Z+ or Pk<(Rk+dk+Pk)αj/(1+αj), we have Fj(d1,…,dm;P1,…,Pm;b1,…,bm;E)=+∞.Fork=m,(Rm+dm+Pm)αj/(1+αj)∈Z+ and Pm≥(Rm+dm+Pm)αj/(1+αj), we have(4)Fjd1,…,dm;P1,…,Pm;b1,…,bm;E=Fj-1d1,…,dm;P1,…,Pm-1,Pm-Rm+bm+Pmαj1+αj;b1,…,bm-1,b;E+Rm+dm+Pmαj1+αj.Otherwise, Fj(d1,…,dm;P1,…,Pm;b1,…,bm;E)=+∞.Case
2.2
(
b
k
>
1
). In this subcase, Jj can be assigned to the last batch starting in [Rk,Rk+1). Therefore, we have (5)Fjd1,…,dm;P1,…,Pm;b1,…,bm;E=Fj-1d1,…,dm;P1,…,Pm;b1,…,bk-1,bk-1,bk+1,…,bm;E.Suppose thatr1=Ri for some i, if it is accepted, it can only be scheduled at or after Ri. Without loss of generality, suppose that it is scheduled at time interval [Rk,Rk+1),i≤k≤m; then, C1=(Rk+dk)(1+α1).Combining the above discussion, we design AlgorithmDP2 as follows.Algorithm
D
P
2Step
1 (initialization)(6)F10,…,0,dk,0,…,0;0,…,0,Rk+dkα1,0,…,0;0,…,0,1,0,…,0;0=max⁡Rm,Rk+bk1+α1,F1d1,…,dm;P1,…,Pm;b1,…,bm;E=+∞ford1,…,dm;P1,…,Pm;b1,…,bm;E≠0,…,0,dk,0,…,0;0,…,0,Rk+dkα1,0,…,0;0,…,0,1,0,…,0;0,F10,…,0;0,…,0,…,0;0,…,0;e1=Rm+e1,F1d1,…,dm;P1,…,Pm;b1,…,bm;E=+∞ford1,…,dm;P1,…,Pm;b1,…,bm;E≠0,…,0;0,…,0,…,0;0,…,0;e1.Step
2 (iteration)(7)Fjd1,…,dm;P1,…,Pm;b1,…,bm;E=min⁡Fj-1d1,…,dm;P1,…,Pm;b1,…,bm;E-ej+ej,min⁡Fkj,where Fk(j) is defined as follows:(8)Fkj=Fj-1d1,…,dm;P1,…,Pm;b1,…,bk-1,bk-1,bk+1,…,bm;Efor bk>1 and i≤k≤m.(9)Fkj=Fj-1d1,…,dm;P1,…,Pk-1,Pk-Rk+dk+Pkαj1+αj,Pk+1,…,Pm;b1,…,bk-1,b,bk+1,…,bm;Efor bk=1,i≤k<m, (Rk+dk+Pk)αj/(1+αj)∈Z+, and Pk≥(Rk+dk+Pk)αj/(1+αj).Otherwise,Fk(j)=+∞,(10)Fmj=Fj-1d1,…,dm;P1,…,Pm-1,Pm-Rm+bm+Pmαj1+αj;b1,…,bm-1,b;E+Rm+dm+Pmαj1+αj,for bk=1, k=m, (Rm+dm+Pm)αj/(1+αj)∈Z+ and Pm≥(Rm+dm+Pm)αj/(1+αj).Otherwise,Fm(j)=+∞.Step
3(optimal value)Define the optimal value(11)F∗=min⁡Fnd1,…,dm;P1,…,Pm;b1,…,bm;E:0≤di≤Riαmax,0≤Pi≤Ri+diT-1,1≤bi≤b,i=1,…,m;0≤E≤∑j=1nej,where T=∏j=1n(1+αj).Theorem 8.
AlgorithmDP2 solves problem 1∣p-batch,pj=αjt,rj∈{Ri:1≤i≤m},outsourcing,b<n∣Cmax(S)+∑Jj∈S¯ej with the running time of O(mnR2(b(1+αmax)αmaxT)m), where R=R1R2⋯Rm.Proof.
The correctness of the dynamic programming algorithmDP2 is guaranteed by the above discussion. Clearly, we have 1≤bi≤b,0≤di≤Riαmax for i=1,…,m and 0≤E≤∑j=1nej. Then, 0≤Pi≤(Ri+di)(T-1)≤Ri(1+αmax)T. Therefore, there is O(nR2(b(1+αmax)αmaxT)m) set of possible input value. For each set, it takes O(m) time to compute the value of objective. Thus, the running time of algorithm DP2 is O(mnR2(b(1+αmax)αmaxT)m).


## 5. Conclusion

In this paper, we presented a pseudo-polynomial time algorithm for1∣p-batch,pj=αj(A+Dt),rj=0,outsouring,b<n∣Cmax(S)+∑S-ej and a dynamic programming algorithm for the case where jobs have m distinct release dates of problem 1∣p-batch,pj=αjt,rj,outsouring,b<n∣Cmax(S)+∑S-ej. For future research, it is worth considering other objectives.



---

*Source: 6093029-2017-06-22.xml*