Int.J.Production Economics 76(2002)265–279
Parallel machine scheduling to minimize total tardiness
FaroukYalaoui*,Chengbin Chu
Uni v ersit !e
de Technolo g ie de Troyes,Industrial Systems Optimization Laboratory,12rue Marie Curie,St.,BP-2060,10010Troyes Cedex,France
Received 19July 2000;accepted 11June 2001
Abstract
井村雅代
This paper address,using an exact method,the identical parallel machine scheduling problem to minimize total tardiness.In this problem,a t of jobs has to be scheduled,without preemption,on identical parallel machines.Each machine is able to treat only one job at a time.In order to prune the arch tree,dominance properties are proved and lower and upper bounding schemes are propod.A branch and bound (BAB)algorithm is developed taking into account the theoretical properties,lower and upper bounds.This BAB algorithm has been tested on a large t of randomly generated medium-sized problems.Computational results demonstrate the effectiveness of our appr
oach over existing methods in the literature.r 2002Elvier Science B.V.All rights rerved.
Keywords:Parallel machine scheduling;Total tardiness;Dominance properties;Lower bound;Branch and bound
1.Introduction
This paper deals with the identical parallel machine scheduling problem to minimize total tardiness.Minimizing total tardiness is among the most interesting criteria for production systems,especially in the current situation where competition is becoming more and more intensive.This paper aims at developing an exact method to solve this problem.
This problem can be described as follows.A t of N jobs is to be scheduled without preemption on M identical parallel machines,which are assumed to be continuously available.Each machine can process at most one job at a time.The jobs are assumed to be all available at time zero.With each job i ;are associated a processing time p i and a due date d i :The objective is to determine a schedule such that the total tardiness of jobs is minimized.A job is said to be ardy if its completion time C i is greater than its due date d i and its tardiness is measured by C i Àd i :If a job is not tardy,its tardiness is t to 0,without loss of generality.Therefore,the tardiness of job i is given by max
ðC i Àd i ;0Þ:
According to Koulamas [1],the problem considered here is at least binary NP-hard since Du and Leung
[2]showed that the problem with M ¼1is binary NP-hard.Lenstra et al.[3]also showed that the problem with two machines was binary NP-hard.Nevertheless the exact complexity of this problem remains open.The literature on this problem with M >1;is relatively limited compared to its single machine counterpart.*Corresponding author.Tel.:+33-325715626;fax:+33-325715649.
E-mail address:yalaoui@univ-troyes.fr (F.Yalaoui).
0925-5273/02/$-e front matter r 2002Elvier Science B.V.All rights rerved.
PII:S 0925-5273(01)00175-X
This remarkwas already made by Koulamas in 1994[1]in a very interesting workwhere a state of the art on tardiness minimization problems was prented.
The development of heuristics has been carried out in some rearch works.Montagne [4]introduced
a rule called Montagne’s ratio method (MRM)for total weighted tardiness minimization.The MRM rule schedules jobs in increasing order of the ratio p i =ðN Â%p
Àd i Þwith %p ¼P N i ¼1p i =N being the average processing time.In 1971,Wilkerson and Irwin [5]developed a method,noted WI,bad on neighbor arch to minimize the average tardiness on a machine.This method was formally prented by Baker [6]and ud to solve the parallel machines ca.It consists of ranking the jobs according to the earliest due date (EDD)rule,of lecting an unscheduled job,with the earliest due date,and assign it to a machine according to the following rule:if the job lected can be added after a partial schedule without being late,then the job is assigned on the machine such that it can be completed as cloly as possible to its due date,otherwi it is assigned to the earliest available machine.According to Baker’s experimentation,the WI gave results about
1.6%from optimal solutions for small-sized problems.In 1979,Dogramaci and Surkis [7],propod a heuristic,for parallel machine problem,using list algorithms.This heuristic makes it possible to obtain three different solutions,by using three priority rules independently:shortest processing time (SPT),EDD and minimum slack(the slackof a job j is defined as SL j ¼d j Àp j ).The best one out of the three solutions is retained.In 1991,Ho and Chang [8]built an assignment rule noted traffic priori
ty index (TPI).This method combines the SPT and EDD rules using a new measurement called traffic congestion ratio (TCR).Then,they built heuristics for the cas with one or identical machine.The heuristics consist of building a first solution by scheduling jobs in increasing order of their priority index,then an improvement of this solution is obtained using permutation technique of WI method previously quoted.Koulamas prented veral works to solve this problem.First in 1994,he developed a heuristic,called KPM,which is an extension to parallel machines of PSK heuristic of Panwalkar et al.[9],conceived initially for the single machine problem.This method gave,according to the authors,more interesting results than other heuristics previously prented.In 1997,Koulamas propod a method called PDEC bad on method of Potts and Wasnhove [10]for the single machine problem –this method is bad on the combination of a decomposition procedure and the WI method.The PDEC method is a decomposition procedure coupled with PSK heuristic for parallel machine problem.It consists of bringing backthe problem with parallel machines to a system of veral problems with a single machine on which theoretical properties are available,where the PSK method is applicable.In addition to the PSK method,Koulamas [11]developed hybrid simulated annealing (HSA)heuristic bad on simulated annealing.According to the authors the two methods are effective compared to the others.But one of the disadvantages of HSA is the relatively long completion time.We have also highest priority job first (HPJF)method of Chen et al.[12],which is an e
xtension of the WI method supplemented by various priority rules such as:Minimum processing time first ðpriority ¼1=processing time Þ;Maximum processing time first ðpriority ¼processing time Þ;Minimum deadline first ðpriority ¼1=due date Þand Maximum deadline first ðpriority ¼due date Þ:In 1997,Alidaee and Rosa [13]propod a heuristic that is an extension of the modified due date (MDD)method of Baker and Bertrand [14].This last method was,according to the experimentation of authors,quite effective for the parallel machine problem.收款收据填写样本
As far as exact methods are concerned,to the best of our knowledge,only Azizoglu and Kirca
[15]propod a branch and bound (BAB)approach to handle the same problem we consider here.Nevertheless,optimal methods are available for problems very similar to our problem at hand.Among the methods,we can refer to the formulation of Lawler [16]of the parallel machine problem as a transportation problem when the job processing times are identical.In 1965,assuming that all jobs have identical due dates,Root [17]developed a method by construction.For their part,Pritsker et al.[18]in 1969,modeled with 0–1linear programming the limited resource problem where the minimization of total tardiness on identical parallel machines is a special ca.By considering identical due dates and processing times,Elmaghraby and Parkin 1974[19],
F.Yalaoui,C.Chu /Int.J.Production Economics 76(2002)265–279
扩散作用>东南大学研招办266
F.Yalaoui,C.Chu/Int.J.Production Economics76(2002)265–279267 propod a branch and bound to minimize a function of penalties related to tardiness.Three years later, this method was taken again and improved by Barnes and Brennan[20].
In addition to previous quoted works,there exist a t of studies that deal with parallel machine scheduling problem but with alternatives.For the minimization of the total weighted tardiness we have for example:Arkin and Roundy[21]or Emmons and Pinedo[22];in the ca of uniform or unspecified parallel machines or in the stochastic ca of scheduling:Guinet[23]or Emmons[24]or Azizoglu and Kirca[25].
2.Theoritical properties
The problem considered in this paper is to schedule N jobs indexed from1to N on M identical machines indexed from1to M:Each job iði¼1;2;y;NÞhas a processing time p i and a due date d i:Before proceeding,note that a schedule corresponds to a unique permutation on the t f1;2;y;N g.In fact,for any given permutation,a corresponding schedule can be constructed by assigning the next unscheduled job in the list to the machine available the earliest,ties broken by lecting the leas
t indexed machine. Converly,for any given mi-active schedule,a permutation can be obtained by ordering the jobs in non decreasing starting times,ties broken in non decreasing order of machine indexes.As a conquence,a partial schedule is a permutation of a subt of f1;2;y;N g.In the remainder,the word‘‘schedule’’indifferently refers to a partial schedule or complete schedule,unless additional precision is given.The following notation will be ud.
征文主题
JðKÞt of jobs scheduled in schedule Karean
J mðKÞt of jobs scheduled on machine m in schedule K
D iðKÞcompletion time of the job immediately preceding job i in schedule K:If job i is thefirst job in K;
D iðKÞis t to0,without loss of generality
C IðKÞcompletion time of job i in schedule K
T mðKÞtotal tardiness of the jobs scheduled on machine m in schedule K
f mðKÞcompletion time of the last scheduled job on machine m in schedule K
mðKÞthe machine available the earliest in schedule K(the machine with the smallest f mðKÞ)
K3i the new schedule obtained by adding job i behind by adding job i on the machine mðKÞ) OðK;iÞthe schedule compod of K3i;completed by the partial optimal schedule of remaining jobs. When there is no ambiguity,JðKÞ;J mðKÞ;D iðKÞ;C iðKÞ;T mðKÞ;f mðKÞ;and mðKÞare simplified into J;J m;
D i;C i;T m;f m and m;respectively.
Let m0ðKÞbe the machine available just after machine mðKÞand before all other machines of the system. Bad on the general properties prented in[26]and[27],we have:
Theorem1.There is an optimal schedule such that the number of jobs scheduled on any machine is less than or equal to NÀMþ1:
Corollary1.Any partial schedule K such that more than NÀMþ1jobs are scheduled on a machine can be discarded.In any optimal schedule resultin g from K;the number of additional jobs on a machine m is at most U mðKÞ¼min½N2Mþ12j J mðKÞj;N2j JðKÞj :
In the remainder,we denote by UÃthe maximum over all U mðKÞ’
U*¼max
U mðKÞð1Þ1p m p M
and also U¼U mðKÞ¼min½NÀMþ1Àj J mðKÞj;NÀj JðKÞj :
2.1.Dominance properties
In this subction,some dominance properties are proved in order to eliminate dominated partial schedules and therefore to speed up the branch and bound algorithm.For the minimization of total tardiness on identical parallel machines we obtained the following properties.
Theorem 2.For any partial schedule K and for any job i unscheduled in K ;if there is another job j unscheduled in K such that :p j p p i ;and ðp i Àp j ÞðU ÃÀ1Þp min ðd i Àp i ;f m 0ÞÀmax ðd j Àp j ;f m Þ;then O ðK ;i Þis dominated .
Theorem 3.For any partial schedule K and for any job i unscheduled in K ;if there is another job j unscheduled in K such that :0p p j Àp i p p ;d j p f m þp j p d i and ðp j Àp i ÞðU À1Þp min ðf m 0;d i Àp i ÞÀf m ;then O ðK ;i Þis dominated,where p is the processin g time of the unscheduled jobs .
The two properties can be proved using the same scheme.In this scheme,two cas are examined:In the first ca jobs i and j are scheduled on the same machine m whereas in the cond,
they are scheduled on different machines.For both cas,we checkwhether there is another schedule S at least as good as O ðK ;i Þ;by interchanging the positions of jobs i and j :To simplify the notation,O ðK ;i Þis noted as S :By definition,the total tardiness of schedule S is
T ðS Þ¼X
M k ¼1T k ðS Þ¼X N h ¼1max ðC h ðS ÞÀd h ;0Þ:ð2Þ
In the proofs that will follow,we will consider the following notation:
‘‘Ca 1’’refers to the ca where jobs i and j are both scheduled on machine m in S :‘‘Ca 2’’refers to the other ca.A i -j is the t of jobs scheduled between jobs i and j on machine m in S .A k is the t of jobs scheduled after job k on the same machine in S :
Proof of Theorem 2.The conditions of the theorem imply:
min ðd i Àp i ;f m 0ÞÀmax ðd j Àp j ;f m ÞX 0:
Therefore
d i Àp i X d j Àp j )d i X d j þðp i Àp j ÞX d j ;
d i Àp i X f m )d i X f m þp i :
Ca 1:if jobs i and j are both scheduled on machine m ;construct a new schedule S 0by permuting jobs i and j :Let t be the starting time of job j in S :
In this new schedule,the completion time and hence the tardiness of any job between i and j is decread.Therefore
T ðS 0ÞÀT ðS Þp T i ðS 0ÞþT j ðS 0ÞÀT i ðS ÞÀT j ðS Þ
¼max ðf m þp j Àd j ;0Þþmax ðt þp j Àd i ;0ÞÀmax ðf m þp i Àd i ;0ÞÀmax ðt þp j Àd j ;0Þ
¼max ðf m þp j Àd j ;0Þþmax ðt þp j Àd i ;0ÞÀmax ðt þp j Àd j ;0Þ:
F.Yalaoui,C.Chu /Int.J.Production Economics 76(2002)265–279
种植大棚
268
If t þp j Àd i >0then t þp j Àd j >0;
T ðS 0ÞÀT ðS Þp max ðf m þp j Àd j ;0Þþt þp j Àd i Àt Àp j þd j ¼max ðf m ;d j Àp j Þþp j Àd i
p max ðf m ;d j Àp j ÞÀðd i Àp i Þ
p max ðf m ;d j Àp j ÞÀmin ðd i Àp i ;f m 0Þp 0:
If t þp j Àd i p 0then T ðS 0ÞÀT ðS Þp max ðf m þp j Àd j ;0ÞÀmax ðt þp j Àd j ;0Þp 0:
Ca 2:If job j is scheduled on a machine different from m ;the completion time and hence the tardiness of jobs initially scheduled after job j is incread at most by ðp i Àp j Þ:The number of such jobs is at most ðU ÃÀ1Þ:The tardiness of jobs initially scheduled after i is decread.Let t be the starting time of job j in S :Then
小学语文评课T ðS 0ÞÀT ðS Þp ðU *À1Þðp i Àp j Þþmax ðf m þp j Àd j ;0Þþmax ðt Àd i þp i ;0ÞÀmax ðt þp j Àd j ;0Þ
p ðU *À1Þðp i Àp j Þþmax ðf m þp j Àd j ;0Þþmax ðt Àd i þp i ;0ÞÀt Àp j þd j
p ðU *À1Þðp i Àp j Þþmax ðf m ;d j Àp j ÞÀmin ð0;d i Àp i Àt ÞÀt
p ðU *À1Þðp i Àp j Þþmax ðf m ;d j Àp j ÞÀmin ðt ;d i Àp i Þ
p ðU *À1Þðp i Àp j Þþmax ðf m ;d j Àp j ÞÀmin ðf m 0;d i Àp i Þ:
T ðS 0ÞÀT ðS Þp 0:&
Proof of Theorem 3.
Ca 1:By construction we have
1.X
k a m T k ðS 0Þ¼X k a m T k ðS Þ;
2.X
h A A i -j max ðC h ðS 0ÞÀd h ;0Þp X h A A i -j max ðC h ðS ÞÀd h ;0Þþðp j Àp i ÞÂA i -j
and X
h A A j max ðC h ðS 0ÞÀd h ;0Þp X h A A j max ðC h ðS ÞÀd h ;0Þ
since p j p p i ;
3.
D i ðS 0Þ¼D j ðS Þþðp j Àp i Þ
and
4.
f m þp i p f m þp j p D j ðS Þþp j :
Then T ðS 0ÞÀT ðS Þp ðp j Àp i ÞÂA i -j þD T 3þD T 4with D T 3¼max ðD i ðS 0Þþp i Àd i ;0ÞÀmax ðf m þ
p i Àd i ;0Þwe have d i X f m þp j X f m þp i then D T 3¼max ðD i ðS 0Þþp i Àd i ;0Þ¼max ðD i ðS Þþp j Àd i ;0Þand D T 4¼max ðf m þp j Àd j ;0ÞÀmax ðD j ðS Þþp j Àd j ;0Þ:F.Yalaoui,C.Chu /Int.J.Production Economics 76(2002)265–279269
