Bicriteria Scheduling on a Series-Batching Machine to Minimize Makespan and Total Weighted Completion Time with Equal Length Job

HE Cheng,LIN Hao,DOU Jun-mei,MU Yun-dong

(School of Science,Henan University of Technology,Zhengzhou 450001,China)

Bicriteria Scheduling on a Series-Batching Machine to Minimize Makespan and Total Weighted Completion Time with Equal Length Job

HE Cheng,LIN Hao,DOU Jun-mei,MU Yun-dong

(School of Science,Henan University of Technology,Zhengzhou 450001,China)

It is known that the problem of minimizing total weighted completion time on a series-batching machine is NP-hard.We consider a series-batching bicriteria scheduling problem of minimizing makespan and total weighted completion time with equal length job simultaneously.A batching machine can handle up to b jobs in a batch,where b is called the batch capacity of the machine.We study the unbounded model with b≥n,where n denotes the number of jobs.A dynamic programming algorithm is proposed to solve the unbounded model,which can f i nd all Pareto optimal schedules in O(n3)time.

bicriteria scheduling;series-batching;makespan;total weighted completion time;Pareto optimal schedules

§1.Introduction

Multicriteria scheduling problems have been extensively studied in the last decade[8].The basic motivation of this direction is that decision-makers usually pursue several performance criteria simultaneously in product quality evaluations.On the other hand,scheduling on batching machines is also an appealing direction in recent years[3].This kind of problems have a wide range of applications in manufacturing and computer systems.Much study has been done inthese two directions[1,3,810].In this paper,we consider a bicriteria scheduling problem with two objective functions:makespan Cmaxand total weighted completion timewjCjand with the condition that the processing times of all jobs are equal.The goal is to fi nd all Pareto optimal schedules in polynomial time.Here,the machine environment is“series-batching”,which means that the jobs processed jointly form a batch with a constant setup time s and with a processing time being the sum of the processing times of its jobs.Following thethree- fi eld notation of[4], this model may be denoted by 1|s-batch,pj=p,b≥n|F(Cmax,),where“s-batch”refers to the series-batching and F represents an unknown composition objective function in simultaneous optimization.Moreover,a batching machine can handle up to b jobs in a batch, where b is called the batch capacity of the machine.We study the unbounded model with b≥n.

A minimum makespan Cmaxusually implies a high utilization of the machine(s)and the total weighted completion time usually denotes the total holding,inventory costs. Our model can be applied when decision-makers pursue a high utilization of the machine and a minimum inventory costs simultaneously in series-batching production.

Some related results in the literature is as follows.For the bicriteria scheduling problem,Hoogeveen[9]showed that the problem of minimizing two maximum cost criteria,that is 1||F(fmax,∑),is solvable in O(n4)time.For the batch scheduling problem 1|s-batch,pj= p,b≥n|wjCj,Albers and Brucker[1]presented an O(nlogn)algorithm and proved that j=1∑-1|s-batch,b≥n|wjCjis NP-hard.In our previous work[57]we investigated parallel-batching problem 1|p-batch,b≥n|F(Lmax,Cmax)and series-batching problems 1|s-batch,b≥n|F(Lmax, Cmax)and 1|s-batch,b≥n or b＜n|F(),respectively.In this paper we consider3a new combination of criteria CmaxandThe main result is to present an O(n) time algorithm for fi nding all Pareto optimal schedules of problem 1|s-batch,pj=p,b≥

The paper is organized as follows.In Section 2 we state some preliminaries.Section 3 is dedicated to the main result,an O(n3)algorithm for the problem.Section 4 gives a short summary.We shall follow the terminology and notation of[2].

§2.Preliminaries

Suppose that we are given n independent jobs with the identical processing time p,denoted by J1,J2,···,Jn.Job Jjhas a weight wj(j=1,···,n).They are to be scheduled on a single batching machine that is continuously available from time zero onwards and that can handle at most b jobs in a batch.Given a schedule σ,Cj(σ)and Cmax(σ)=1m≤ja≤xnCj(σ)denote the completion time of job Jjin σ and the maximum completion time(makespan)of jobs in σ.The total weighted completion time

For problems of minimizing a regular objective function without job’s release dates,theremust be an optimal schedule in which the batches are processed contiguously from time zero onwards.Throughout the paper,we restrict our attention to the schedules with this property. Thus,a schedule σ is a sequence of batches σ=(B1,B2,···,Bl),where each batch Bris a set of jobs(r=1,···,l).We denote the number of batches in σ by|σ|=l.Before processing each batch,there is a setup time s(a given positive constant).The processing time of batch Briscompletion time of job Jj∈Br(1≤r≤l)is Cj(σ)=C(Br).When there is no ambiguity,we abbreviate Cj(σ)to Cj.

In the scenario of bicriteria scheduling,we always use a composition objective function F(f(σ),g(σ))to combine two performance criteria f(σ)and g(σ),where F is assumed to be nondecreasing in both arguments.In particular,when F is an unknown function,this formulation represents the general case of simultaneous optimization.In this paper,the criteria f(σ)and g(σ)under consideration are two regular objective functions:makespan Cmax(σ)and total weighted completion time

With each schedule σ we associate a the status of twocriteria in R2.In the sequel,we use the terms schedule and point interchangeably.We can solve the bicriteria problem in polynomial time provided that we are able to identify all of the so-called Pareto optimal schedules in polynomial time.

Def i nition 2.1A feasible schedule σ is Pareto optimal,or nondominated,with respect to the performance criteria CmaxwjCjif there is no feasible schedule π such that both C

max(π)≤Cmax(σ)andwjCj(σ),where at least one of the inequalities is strict.

Let f,g be two criteria of the problem.A general way of f i nding the set of Pareto optimal points is the so-called ε-constraint approach as follows.Given a Pareto optimal point(x1,y1), say it is obtained by the hierarchical optimization,we may produce the second Pareto optimal point(x2,y2),where y2is obtained by minimizing g subject to the constraint f＜x1and x2is obtained by minimizing f subject to the constraint g≤y2.This is a basic procedure in multicriteria optimization[8].

§3.Polynomial-time Algorithm

It is well known that the classical problem 1|s-batch,p=p,b≥n|can be solved

jby the LW(the largest weight fi rst)rule[1].So we may re-index the jobs so that w1≥w2≥···≥wnin advance.We may call this the LW-property.Further,this property still holds for our bicriteria model:

Lemma 3.1For problem 1|s-batch,p=p,b≥n|F(,each Paretojoptimal schedule satis fi es the LW-property.

ProofAssume that there is a Pareto optimal schedule σ=(B1,···,Br,···,Bq,···,Bl), where 1≤r＜q≤l,with Jk∈Br,Jj∈Bq,but wk＜wj.Consider now the schedule σ0=(B1,···,(Br∪{Jj}){Jk},···,(Bq∪{Jk}){Jj},···,Bl)that is obtained from σ by interchanging jobs Jkand Jj.Since pk=pj=p,we have Cx(σ)=Cx(σ0)(x/=k,j)and Ck(σ)= Cj(σ0)and Cj(σ)=Ck(σ0).However wk＜wjand Cj(σ)＞Ck(σ),so Cmax(σ)=Cmax(σ0)andcontradicting the Pareto optimality of σ.

Lemma 3.1 shows that a Pareto optimal schedule can be specif i ed by the jobs that start each batch,since the complete schedule can be formed by the LW-rule.We refer to such a schedule as LW-batch schedule.

Note that the makespan of schedule σ is mainly dependent on the number l of batches.So we have the following.

Lemma 3.2For any schedule σ with l batches,Cmax(σ)=ls+np.

Therefore,in order to f i nd all Pareto optimal schedules of the problem 1|s-batch,pj=We solve this problem by a dynamic programming algorithm,called DP algorithm in short.

Let Fl(j)be the minimumwiCiof any LW-batch schedule σ with l batches of jobs J1,J2,···,Jj(j≥l),and Wkj=wi(0≤k≤j?1＜j≤n).Then the recursion equation is

In fact,let Bl={Jk+1,···,Jj}be the last batch.Then each job in this batch has the same completion time ls+jp,and so their total weighted completion time is(ls+jp)Wkj.Moreover, the minimum total weighted completion time of the fi rst l?1 batches is Fl?1(k).Therefore the optimal value Fl(j)of l batches is the minimum of Fl?1(k)+(ls+jp)Wkjover all k with l?1≤k＜j.On the other hand,let kl(j)be the value of k attaining the minimum of(1)(for given l and j).If there is a tie,we always choose kl(j)as large as possible.The values kl(j) are called optimal decision functions.

It is clear that the initial conditions of the recursive process are as follows

In a routine procedureofDPalgorithm,wehavetocomputethe optimalityfunctionsF1(j),F2(j), ···,Fn(j)and the decision functions k1(j),k2(j),···,kn(j)successively.

Let ?(j,k):=Fl?1(k)+(ls+jp)Wkj(l?1≤k＜j)for fi xed l.It is increasing for j when k is fi xed,while ?(j,k)?Fl?1(k)is decreasing when j is fi xed.Note that Fl(j)=?(j,k)= ?(j,kl(j)).We have the following basic properties.

Lemma 3.3kl(j)≤kl(j+1)≤j.

ProofSuppose to the contrary that kl(j)＞kl(j+1)=r.By the optimality of kl(j), we have ?(j,kl(j))=l?m1≤ikn＜j?(j,k)≤?(j,r).Furthermore,?(j+1,kl(j))??(j+1,r)= Fl?1(kl(j))?Fl?1(r)?[ls+(j+1)p]Wr,kl(j)=?(j,kl(j))??(j,r)?pWr,kl(j)＜0.Hence ?(j+1,kl(j))＜?(j+1,kl(j+1)),contradicting the optimality of kl(j+1).This completes the proof.

By this property,in order to compute the minimum of(1),the variable k can be taken from kl(j?1)to j?1(rather than starting from scratch).Moreover,we want to know the condition of kl(j)=kl(j+1).

Lemma 3.4Let r=kl(j)and for r＜k≤j,let α(r,k)Then kl(j)=kl(j+1)if and only if j+1

Proof kl(j)=kl(j+1)if and only if ?(j+1,k)≥?(j+1,r)for any r＜k≤j and this is in turn equivalent to

i.e.,

that is,j+1≤α(r,k).Therefore we have j+1≤α(r,k)by the arbitrariness of k.The proof is complete.

If this condition holds,we can save the computation of kl(j+1)at round j+1.Likewise, we can consider the round j+2.So we have the following subroutine for each stage l,for which Fl?1(j)(l?1≤j≤n)are known.

Procedure lComputation of Fl(j)

Step 0Let Fl(j)=+∞for j≤l?1 and Fl(l)=Fl?1(l?1)+(ls+lp)wl,kl(l)=l?1. Let j=l+1.

Step 1(Round j)Let r:=kl(j?1),k:=r,α(r):=+∞.

(1.2)If α(r,k)＜α(r),then set α(r):=α(r,k).If j≥α(r),then set r:=k,α(r):=+∞.

(1.3)If k＜j?1,then go back to(1.1);otherwise k=j?1,then set Fl(j):=Fl?1(r)+ (ls+jp)Wrj,kl(j):=r.

Step 2(Concatenation)If j=n,then stop.Otherwise set j:=j+1,α(r):= min{α(r),α(r,j?1)},if j≥α(r),then set r:=r+1,k:=r,α(r):=+∞and go to(1.1).If j＜α(r),then kl(j)=kl(j?1)and go back to the beginning of Step 2.

Note that the computation of Step 1 is α(r)=+(ls+jp)Wkj}.The goal of Step 2 is to decide whether kl(j)keeps the same value in the next round(and so the computation of the next round can saved).

Lemma 3.5Procedure l correctly solves problem 1|s-batch,b≥n,2wiCiin O(n)time for the worst case.

ProofThe correctness of Procedure l is based on the recursion equation(1)and lemmas 3.3～3.4.Let r1＜r2＜···＜rhbe the di ff erent values of kl(j)and let nibe the multiple number of ri(i=1,2,···,h).Then n1+n2+···+nh≤n.We call the set of steps that kl(j) keep the same value rithe“stage i”.In each stage,when kl(j)changes from rito ri+1,the computation of Step 1 takes at most O(n)time.Besides,the decision of kl(j)=kl(j+1)at each point ritakes O(ni)time in Step 2.Therefore the overall running time is O(n2).This completes the proof.

By using the above Procedure l we obtain the optimality function Fl(n),i.e.,the minimumCj(σ)subject to|σ|=l and the corresponding optimal schedules(l=1,2,···,n).Let=∑and C(l)max=ls+np.Then we have a set of n points

(if there is a tie,choose m as small as possible).Then Qmis also a Pareto optimal point, which dominates all Qlwith m＜l≤n.Hence all Pareto optimal points are included in {Q1,Q2,···,Qm}.In order to fi nd all Pareto optimal points,we can check these m points one by one.So we have the following procedure.

Selection Procedure

Step 0List the candidates of Pareto optimal points{Q1,Q2,···,Qm},where= min{:1≤l≤n}.

Step 1Q1is chosen.Let i1=1,l=1,k=1 and y=

Step 2If l=m,then go to Step 4,else set l:=l+1.

Step 4Return the Pareto optimal points{Qi1,Qi2,···,Qik}with i1=1 and ik=m.

By combining the above procedures together,we have the entire algorithm as follows.

Pareto Optimization Algorithm

Step 0(Initiation)Let F1(j)=(s+jp)W0jfor j=1,2,···,n.Let l=2.

Step 1Carry out the Procedure l.

Step 2(Backtrack)Determine the optimal scheduleof l batches by means of the decision function kl(j):the last batch is{kl(n)+1,···,n},the second last batch is{kl?1(kl(n))+ 1,···,kl(n)},and so on.

Step 3If l＜n,then set l:=l+1 and go back to Step 1;otherwise l=n,return all optimal scheduleswith di ff erent numbers of batches.

Step 4Carry out the Selection Procedure and produce all Pareto optimal points{Qi1,Qi2, ···,Qik}and the corresponding Pareto optimal schedules

To illustrate this algorithm,we describe the following numerical example.

ExampleSuppose that s=3,p1=p2=p3=p4=p5=p=1 and w1=7,w2= 4,w3=3,w4=3,w5=1.The implementation of the algorithm is as follows.At the initial step(l=1),=s+=8 and F1(1)=(s+p)w1=28,F1(2)=(s+2p)(w1+w2)= 55,F1(3)=84,F1(4)=119,F1(5)=144,i.e.,(144,8)is the fi rst Pareto-optimal point and the corresponding Pareto-optimal schedule is={(1,2,3,4,5)}.

Therefore we see that(144,8)and(128,31)are all possible Pareto optimal points. Finally,we come to the conclusion of this section.Theorem 3.6All Pareto optimal schedules of problem 1|s-batch,pj=p,b≥n|F(Cmax, can be determined in O(n3)time.

ProofFrom the Pareto Optimization Algorithm we get a sequence of points Qi1,Qi2, ···,Qik,withpossible Pareto optimal points.This is because each discarded point Qlis dominated by the previously chosen one.And the Selection Procedure takes O(n)time.Each Procedure l takes O(n2)time.In addition,compute all Wkr(0≤r＜k≤n)and sort weights take O(n2)and O(nlogn)time,respectively.Therefore,the overall running time of fi nding all Pareto optimalpoints is O(n3).This completes the proof.

From the proof we see that

This is the basic feature that makes the problem easy to solve.

§4.Concluding Remarks

The multicriteria scheduling on batching machines is a signi fi cant topic in scheduling theory. In the foregoing se∑ctions we have studied an unbounded model of serial-batching scheduling with criteria Cmaxandand established an algorithm for fi nding all Pareto optimal schedules in polynomial time.In fact,by slight modi fi cation,our algorithm can extend the corresponding bounded model(b＜n).In fact,we only need modifying l?1≤k＜j is max{l?1,j?b}≤k≤min{j?1,(l?1)b}in equation(1).We have studied 1|s-batch,b≥n|F(Cmax,Lmax)in [6]and 1|s-batch,b≥n or b＜n|Fin[7].More models with other criteria remain to further investigate.For example,the case of minimizing two maximum costs fmaxand gmaxsimultaneously,which is difficult to determine the number of Pareto optimal schedules,should be considered.

[1]ALBERS S,BRUCKER P.The complexity of one-machine batching problems[J].Discrete Applied Mathematics,1993,47(2):87-107.

[2]BRUCKER P.Scheduling Algorithms[M].Berlin:Springer,2001.

[3]BRUCKER P,GLADKY A,HOOGEVEEN H,et al.Scheduling a batching machine[J].Journal of Scheduling,1998,1:31-54.

[4]GRAHAM R L,LAWLER E L,LENSTRA J K,et al.Optimization and approximation in deterministic sequencing and scheduling:a survey[J].Annals of Discrete Mathematics,1979,5:287-326.

[5]HE Cheng,LIN Yi-xun,YUAN Jin-jiang.Bicriteria scheduling on a batching machine to minimize maximum lateness and makespan[J].Theoretical Computer Science,2007,381:234-240.

[6]HE Cheng,LIN Yi-xun,YUAN Jin-jiang.Bicriteria scheduling of minimizing maximum lateness and makespan on a serial-batching machine[J].Foundations of Computing and Decision Sciences,2008,33: 369-376.

[7]HE Cheng,LIN Yi-xun,YUAN Jin-jiang.A DP algorighm for minimizing makespan and total completion time on a series-batching machine[J].Informations Processing Letters,2009,109:603-607.

[8]HOOGEVEEN H.Multicriteria scheduling[J].European Journal of Operational Research,2005,167:592-623.

[9]HOOGEVEEN H.Single-machine scheduling to minimize a function of two or three maximum cost criteria[J]. Journal of Algorithms,1996,21:415-433.

[10]HOOGEVEEN J A,VAN de Velde S L.Minimizing total completion time and maximum cost simultaneously is solvable in polynomial time[J].Operation Research Letters,1995,17:205-208.

tion:90B35

CLC number:O221.6Document code:A

1002–0462(2014)02–0159–08

date:2012-05-31

Supported by the National Natural Science Foundation of China(11201121,11101383); Supported by the China Scholarship Council(201309895008);Supported bythe 2013GGJS-079;Supported by the 2011B110008

Biography:HE Cheng(1975-),female,native of Shangcheng,Henan,a lecturer of Henan University of Technology,Ph.D.,engages in the scheduling theory and its applications.