Scheduling to Minimize Average Completion Time Oline and Online Approximation Algorithms Dedicated to the memory of Gene Lawler Leslie A Hall1 Andreas S Schulz David B Shmoys Joel Wein May revised March Abstract In this paper we i n troduce two general techniques for the design and analysis of approxi mation algorithms for NP hard scheduling problems in which the objective is to minimize the weighted sum of the job completion times Fo r a v ariety o f s c heduling models these techniques yield the rst algorithms that are guaranteed to nd schedules that have objective function value within a constant factor of the optimum In the rst approach we use an optimal solution to a linear programming relaxation in order to guide a simple listscheduling rule Consequently w e also obtain results about the strength of the relaxation Our second approach yields online al gorithms for these problems in this setting we are scheduling jobs that continually arrive t o b e processed and for each time t w e m ust construct the schedule until time t without any k n o wl edge of the jobs that will arrive afterwards Our online technique yields constant performance guarantees for a variety o f s c heduling environments and in some cases essentially matches the performance of our o line LPbased algorithms lahjhuedu Department of Mathematical Sciences The Johns Hopkins University Baltimore MD schulzmath tu berlin de Department of Mathematics Technical University of Berlin Berlin Germany shmoyscs cornell edu 􀀀S c hool of Operations Research Industrial Engineering and Department of Computer Science Cornell University Ithaca NY weinmempoly edu Department of Computer Science Polytechnic University Brooklyn NY Introduction In his seminal paper Graham showed that when jobs are scheduled on identical parallel machines by a listscheduling rule then the resulting schedule is guaranteed to be of length within a factor of two of optimal This result is often viewed as the starting point for research o n t h e design and analysis of approximation algorithms A 􀀀approximation algorithm is a polynomialtime algorithm that always nds a solution of objective function value within a factor of of optimal is also referred to as the performance g u a r antee of the algorithm In the intervening thirty y ears there has been a great deal of work on approximation algorithms for NP hard optimization problems and in particular for scheduling problems with minmax objective functions However until recently much less was known about approximation algorithms for NP hard scheduling problems with min sum objective functions In this paper we i n troduce two general techniques for the design of approximation algorithms for NP hard scheduling problems in which the goal is to minimize the weighted sum of the job completion times these techniques yield the rst constant performance guarantees for a variety o f scheduling models Whereas little was known about approximation algorithms for these problems there is an extensive literature on their polyhedral structure Queyranne Schulz give a comprehensive s u r v ey of this area of research For singlemachine models several linear program ming relaxations have been considered and they yield suciently strong lower bounds to allow instances of modest size to be solved by e n umerative methods Our rst technique was motivated by this success we s h o w that Grahams listscheduling algorithm when guided by an optimal so lution to a linear relaxation is guaranteed to produce a schedule of total weighted completion time within a constant factor of optimal A consequence of these results is that the lower bound given by the linear programming relaxation is also guaranteed to be within a constant factor of the true optimum Our second technique is a general framework for designing online algorithms to minimize total weighted completion time in scheduling environments with release dates In this setting we a r e scheduling jobs that intermittently arrive to be processed and for each time t w e m ust construct the schedule until time t without any k n o wledge of the jobs that will arrive after time t Our online algorithm relies only on the existence of an oline approximation algorithm for a problem that is closely related to nding a minimumlength schedule in that environment For several of the problems we consider the performance guarantee proved for this online technique asymptotically matches the guarantee proved for our oline LPbased algorithms The problem of scheduling a single machine to minimize the total weighted job completion time is one of the most basic problems in the area of scheduling theory W e are given n jobs andeach jo b j has a speci ed positive w eight wj and a nonnegative processing time pj jn The jobs must be processed without interruption and the machine can process at most one job at a time P We let Cj denote the completion time of job j the goal is to minimize j wj Cj or equivalently P n Consider some optimal schedule and let Cj denote the completion time of job j in it j w Pj Cj thus j wj Cj denotes the optimal value We shall present a n umber of approximation algorithms that are based upon solving a particular relaxation throughout the paper we shall use the notation P Cj to denote the value assigned to job j by the relaxation and so j wjCj is a lower bound on P e j wj Cj Furthermore for each a p p r o ximation algorithm that we shall consider we u s e Cj to denote the completion time of job j in the schedule that it computes For the singlemachine problem stated above Smith showed that sequencing in or der of nondecreasing ratio pj wj produces an optimal schedule We shall be interested in more constrained strongly NP hard problems in which e a c h job j cannot begin processing before a speci ed release date rj jn or there is a partial order on the jobs where jk is a precedence c onstraint that requires job k to begin processing no earlier than the completion time of job j We g i v e a approximation algorithm for the case in which there are precedence constraints but no nontrivial release dates In contrast Ravi Agrawal Klein gave P an O log n log j wj approximation algorithm and Even Naor Rao Schieber recently P improved this to O log n log log j wj For the case in which there are also release dates we give a approximation algorithm In fact with only slightly larger constants these results extend to the model with m identical parallel machines in which each j o b j must be processed without interruption for pj time units on some machine Furthermore these results extend to models in which preemption is allowed that is the processing of a job may b e i n terrupted and resumed at a P later time possibly on a dierent m a c hine Even for the special case of minimizing j Cj these algorithms are the rst shown to have sublogarithmic performance guarantees Our results were motivated by r e c e n t w ork using polyhedral methods for scheduling problems and in particular singlemachine scheduling problems There are a numb e r o f i n teresting papers in this area both for characterizations of polynomiallysolvable special cases and for computing optimal solutions starting with the work of Balas Wolsey Dye r W olsey and Queyranne For a thorough survey of results in this area the reader is referred to the survey of Queyranne Schulz Several of our algorithms are based on the work of Wolsey and Queyranne who proposed a linear programming relaxation in which each d e c i s i o n v ariable Cj j n corresponds to the completion time of job j in a schedule For the unconstrained singlemachine scheduling problem solved by Smith this formulation provides an exact characterization Since there is a polynomialtime separation algorithm the relaxation can be solved in polynomial time even if additional constraints are added to enforce release dates or precedence constraints For these more constrained variants we will show that an optimal solution to the linear programming formulation can be used to derive a s c hedule that is within a constant factor of the LP optimum If a linear programming relaxation for a problem is shown to have an optimal value that is always within a factor of of the true optimum for that problem then we shall call it a 􀀀relaxation of the problem For example for the problem of minimizing total weighted completion time on a single machine subject to precedence constraints we s h o w that the formulation of Queyranne and Wolsey is a relaxation Our algorithm and its analysis are also inspired by recent w ork of Phillips Stein Wein for the case in which there are release dates but no precedence constraints They introduced the notion of constructing a nearoptimal nonpreemptive s c hedule by s c heduling the jobs in order of their completion times in a preemptive s c hedule this idea led to a simple approximation algorithm to minimize nonpreemptively the average completion time of a set of jobs with release dates on one machine i e  in the special case where wj jn They also introduced a timeindexed linear programming formulation from which they constructed nearoptimal preemptive s c hedules for a variety of models in which the objective is to minimize the average weighted completion time Based on these ideas they gave a p p r o ximation algorithms for four models with this objective scheduling preemptively or nonpreemptively on one machine or m identical parallel machines Let be an arbitrarily small positive constant for both preemptive models their performance guarantee is for one machine their nonpreemptive guarantee is and for m identical parallel machines their guarantee is For all four scheduling models our techniques signi cantly improve upon these performance guarantees Our results also have implications for other wellstudied formulations of these singlemachine scheduling problems For example since the formulation in completiontime variables is weaker than both a linearordering formulation of Potts and a timeindexed formulation of Dyer Wolsey we see that each of these is also a relaxation in the case mentioned above Van den Akker evaluated the eectiveness of several heuristics for the model in which there are release dates but no precedence constraints and concluded that the following one is particularly eective in practice solve the timeindexed relaxation and schedule the jobs in the order in which they complete in an average sense in the optimal fractional solution Our analysis implies that this procedure is a approximation algorithm and hence it can be viewed as a theoretical validation of this approach to nding a good schedule We also introduce a polynomialsize variant of the timeindexed formulation called an interval􀀀 indexed formulation W e show that such formulations are eective in the design of approximation algorithms for scheduling jobs constrained by release dates on unrelated p arallel machines In this scheduling environment each j o b j must be assigned to some machine i and requires pij time units when processed on machine i f m g W e i n troduce new rounding algorithms that yield the rst constant performance guarantee for this problem All of our results build on earlier research on computing nearoptimal solutions for other schedul ing models by rounding optimal solutions to linear relaxations The earlier results give t wo general approaches for exploiting the solution to a linear relaxation In work of Lenstra Shmoy s  T ardos Lin Vitter Trick and Shmoy s T ardos the linear program is used to guide the assignment o f j o b s t o m a c hines whereas in the work of Munier Konig the linear program is used to derive priorities for jobs that are used in constructing the schedule We shall use a variant of the latter approach extensively but will also in some settings rely on the former approach We then turn to our second technique a general method for devising online algorithms to minimize the total weighted completion time in any s c heduling environment with release dates We show t h a t i f w e assign jobs to intervals by applying a type of greedy strategy then the resulting performance guarantee is within a factor of four of the performance guarantee of the subroutine used to make the greedy selection This technique is similar to one used by Blum Chalasani Coppersmith Pulleyblank Raghavan Sudan to devise an approximation algorithm for the minimum latency problem which i s t h e v ariant of the traveling salesman problem in which o n e wishes to minimize the sum of the travel times to reach e a c h c i t y rather than the time to reach the last city W e shall use this technique to devise online approximation algorithms and in several cases the resulting algorithm has nearly as good a performance guarantee as the oline LPbased technique From the perspective of computing optimal solutions minimizing the total weighted completion time is equivalent to minimizing the total weighted owtime where the owtime of a job is the time that elapses between its release date and its completion time However these two objective functions are quite dierent from the perspective o f a p p r o ximation especially within the context of online algorithms The owtime objective function is of more immediate practical relevance since the mere fact that a job was released later should not make it more palatable that a long times elapses between its release date and its completion time However even in the oline setting one cannot hope for strong performance guarantees for the owtime objective function Kellerer Tautenhahn Woeginger showed that unless P NP for any andany 1 there does not exist an n approximation algorithm for nonpreemptively scheduling jobs on a single machine subject to release dates with the objective of minimizing the total owtime Since there are a numb e r o f s c heduling models considered in this paper it will be convenient t o refer to them in the notation of Graham Lawler Lenstra Rinnooy Kan We summarize the most relevant features of this notation here Each problem that we shall consider can be abbreviated jj where i is either P or R denoting that there is either one machine m identical parallel machines or m unrelated parallel machines ii contains some subset of rj prec pmtn and pj where these denote respectively the presence of nontrivial release date constraints precedence constraints the ability t o s c hedule preemptively and the restriction P that all jobs are of unit size and iii is wjCj indicating that we are minimizing the total P weighted job completion time For example jrj prec j wj Cj refers to the problem of minimizing nonpreemptively the total weighted completion time on one machine subject to releasedate and precedence constraints We shall assume without loss of generality that the data for each instance is integral and that the data is preprocessed so that in any feasible schedule there does not exist a job that can be completed at time hence no job can complete before time Finally note that we have assumed that no job has weight primarily to ensure that the pj wj ordering is wellde ned all of our results can be extended to the more general setting A summary of our results along with a comparison to previously known performance guarantees can be found in Table Model O line Online Known New Known New P jprecj wj Cj P O log n log log wjj P jrj prec pj j wj Cj P jrj prec pmtnj wj Cj P jrj j wj Cj P jrj p r e c j wj Cj P P jprec pj j wj Cj 􀀀 m P P jprec pmtnj wj Cj 􀀀 m P P jrj prec pj j wj Cj P P jrj prec pmtnj wj Cj P P jrj j wj Cj 􀀀 m P P jrj p r e c j wj Cj P Rjrij j wj Cj O log n Table A summary of performance guarantees for the minimization of the total weighted completion time The Known columns list the best previously known performance guarantees whereas the New columns list new results from this paper indicates the absence of a relevant result is an arbitrar ily small constant and m denotes the number of parallel machines The best previously known performance guarantee with precedence constraints is due to Even Naor Rao Schieber The other bounds are due to Phillips Stein Wein The approach of applying a listscheduling rule in which the jobs are ordered based on solving a linear program can easily be extended to a wide spectrum of scheduling problems and we believe that it will have further consequences for the design of approximation algorithms For several other basic scheduling models we h a ve considered analogous formulations and we conjecture them to yield substantially stronger guarantees than are presently known Our work has already stimulated a great deal of subsequent research Many of the bounds given in this paper have been improved for example in work by Chakrabarti Phillips Schulz Shmoys Stein Wein Goemans Chekuri Motwani Natarajan Stein Wang b  and Schulz Skutella Furthermore similar techniques have yielded improved performance guarantees for other scheduling models as in work by M ohring Schater Schulz Chakrabarti Muthukrishnan and Chudak Shmoys Singlemachine scheduling problems In this section we p r e s e n t approximation algorithms for several singlemachine scheduling prob lems we consider variants in which the set of jobs may be precedence constrained and in which additionally each j o b j may h a ve a release date rj W e use jk to denote the constraint t h a t j o b j must be completed before job k starts We denote the entire set of jobs f n g as N and for any subset SN w e use the following shorthand notation X pS pj rmin S min rj and rmax S m ax rj jS jS jS P We shall also require the quantity jS pj which w e shall denote by pS The basis of our approximation algorithms is a linear programming relaxation that uses as P variables the completion times Cj W e can formulate the problem jrj prec j wj Cj in the following way where the constraints ensure that the variables CC n specify a feasible set of completion times Xn minimize wj Cj j subject to Cj rj pj j n Ck Cj pk for each pair j k such that j k Ck Cj pk or Cj Ck pj for each pair j k The diculty with this characterization is that the socalled disjunctive constraints are not linear inequalities and cannot be modeled using linear inequalities Instead we use a class of valid inequalities introduced by Queyranne and Wolsey that are motivated by considering Smiths rule for scheduling the jobs when there are no release dates or precedence constraints Smith proved that a schedule is optimal if and only if the jobs are scheduled in order of non PP decreasing ratio pj wj As aresult ifwe set wj pj for all j then the sum j wj Cjj pjCj is invariant for any ordering of the jobs In particular for the ordering n if there is no idle Pj time in the schedule then Cj pk therefore for any s c hedule we can write down the valid k constraint n nj nj X XX XX pjCj pj pk pkpj pN pN j jk jk where the inequality results from the possibility of idle time in the schedule Consider the completion times for a feasible schedule Cj jN F or each subset SN we can consider the instance induced by S the induced completion times Cj jS correspond to a feasible schedule for this smaller instance Hence we can apply the previous inequality to each subset and derive the following valid inequalities X pjCj pS pS for each SN jS We note that these inequalities remain valid even if we allow the schedule to be preemptive that is the processing of a job may b e i n terrupted and continued at a later point in time Fur thermore Queyranne and Wolsey have s h o wn that constraints de ne the linear transformation of a supermodular polyhedron and are thus sucient to describe the convex hull P of completiontime vectors of feasible schedules for instances of jj wj Cj These constraints are no longer sucient however if we add constraints such as and that enforce release dates and precedence constraints respectively Although we d o n o t h a ve exact characterizations for PP P jprecj wjCj jrj j wjCj or jrj prec j wj Cj w e will show that linear relaxations can be used to nd nearoptimal solutions for each of them The key to the quality of approximation deriving from these relaxations is the following lemma Lemma Let CC n satisfy and assume without loss of generality that CCn Then for each job jn j X Cj pk k Proof Inequality for S f j g implies that j X pkCk pSpS pS k Since Ck Cj for each kj w e have jj XX Cj pS Cj pk pkCk pS kk Pj or equivalently Cj pk k A feasible solution CCn to need not correspond to a feasible schedule the intervals Cj pj Cj n are not constrained to be disjoint If this solution actually corresponds j Pjto a feasible schedule then Cj pk jn Lemma states that merely satisfying k Pjthe constraints is sucient to obtain a relaxation of this Cj pk jn It k is this intuition that underlies the approximation algorithms of this section Singlemachine scheduling with precedence constraints P We begin by presenting a approximation algorithm for jprecj wjCj based on the linear pro P n gramming formulation that minimizes j wjCj subject to constraints and Consider the following heuristic for producing a schedule rst we obtain an optimal solution to the linear program CCn then we s c hedule the jobs in order of nondecreasing Cj where ties are bro ken by c hoosing an order that is consistent with the precedence relation We h a ve only assumed nonnegative processing times and so if jk and pk then it is possible that Cj Ck We refer to this algorithm as Scheduleby Cj since the jobs are ordered according to their completion times in the linear programming solution Observe that constraints ensure that the resulting schedule will be consistent with the precedence constraints ee Lemma Let CC denote the completion times in some optimal schedule and CCn n PP e denote the completion times in the schedule found by Scheduleby Cj T hen j wj Cjj wjCj Proof For simplicity w e assume that the jobs have been renumbered so that CCn therefore for S f j g e Cj pS e By Lemma we immediately obtain Cj Cj Since wj for each jo b jn and PP j wj Cjj wj Cj the result follows Queyranne has shown that the linear program given by and is solvable in polynomial time via the ellipsoid algorithm the key observation is that there is a polynomialtime separation algorithm for the exponentially large class of constraints Hence we h a ve established the following theorem P Theorem Scheduleby C j is a 􀀀approximation algorithm for jprecj wj Cj Next we present a set of instances suggested by Margot and Queyranne which s h o w that our analysis of this heuristic is tight Consider an instance with k jobs with jk pj jk k jk wj j kk jk k Also j kj and j kj fo r jk and kk If Cj denotes the optimal LP P k completion time then Cj jk where is chosen so that pjCj pN j pN for N f kg In the optimal schedule the jobs are processed in the order k k kk Its value is kk On the other hand one possible ordering generated by the algorithm Scheduleby Cj is k with objective function value equal to k Hence the ratio between the heuristic value and the optimal value approaches as k In this example the bad behavior of the heuristic results from an unlucky breaking of ties in fact by perturbing the data it is possible to force the algorithm to choose an equivalently bad solution One manner in which the linear program given by and can be strengthened is by adding a set of socalled series constraints see Queyranne Schulz When these are added to the model Queyranne Wang showed that this gives an exact characterization of the feasible completiontime vectors in the case that the partial order associated with the precedence relation is seriesparallel It is interesting to note however that these constraints cannot immediately strengthen our approximation result since the preceding example remains unaected when these new inequalities are added We conclude this section with a few additional observations First notice that in equation we h a ve discarded the term pS By analyzing the inequality more carefully it is possible to show that Scheduleby Cj i s a approximation algorithm see Schulz a for the details n Second notice that our algorithmic results yield the following corollary concerning the quality of the optimal value of the linear program P Corollary The linear program and is a 􀀀relaxation of jprecj wjCj In fact by the observations just made this linear program is actually a relaxation n Furthermore we n o w give an example that shows that this analysis of the quality of the linear program is asymptotically tight a s w ell Consider an instance with n unitlength jobs in which the rst n j o b s m ust precede job n but are otherwise independent Let wj fo r jn and wn The optimal LP solution will set Cj nn for jn and Cn nn t h us the overall LP objective v alue is nn On the other hand the heuristic schedule which is in fact an optimal schedule has value n thus as n the ratio between the two v alues approaches Note that this example is not a bad example for the algorithm and the earlier example is not a bad example for the linear program Moreover this second example has a seriesparallel precedence partial order and so by adding the series inequalities to the linear program and we w ould ensure that its extremepoint solutions also satisfy the disjunctive constraints The results of this section have implications for other LP formulations as well we g i v e t wo basic examples here The rst formulation which w as given by P otts uses linear ordering variables ij where ij implies that job i precedes job j in the chosen schedule Xn minimize wj Cj j subject to Xn Cj pi ij pj jn i ij ji ij nij ijjk ki ijk nij k or i j k ij ij nij ij ij nij Notice of course that the Cj may be made implicit in this formulation and from a set of ij P n one could construct Cji pi ij pj S c hulz a has shown that these Cj are feasible for the linear program given by and consequently the optimal value for the formulation in linearordering variables is at least the optimal value for the one given by t h e Cj decision variables P Hence the linearordering formulation is also a relaxation of jprecj wj Cj In addition the linear ordering formulation is polynomial in size and thus by using it in conjunction with our algorithm we can actually avoid the use of the ellipsoid algorithm in obtaining an optimal LP solution The next formulation which w as given by D y er Wolsey uses timeindexed variables In this formulation we x a time horizon T pN b y which all jobs will be completed in any feasible schedule without unnecessary idle time For each j o b jn and each tT we de ne xjt if job j completes processing at time t W e then have the following LP relaxation T Xn X minimize wj txjt jt subject to T X xjt jn t tX t pkX xjs xks if j k t pj T pk s s nminft pjX X Tg xjs t T j s t xjt j n t T xjt t p j Equation says that each j o b m ust be assigned to some time slot inequality ensures that there is at most one job undergoing processing in the time interval tt and inequalities enforce the precedence constraints since they say that for jk in order for k to be completed by time tpk jo b j must be completed by t i m e t for all t In Section we will also introduce a closely related formulation that is polynomial in size and show h o w to use it to design approximation algorithms PT Ifwe de ne Cj tx where x is a feasible solution to the linear program then tpj jt CC nare guaranteed to be feasible for and Schulz a hence the timeindexed formulation is a relaxation as well Although our analysis provides an identical performance guarantee for each of these three formulations its seems likely that these formulations are not equivalently strong for neither the linearordering formulation nor the timeindexed formulation have w e been able to show that our analysis is tight Clearly f o r a n y LPbased approximation algorithm the choice of formulation can have a signi cant impact on the performance guarantee that one can hope to prove Singlemachine scheduling with precedence constraints and release dates We next consider a more general model in which in addition to precedence constraints each job j has a release date rjwhen it rst becomes available for processing We will demonstrate that an algorithm analogous to the one of the previous section is a approximation algorithm Consider the following linear program given by and Suppose we solve the linear program to obtain an optimal solution CCn for simplicity w e assume as before that CCn Given the Cj w e use the same heuristic Scheduleby Cj construct the minimal feasible schedule in which the jobs are ordered according to nondecreasing Cj In this case we might i n troduce idle time before the start of job j if rjis greater than the time at which job j completes then job j begins processing at time rj Lemma Let CCnbe an optimal solution to the linear program dened b y ee and and let CCndenote the completion times in the schedule found by Scheduleby Cj e Then for j nCj Cj Proof Letus x j and de ne S f j g Since no idle time is introduced between rmax S e and Cj e Cj rmax S pS Moreover by and the ordering of the jobs we h a ve t h a t rmax S maxkjCk Cj and so e Cj Cj pS Finally b y applying Lemma we obtain our result Since this linear program can also be solved in polynomial time via the ellipsoid algorithm we have the following theorem P Theorem Scheduleby C j is a 􀀀approximation algorithm for jrj prec j wj Cj Moreover the optimal value of the linear program is guaranteed to be within a factor of three of the optimal schedule value P Corollary The linear program given by a n d is a 􀀀relaxation of jrj prec j wj Cj It is interesting to note that in the absence of precedence constraints the inequalities and still de ne the linear transformation of a supermodular polyhedron Consequently w e need not rely on the ellipsoid method but can instead apply the greedy algorithm for these polyhedra to obtain an optimum LP solution Hence this gives a combinatorial approximation algorithm for P jrj j wj Cj with running time On see Queyranne Schulz for the details Again these results have implications for other LP relaxations We obtain a timeindexed formulation for this model by simply changing constraints to xjt tr j pj PT Then if x satis es and then Cj txjt also satis es the releasedate tpj P constraints Consequently the timeindexed formulation is a relaxation of jrj prec j wj Cj In the absence of precedence constraints this formulation has been reported to be quite strong in practice However it has an exponential numb e r o f b o t h v ariables and constraints and so signi cant eort has been devoted to developing ecient computational techniques to compute its solution see for example Sousa Wolsey Van den Akker Van den Akker Hurkens Savelsbergh Speci cally V an den Akker reports that the heuristic Scheduleby Cj that uses Cj computed from the optimal solution to the timeindexed formulation is the best heuristic in P practice for jrj j wj Cj Therefore our analysis of Scheduleby Cj gives the rst evidence from a w orstcase perspective of the computational ecacy of this heuristic and the quality o f l o wer bounds provided by these formulations P Dyer Wolsey proposed a formulation for jrj j wjCj in completion time variables Cj and another kind of timeindexed variables yjt H ere yjt if job j is being processed in the time period tt and yjt otherwise The relaxation is as follows Xn minimize wj Cj j subject to nX yj t t T j TX yj t pj j n t pj pj TX t t yj t Cj j n yj t j n t rj T Notice that this linear programming problem is a transportation problem with a quite specially structured objective function the coe cient o f v ariable yjt is the product of wj pj and t As a consequence the following preemptive s c hedule is an optimal solution to this LP at any p o i n t i n time schedule among the available jobs the one with largest ratio wj pj Dyer Wolsey Goemans showed that this relaxation is equivalent to the following relaxation which s o l e l y uses completion time variables Xn minimize wj Cj j subject to X pjCj S for each SN jS where Srmin SpS pS pS The valid inequalities are a strengthened variant of see e g  Queyranne Schulz P This implies that the linear program and also is a relaxation of jrj j wjCj Since the polyhedron de ned by constraints is a linear transformation of a supermodular polyhedron Goemans we m a y apply the greedy algorithm for supermodular polyhedra to solve this particular relaxation In fact it delivers the same preemptive s c hedule Combining this with P algorithm Scheduleby C j w e obtain a combinatorial approximation algorithm for jrj j wjCj that runs in On log n time Subsequently W ang a showed that our analysis of the algorithm Scheduleby Cj is tight irrespective of the use of inequalities and or in the underlying LP relaxation Singlemachine scheduling with preemption P The third model we consider is jrj prec pmtnj wj Cj that is the scheduling model in which jobs have release dates and precedence constraints but the processing of a job may b e i n terrupted and continued at a later point i n t i m e Since the preemptive problem is a relaxation of the non preemptive problem and constraints and are all valid for the preemptive v ersion of the problem Theorem immediately yields a approximation algorithm for the preemptive problem In this section we give a approximation algorithm based on a strengthened linear programming relaxation P Consider an instance of jrj prec pmtnj wj Cj Notice that if jk and rj pj r k we can increase the value of rk to rj pj without causing any feasible schedules to become infeasible We begin by preprocessing the data in the instance in this manner so that for all jk with jk rk rj pj N e x t w e consider the linear programming formulation given by and which also is a valid relaxation for the preemptive problem Suppose we obtain an optimal linear programming solution to this system call it CCn W e construct a preemptive s c hedule from the LP solution as follows We consider the jobs one at a time in order of their Cj values notice that the ordering is consistent with the precedence constraints because of and thus by the time we consider job j all of its predecessors have already been scheduled To s c hedule job j we nd the rst point in time in the partially constructed schedule at which all of the predecessors of j have completed processing or time rj whichever is larger Subsequent to that point in time we s c hedule parts of j in any idle time in the partial schedule until j gets completely scheduled We call this algorithm PreemptivelyScheduleby Cj Lemma Let CCn be an optimal solution to the linear program dened b y ee and and let CCn denote the completion times in the schedule found by Preemptively e Scheduleby Cj Then for j nCj Cj e Proof Consider a job j whose completion time in the constructed schedule is Cj and consider the partial schedule constructed by the algorithm for jobs j Let t be de ned as the latest e point in time prior to Cj at which there is idle time in this partial schedule or if no idle time e exists before Cj set t Let S denote the set of jobs that are partially processed in the interval e tCj in the partial schedule First we observe that no job of S gets released before time t for if there were such a job then by the preprocessing of the data there would also be a job k minimal in S with respect to for which t h i s w ere true But then job k would have b e e n s c heduled during part of the idle time prior to t w h ich it w asnot Therefore trmin S and since there is no idle e time between t and Cj e Cj rmin S pS Now w e return to the strengthened inequalities Recall that the set S was de ned relative to the partial schedule obtained just after job j was scheduled thus for all k SCk Cj This fact combined with implies that X Cj pS pkCk rmin SpS pS kS e or Cj rmin S pS Thus Cj Cj a s w e wished to show Notice that the algorithm PreemptivelyScheduleby Cj creates a preemption only when a job is released Consequently the total number of preemptions is less than n Moreover the underlying linear program and can be solved in polynomial time The crucial observa tion needed is that there is a polynomialtime separation algorithm for the inequalities see Queyranne Schulz or Goemans Hence altogether we h a ve the following corollary Theorem P PreemptivelyScheduleby Cj is a 􀀀approximation algorithm for jrj prec pmtnj wjCj Due to our assumption about the integrality o f the data each preemption introduced by PreemptivelyScheduleby Cj will occur at an integer point in time Consequently i f w e apply PreemptivelyScheduleby Cj to an instance in which pj for each jn then there will n o t b e a n y preemptions introduced Since we h a ve obtained a nonpreemptive s c hedule that is within a factor of of the preemptive optimum we h a ve also obtained the following corollary Corollary P PreemptivelyScheduleby Cj is a 􀀀approximation algorithm for jrj prec p j j wjCj The proof of Theorem also has the corollary that the linear programming optimum is within a factor of two of the optimal preemptive s c hedule value When considering a preemptive model it is also interesting to consider the ratio between the nonpreemptive and preemptive optima that is to bound the power of preemption Phillips Stein Wein and Lai showed that P the optimum for jrj j wj Cj is at most a factor of more than its preemptive relaxation and Lai P showed that there exist instances of jrj j Cj for which the ratio is at least Since the inequalities and are all valid for preemptive s c hedules the proof of Theorem P implies that the optimum for jrj prec j wj Cj is always within a factor of of its preemptive relaxation however the technique of Phillips Stein Wein easily extends to yield a bound of for this case as well Conversely f o r a n y LP relaxation of the preemptive v ersion the ratio of the nonpreemptive optimum to the preemptive o p t i m um is also a lower bound on the ratio of the nonpreemptive o p t i m um to the LP optimum Applying this to our strongest LP relaxation we P can conclude that there are instances of jrj j Cj for which the optimum value is at least times the optimal value for the linear relaxation given by and More recently Queyranne P W ang provided a set of instances of jrj j wj Cj for which the ratio of the nonpreemptive optimum to the optimum of this LP is at least ee Since the optimal LP solution to their instances is always achieved by a preemptive s c hedule it also follows that there exist instances P of jrj j wj Cj for which the ratio between the nonpreemptive and preemptive optima is at least ee Chekuri Motwani Natarajan Stein prove a surprisingly strong result about converting preemptive s c hedules to nonpreemptive s c hedules Consider any preemptive s c hedule with completion times Cj jn and for any x e d let the point o f jo b jCj be the rstmomentintim eatwhichatotalof pj time units of processing have been completed on job j Chekuri et al show that if is selected at random in with density function ee then the expected completion time of job j in the schedule produced by Scheduleby Cj is at P e most Cj Hence for any instance of jrj j wj Cj there exists a nonpreemptive s c hedule of e objective function value within a factor of ee of the preemptive o p t i m um Identical parallel machines In this section we s h o w that our approach can be extended to the more general setting in which we have m identical parallel machines each job can be processed by a n y of the machines In a nonpreemptive s c hedule a job must be processed in an uninterrupted fashion by exactly one machine whereas in a preemptive s c hedule a job may b e i n terrupted on one machine and continued onanotheratalaterpoint in time at any p o in tin timeajob may be processed by a t m o st o n e machine The problem of minimizing the total weighted completion time on two identical parallel ma chines either preemptively or nonpreemptively w as established to be NP hard by Bruno Coman Sethi and Lenstra Rinnooy Kan Brucker We will again use variables Cj to denote the completion time of job j irrespective of the machine on which it is processed The convex hull of feasible completion time vectors has not been previously studied in this general set ting We can derive a class of valid inequalities for this model by generalizing the inequalities this observation was also made by Queyranne P Lemma Let CC n denote the job completion times in a feasible schedule for P jj wj Cj Then the Cj satisfy the inequalities X pjCj pS pS for each SN m jS Proof Without loss of generality assume that there is no unforced idle time in the schedule and that the jobs are indexed so that CCn Consider the schedule induced for the subset of jobs J f j g Job j is the last job to nish among jobs of J If job j is scheduled on machine i then i is the most heavily loaded machine with respect to jobs in J So the load on Pj machine i is at least pJ m and hence Cj pJm pk m But then k nj Xn XX pjCj mpj pk j jk and then the usual arithmetic simpli es the righthand side to yield in the case where S f n g The general case follows from the fact that the restriction of a schedule for the entire set of jobs to a subset can be interpreted as a schedule for this subset In fact Schulz a has also shown that the following slightly stronger class of inequalities is valid X pjCj pS pS for each SN m jS However our analyses of approximation algorithms will not require this strengthened class of inequalities We s h o w next that the inequalities imply a kind of load constraint this result is an immediate generalization of Lemma in the singlemachine setting Lemma Let CC n satisfy and assume without loss of generality that CCn Then for each jn if S f j g Cj pS m Proof Let S f j g from and the fact that Ck Cj for each kj we have jj XX Cj pS Cj pk pkCk pSpS pS mm kk from which w e obtain Cj pS m Note that inequalities and Lemma apply to both preemptive and nonpreemptive s c hed ules As in the singlemachine setting our approximation algorithms are based on solving a linear programming relaxation in the Cj variables and then scheduling the jobs in a natural order dictated by the solution to the linear program For several models simple variants of a listscheduling rule that are based on the LP solution yield excellent performance guarantees we present these algorithms and their analysis in Sections and For the most general version of this problem a somewhat more complex approach will be necessary we present this result in Section We note in advance that with every approximation algorithm we obtain a bound on the quality of the associated linear programming relaxation to avoid excess verbiage we omit explicit statements of these corollaries Independent jobs PP We begin by considering the problem P jrj j wj Cj as our linear program we minimize j wjCj subject to constraints and releasedate constraints which of course remain valid in the parallel machine setting Our algorithm StartJobsby Cj works as follows We rst compute an optimal solution CCn to this linear program we again assume without loss of generality that CCn W e s c hedule the jobs iteratively in the order of this list and for each j o b j we consider the current s c hedule after time rj and identify the earliest block o f pj consecutive idle time units on some machine in which t o s c hedule this job Lemma Let CCn be an optimal solution to the linear program dened b y ee and and let CCn denote the completion times in the schedule found by StartJobsby Cj For each jn e Cj Cj m Proof Consider the schedule induced by the jobs j and let S f j g A n y idle period on a machine in this partial schedule must end at the release date of some job in S Consequently all machines are busy between time rmax S and the start of job j T hus e Cj rmax S pS nf jg pj m rmax SpS pj mm To bound this expression we note that the constraints of the LP formulation ensure that Cj pj and since Cj Ck for kj th at Cj rmax S ByLemma we h ave Cj pS m e which yields an overall upper bound of Cj on Cj m To s o l v e the linear program in polynomial time we again use the greedy algorithm for rescaled supermodular polyhedra the feasibility of this approach follows from the fact that and also de ne the linear transformation of a supermodular polyhedron see Queyranne Schulz for the details Thus we h a ve the following theorem which w as also obtained by Queyranne P Theorem StartJobsby Cj is a 􀀀approximation algorithm for P jrj j wj Cj m The ideas used in this result are similar to those introduced by Phillips Stein Wein to convert preemptive parallel machine schedules to nonpreemptive s c hedules For the case in which there are no nontrivial release dates Kawaguchi Kyan have p shown that the following is a approximation algorithm order the jobs by nondecreasing ratio pj wj and apply the listscheduling algorithm of Graham In this special case our algorithm StartJobsby Cj is closely related to this algorithm assume that the jobs are indexed so that pw pn wn Suppose that we started by solving a somewhat weaker linear program P instead minimize j wj Cj subject to In other words we relax the constraint that Cj pj jn H o wever this is the same linear program as we w ould solve for a machine input in which jo b j requires pj m units of processing By the theorem of Queyranne and Wolsey the optimal solution to this linear program is Cj p S m where S f j g In other words our modi ed algorithm is exactly the algorithm of Kawaguchi Kyan Furthermore equation implies that e Cj pSm pj Cj Cj mm where Cj jn denotes the completion time of job j in some optimal schedule Hence we obtain a simple proof that the algorithm of Kawaguchi Kyan is a approximation m algorithm Furthermore this analysis implies the following bound on the strength of the linear relaxation used by StartJobsby Cj P Corollary The linear program a n d is a 􀀀relaxation of P jj wj Cj m Preemptive s c heduling and unittime jobs P We consider next the preemptive v ariant P jrj prec pmtnj wj Cj in w h ich w eareallowed to interrupt the processing of a job and continue it later possibly on another machine We will give a simple approximation algorithm for this problem Furthermore if all of the jobs are unitlength and the release dates are integral then the algorithm does not introduce any preemptions hence P this also yields a approximation algorithm for P jrj prec pj j wj Cj In his groundbreaking paper Graham showed that a simple listscheduling rule is a approximation algorithm for P jprecjCmax In this algorithm the jobs are ordered in some m list and whenever one of the m machines becomes idle the next available job on the list is started on that machine where a job is available if all of its predecessors have completed processing Graham actually showed that when this algorithm is used to schedule a set N of jobs the length Cmax of the resulting schedule is at most pN nC p C m where C denotes the set of jobs that form the longest chain with respect to processing times of precedenceconstrained jobs ending with the job that completes last in the schedule We shall analyze a preemptive v ariant of Grahams listscheduling rule The jobs are listed in order of nondecreasing Cj value where Cj jn denotes an optimal solution to the linear program and once again we shall assume that the jobs are indexed so that CC Cn A job j is available for processing in a schedule at time t if rj t and all predecessors of job j have completed by t i m e t A m a c hineis available at time t if it not assigned to be processing a job at that time The algorithm PreemptivelyListScheduleby C j constructs the schedule in time If machine i becomes available at time t then among all currently available jobs this machine is assigned to process the one that occurs earliest in the list If a job j becomes available at time t and there is a job currently being processed that occurs later on the list than j then among all jobs currently being processed job j preempts the one that occurs latest in the list P Theorem For P jrj prec pmtnj wj Cj PreemptivelyListScheduleby C j is a 􀀀approximation algorithm Proof The proof of this result is very similar in spirit to Grahams original analysis for ee P jprecjCmax Let CCn be the completion times of the scheduled jobs Let us focus on a e particular job j W e claim that the time interval from to Cj can be partitioned into two sets of intervals the total length of one of these sets can be bounded above b y Cj while the length of the other can be bounded above b y Cj e We construct the partition as follows Let tCj and jj W e rst derive a c hain of jobs js js j from the schedule in the following way Inductively f o r ks de ne tk as the time at which job jk becom es available if rjk tk th en set sk and the construction is complete Otherwise jk b e c o m e s a vailable due to the completion of one of its predecessors at time tk Let jk denote a predecessor of jk that completes at time tk Clearly w e h a ve that js js j le t C denote the set of jobs in this chain A simple inductive argument s h o ws that the constraints and imply that Cj rjs p C We can think of this lower bound as the total length of the union of the disjoint time intervals in which some job in this chain is e being processed together with the interval r js So to compute an upper bound on Cj w e need e only consider the complementary set of time intervals within Cj let T denote the set of times t b e t ween ts and t during which no job in C is being processed We wish toshow that T consists of disjoint intervals of time of total length at most Cj Consider any p o i n t in time t T in the interval tk t k ks at this point in time the job jk is available Since it is not being processed this implies that no machine is idle furthermore each job being processed must occur earlier in the list than jk and hence earlier in the list than j In other words for every t T e a c h m a c hine is processing some job in S f j gnC Hence the total length of T is at most pS nC m b y Lemma pSm Cj T hus e Cj tts tts ts p C pS nC mCj for each jn Noting once again that the linear program can be solved in polynomial time we h a ve established our theorem It is easy to bound the number of preemptions introduced by the algorithm PreemptivelyList Scheduleby Cj E a c h preemption can be associated with the moment in time at which a j o b r s t becomes available Since there is no preemption associated with the rst job scheduled there are at most n preemptions Furthermore our assumption about the integrality of the data implies that all preemptions occur at integer points in time This implies that if all jobs are of unit length then no preemptions occur and the schedule found is actually a nonpreemptive one in this case PreemptivelyListScheduleby C j is precisely the listscheduling algorithm of Graham P Corollary For P jrj prec p j j wj Cj PreemptivelyListScheduleby C j is a 􀀀approxima􀀀 tion algorithm If rj jn then we can slightly re ne the analysis of Theorem In this case we can partition the schedule into T and theperiodsoftim ein whichsomejobin C is being processed Hence e Cj pS nC mp C pSm p C m This implies that PreemptivelyListScheduleby C j is a approximation algorithm for both PP m P jprec pmtnj wj Cj and P jprec pj j wj Cj The general problem P We next consider P jrj prec j wj Cj in its full generality Unfortunately w e do not know h o w to prove a good performance guarantee for this model by using a simple listscheduling variant P However we are able to give a approximation algorithm for P jrj prec j wj Cj b y considering a somewhat more sophisticated algorithm Observe that if we use only one of our m machines and schedule the jobs in order of their LP optimal values then Lemma implies that this schedule has objective function value within a factor of m of the m machine optimum and within a factor of m if all release dates are Hence for m this dominates the more sophisticated approach P Our algorithm for P jrj prec j wjCj w h ich w ecall IntervalScheduleby Cj begins as before P by nding the optimal solution CCn to the linear program to minimize j wjCj subject to and as before we assume that C Cn Next we divide the time line into intervals L L where L is the smallest integer such that L is at least rmax N p N Note that rmax N p N is an upper bound on the length of any feasible schedule with no unforced idle time and that our preprocessing assumption about the data also implies that Cj for each jn F or conciseness let a n d L We use j to denote the index of the upper endpoint of the interval in which Cj lies i e  the smallest value of s u c h that Cj F urthermore let S denote the set of jobs j with j L We de ne t p S m t can be thought o f a s t h e a verage load on a machine for the set S F or each L w e set X k tk k We s c hedule the jobs in S using the listscheduling algorithm of Graham in the interval to Note that the order in which the jobs within each S are listed is completely arbitrary P Theorem IntervalScheduleby Cj is a 􀀀approximation algorithm for P jrj prec j wj Cj Proof We rst show that this is a feasible schedule The constraints ensure that the precedence constraints are enforced since for each j o b jS e a c h of its predecessors is assigned to Sk for some k fg We also need to showthattheschedule respects thereleasedate constraints If jS L th en rj Cj H o wever X k k and hence rj Hence the analysis of the listscheduling rule for each i n terval reduces to the case without release dates Grahams analysis implies that the length of the schedule constructed for S can be bounded by the maximum length of any precedence chain plus the average load on a machine The average load is exactly t The constraints ensure that the maximum length of a chain that ends with job j is at most Cj jn and so by the de nition of S the maximum length chain in S is at most Hence we h a ve allocated sucient time to complete this fragment of the schedule Nextwe sh owthateach job j completes by time at most Cj Consider the completion time e of job jS By the Grahamlike analysis discussed in the proof of Theorem Cj is bounded above b y t j where j is the length of some chain that ends with job j Combining PP P terms we can rewrite this bound as kk k tkj w hich is at m ost k tk Cj recall that j Cj Consider the job j S S whose Cj value is largest Lemma implies that X X tk m p Sk Cj k k Thus e Cj Cj Cj since Cj This completes the proof Since the inequalities and are all valid for the preemptive relaxation we h a ve a l s o shown that the ratio between the nonpreemptive o p t i m um and the preemptive optimum is at most In fact if we replace Cj by the completion time of job j in an optimal preemptive s c hedule then the proof of Theorem implies that this ratio is at most instead of inequality we k n o w that the total processing requirement of jobs nishing by in the optimal preemptive s c hedule is at most m Intervalindexed formulations and unrelated machines In this section we consider the problem of scheduling on unrelated parallel machines and give P a  approximation algorithm for Rjrj j j wj Cj In contrast to the results of the previous sections we do not use linear programming formulations in Cj variables but rather a formulation inspired by timeindexed linear programming formulations We shall introduce the notion of an interval􀀀indexed formulation in which the decision variables merely indicate in which timeinterval a given job completes The intervals are constructed by partitioning the time horizon at geometrically increasing points consequently unlike the timeindexed formulation this new formulation is of polynomial size Furthermore since the ratio between the endpoints of each i n terval is bounded by a constant we can assign a job to complete within this interval without too much concern about when within the interval it actually completes We will in fact consider a slightly more general problem in which the release date of a job may depend on the machine and is thus denoted rij job j may not be processed on m achine i until time rij imj n This model will also be relevant to our discussion of network scheduling models We will rst give an approximation algorithm that is somewhat simpler to explain We c a n divide the time horizon of potential completion times into the following intervals LL L where L is chosen to be the smallest integer such that maxij rij P L j maxi pij that is is a suciently large time horizon For conciseness let a n d L and so the th interval runs from time to L Consider the following linear programming relaxation in which the interpretation of each decision variable xij imj n and L is to indicate if job j is scheduled to complete on machine i within the interval mL Xn XX minimize wj xij ji subject to mL XX xij jn i Xn pijxij im L j xij if r ij pij xij imjn L P Lemma For Rjrij j wj Cj the optimal value of the linear program is a lower P bound on the optimal total weighted c ompletion time wj Cj Proof Consider an optimal schedule and set xij if job j is assigned to machine i and completes within the th interval This solution is clearly feasible constraints are satis ed since the total processing requirement o n m a c hine i of jobs that complete within i s a t most constraints are satis ed since any j o b j that completes by on machine i must have rij pij Finally if jo b j completes within the th interval L then its completion time is at least hence the objective function value of the feasible solution constructed is no P more than wjCj One unusual aspect of the formulation is that it is the linear relaxation of an integer program that is itself a relaxation of the original problem We believe that this idea might prove useful in other settings as well Our rounding technique is based on the observation that this linear program is essentially the same as the one considered by Shmoys Tardos for the generalized assignment problem We will apply their rounding technique both in this section and the next we therefore present a brief discussion of the generalized assignment problem and the main result of Shmoy s T ardos Shmoys Tardos consider the following linear program in the setting with m unrelated machines and n jobs where processing job j on machine i requires pij time units and incurs a cost cij fo r each i mj n and the costs need not be nonnegative the total cost incurred must be at most C and each machine im m ust complete its processing within Ti time units Xm Xn cij xij C ij Xm xij for jn i Xn pijxij Ti for im j xij imj n Theorem Shmoys Tardos There i s a p olynomial􀀀time algorithm that given a feasible solution x to the linear program r ounds this solution to an integer solution x such that xij xij and x satises constraints a n d Xn pijxij ti max pij for each im jxij j P n where ti pijxij Furthermore if we let Ji fjxij g im then each j P Ji Si Bi where j pij ti and jBij im Finally the analogous theorem holds S S i P if we replace c onstraints with mi xij im Observe that the properties of Si and Bi imply that equation holds the total processing requirement o f Si is bounded by ti and by thejob j in Bi must have xij Consider again the linear relaxation If we view a machineinterval pair as a virtual machine then this linear program is a further constrained variant of where are the only additional constraints Nonetheless any feasible solution to can be viewed as a feasible solution to and hence Theorem can be applied to round this solution P We can use this rounding theorem to devise an approximation algorithm for Rjrij j wj Cj We rst solve the linear program apply the rounding technique of Shmoys Tardos to this feasible solution x a n d i n terpret the rounded integer solution x as a schedule in the following way Consider the set of jobs Ji fjxij g im L and let P kk L W e shall process each j o b jJi on machine i entirely within the interval from to where the ordering of jobs within this interval is arbitrary First we shall show that this is feasible Clearly L If rij pij then xij and hence xij in other words for each j o b jJi rij rij pij im L Putting these two facts together we see that job j is released by time F urthermore if pij then xij and hence the total processing requirement of the jobs in Ji satis es X pij max pijjxijjJi and so these jobs can all be processed by m a c hine i entirely within the interval from to To analyze the quality o f t h i s s c hedule rst note that the objective function value of the rounded solution x is at most the objective f u n c t i o n v alue of the optimal LP solution x since by Theorem x satis es Observe that each jJi contributes wj to the objective function value of x whereas it completes by time in our schedule and hence contributes at most wj to the objective function value of the schedule found Since L the total weighted completion time of the schedule found is no more than times the objective v alue of the rounded solution x Hence we h a ve found a schedule with total weighted completion time within a factor of of optimal To g i v e an improved performance guarantee we note that the linear programming relaxation is quite weak in the following sense The load constraints limit the load on machine i for the th interval to If for example this constraint is satis ed with equality then for each of the previous intervals machine i can have no load whatsoever We can capture this by adding the following constraints XXn pijxijk im L kj P Lemma For Rjrij j wj Cj the optimal value of the linear program and i s a P lower bound on the optimal total weighted c ompletion time wj Cj We s h o w next that Theorem implies that an optimal solution to the strengthened linear relaxation can be rounded to yield a schedule better than the one found above As above any feasible solution to the linear program and can be viewed as a feasible solution to Let x denote the optimal solution to the strengthened linear relaxation and let ti PP n j pijxij im L th us k tik L The rounding theorem produces an integer solution x which can be interpreted as the job partition Ji im P L where each s e t Ji Bi Si satis es i j pij ti ii jBi j and iii for S S i each jo b jJi rij pij Consider some machine im W e construct the following schedule let X L ik tik k the jobs in Ji are scheduled in the interval from i to i sorted in the order of nondecreasing pj wj ratio We shall call this the Greedy LPinterval algorithm Observe t h a t i f w e c hanged by replacing tik with its upper bound k implied by then i is simply Lemma The schedule produced by the algorithm Greedy LPinterval is feasible Proof Consider some machine im w e m ust show that the release dates are respected and that each set of jobs Ji L t s i n to its assigned interval Since L we see that X ik k For each job jJi w e have that rij rij pij and hence job j has been released by time on machine i F urthermore we h a ve that i X pij ti ii jJi and so these jobs can all be processed entirely within this interval Lemma Consider the class of all schedules S in which every job jJi is scheduled o n machine i entirely within the interval from i to i for each im L A mong all schedules in S th e Greedy LPinterval algorithm produces a schedule of minimum total weighted completion time Proof The proof of Lemma implies that any s c hedule in S is feasible For any s c hedule in S view the completion time of each j o b jJi as i Cb j When optimizing among all schedules PP b in S the problem of minimizing j wjCj is equivalent to the problem of minimizing j wj Cj However in the former case it is clear that we h a ve mL independent sequencing problems and P each is e q u iv alent to an instance of jj wj Cj By the classical result of Smith each c a n b e solved by ordering the jobs in Ji in order of nondecreasing ratio pj wj H o wever this is exactly our algorithm Greedy LPinterval Given the rounded solution x let Cj whenever xij in other words Cj is the completion time that the rounded solution x is charged for job j in its objective function P Theorem For Rjrij j wj Cj Greedy LPinterval is a 􀀀approximation algorithm Proof We w i l l s h o w that the schedule produced by the Greedy LPinterval algorithm is good by analyzing two other ways to sequence the jobs within each i n terval and then showing that one of the two resulting schedules has total weighted completion time within a factor of of optimal By Lemma this implies the theorem The two s c hedules that we consider are as follows for each i n terval either always assign the job in Bi before the jobs in Si L or vice versa Observe that for any sequence of the jobs in Ji Bi Si in its interval each such j o b j completes by time XX X i tikk k Cj kk k This implies that the algorithm is a approximation algorithm but we will show something a bit stronger We rst consider the schedule in which e a c h B job is scheduled rst in its interval In that case the job jBi completes at time XX X i pij i k tik k k k k Cj On the other hand in the schedule in which j Si completes by time e a c h B job is scheduled last in its interval each j o b X X X X i pij i ti tikk k Cj jSi kk k PP PP m PLm PL Let wj Cj and wjCj By Theorem Bi jBi Si jSi BS P i s a l o wer bound on the optimal value j wj Cj The rst schedule has total weighted completion time at most SB and the second one has total weighted completion time at most SB Since minf S BS B g SBSB BS we see that one of these schedules has objective function value within a factor of of the optimum Since the schedule found by the algorithm is at least as good the theorem follows P Corollary The linear program is a 􀀀relaxation of Rjrij j wj Cj Deng Liu Long Xiao and Awerbuch Kutten Peleg independently intro duced the notion of network scheduling i n w h i c h parallel machines are connected by a network each job is located at one given machine at time and cannot be started on another machine until sucient time elapses to allow the job to be transmitted to its new machine it is assumed that an unlimited number of jobs can be transmitted over any n e t work link at the same time This model can be reduced to the problem of scheduling with machinedependent release dates if job j originates on machine k w e set rij to be the time that it takes to transmit a job on machine k to machine i We t h e r e b y obtain the following corollary Corollary There i s a 􀀀approximation algorithm to minimize the average weighted c om􀀀 pletion time of a set of jobs scheduled on a network of unrelated machines The best previously known algorithms due to Awerbuch Kutten Peleg and Phillips Stein Wein provided only polylogarithmic performance guarantees A general online framework In this section we describe a technique that yields an online approximation algorithm to min imize the weighted sum of completion time objective where depends on the scheduling environ ment the setting is online in the sense that we are constructing the schedule as time proceeds and do not know of the existence of job j until time rj If one views the role of the LP in Section as assigning the jobs to intervals this online result shows that if one does this assignment in a greedy fashion then one can still obtain a good performance guarantee The technique is quite general and depends only on the existence of an oline algorithm for the following problem The Maximum Scheduled Weight Problem Given a certain scheduling environment a dead line D a set of jobs available at time and a weight for each job construct a feasible schedule that maximizes the total weight of jobs completed by time D We require a dual 􀀀approximation algorithm for the maximum scheduled weight problem which produces a schedule of length at most 􀀀D and whose total weight is at least the optimal weight for the deadline D Dual approximation algorithms were rst shown to be useful in the design of traditional approximation algorithms by H o c hbaum Shmoys Our technique which is similar to one used by Blum Chalasani Coppersmith Pulleyblank Raghavan Sudan is useful in the design of online algorithms with performance guarantees that nearly match those obtained by the best oline approximation algorithms The required subroutine is a generalization of a subroutine used in the design of approximation algorithms to minimize the length of the schedule For several of the models considered in this paper the design of this more general subroutine is a straightforward extension of techniques devised for minimizing the length of the schedule although we do not yet see how to construct this subroutine for precedence constrained models In addition to the simplicity of the approach the performance guarantees PP can be quite good In fact for jrjj wj Cj and P jrj j wjCj respectively it leads to and approximation algorithms which asymptotically match the guarantees proved for these models in Section This result provides a means to convert o line scheduling algorithms into online algorithms A result of a similar avor was given for minimizing the length of a schedule by S h m o ys Wein Williamson but that result has the advantage that the subroutine required is simply the oline version of the same problem In that case an o line approximation algorithm yields an online approximation algorithm We rst describe our framework GreedyInterval and establish its performance guarantee We then briey discuss several applications The framework GreedyInterval is also based on partitioning the time horizon of possible comple tion times at geometrically increasing points Let a n d The algorithm constructs the schedule iteratively in iteration w e w ait until time and then focus on the set of jobs that have been released by this time but not yet scheduled which w e denote J W e in voke the dual approximation algorithm for the set of jobs J and the deadline D notice that in applying the o line dual approximation algorithm we assume that the jobs are available at time The schedule produced by the subroutine is then assigned to run from time to time e Let S denote the set of jobs scheduled during iteration Since it is clear that the schedule produced by this algorithm is feasible To analyze the performance guarantee of this algorithm consider a xed optimal schedule let L be de ned so that each job completes in this schedule by time L and let S denote the set of jobs that complete in the th interval L W e will argue that the total weight scheduled by GreedyInterval dominates the total weight s c heduled in the optimal schedule in the following sense for each L X X w eSk w Sk k k P where w S j S wj for each subset S f n g F ocus on a particular interval L and consider the set S of jobs that are completed within the rst intervals of the optimal schedule but are not scheduled within the rst iterations of the algorithm that is SSk k Since each job jS is completed by in the optimal schedule it is clearly released by k Se k and by de nition it has not been scheduled by GreedyInterval before Hence jJ and so SJ F urthermore S can be scheduled to complete by since all jobs in S are completed by in the optimal schedule Hence in iteration the dual approximation algorithm must return a set e S of total weight at least wS This implies the dominance property A further consequence ofthisproperty is th a t GreedyInterval has scheduled all of the jobs by iteration L PPL Since the sets SL specify an optimal schedule j wj Cj wS Note that we are using our assumption about the data that no job can complete before time The schedule produced by GreedyInterval has total weighted completion time at most LL XX wSe wSe PL PL e However the dominance property combined with the fact that wS wS PL implies this upper bound is at most wS Theorem Given a dual 􀀀approximation algorithm for the maximum scheduled w e i g h t p r oblem the framework GreedyInterval yields an on􀀀line 􀀀approximation algorithm to minimize the total weighted c ompletion time Next we consider how to apply this framework to speci c scheduling environments by describing the necessary dual approximation algorithms For a single machine and identical parallel machines we provide dual polynomial approximation schemes for the maximum scheduled weight problem for the unrelated parallel machine and network scheduling environments we generalize the algorithms of Shmoys Tardos and Phillips Stein Wein to provide dual approximation algorithms These lead to respectively online and approximation algorithms for these four scheduling problems where is xed but arbitrarily small P We rst consider applying GreedyInterval to the problem jrj j wj Cj In this context the max imum scheduled weight problem is as follows given a deadline D and a set of jobs N nd a subset of jobs S with pS D so as to maximize wS This problem is simply the knapsack problem where the size of the knapsack i s D the size of an object j i e  job j is pj and the value of that object is wj the weight of the associated job We shall argue that it is straightforward to adapt the fully polynomial approximation scheme of Ibarra Kim to yield a dual approximation scheme for this problem Given and a set of n jobs we round down the processing time of each job to the nearest multiple of Dn More precisely w e s e t D bD c pj bpj c and wj wj jn Next we apply a standard dynamic programming algorithm to this rescaled and rounded instance of the knapsack problem this algorithm runs in OnD On time Let S denote the optimal solution for the modi ed instance that is found by this algorithm and let S denote an optimal solution for the unrounded instance We h a ve t h a t pS pSD since each" pj is integer this implies that pS D that is S is a feasible solution for the modi ed data Since S is an optimal solution for the modi ed data wS wS On the other hand X pS pj pSn Dn DD D jS This shows that the proposed algorithm is a dual approximation algorithm Theorem There i s a d u a l 􀀀approximation algorithm for the maximum scheduled weight problem in the single􀀀machine scheduling environment P Corollary For jrjj wj Cj GreedyInterval yields an on􀀀line 􀀀approximation algorithm In fact we can improve on this result by slightly modifying the framework in this setting e GreedyInterval merely requires that the jobs in S b e s c heduled in the interval without specifying the order in which they should be scheduled Furthermore any ordering of the jobs within this interval produces a feasible schedule Hence it is most natural to sequence the jobs in order of nondecreasing pj wj ratio We shall show that this heuristic allows us to prove a stronger performance guarantee Consider the completion time of some job in Se I n w e use the fact that the completion time of this job is at most the upper endpoint of the interval in which these jobs are scheduled Instead let this completion time Cj be view edas j that is set j equal to Cj T hus PPL P n e we canshow that j wjCj is at most the sum of wS and j wjj The rst term is P n exactly half of the upper bound used in and hence is at most j wj Cj H o wever since e the algorithm is now sequencing the jobs in S optimally w e know that XX wjj wj Cj jSe jSe where Cj still denotes the completion time of job j in some optimal schedule of the entire instance P PP nn of the problem jrjj wj Cj Hence j wjj j wj Cj and so the performance guarantee is F rom Theorem we obtain the following corollary P Corollary For jrjj wj Cj GreedyInterval yields an on􀀀line 􀀀approximation algorithm The identical parallel machines environment requires a much m o r e i n volved algorithm that is basically a modi cation of the polynomial approximation scheme of Hochbaum and Shmoys for scheduling identical parallel machines to minimize the makespan We assume that we are given a set of n jobs with processing times and weights a deadline D a n d Our goal is to determine a subset of jobs and an associated schedule that can be scheduled on m machines to complete by time D whose total weight i s superoptimal that is at least as large as that of any subset of jobs that can be scheduled to complete by t i m e D Without loss of generality w e assume that all processing times are at most D since otherwise they cannot be part of such a s c hedule In order to simplify the exposition we shall merely show that for any x e d there exists such a polynomialtime algorithm we shall briey mention techniques for improving the running time at the end First we i n troduce two positive parameters and whose values will be speci ed later We partition the set of jobs into two sets a job j is short if pj and is long otherwise For each long job j w e round down its processing time to the nearest multiple of Notice that there are fewer than D distinct processingtime values for long jobs after rounding let us assume that there are K distinct values ppK Next we i n troduce the notion of a machine pattern that describes a possible assignment o f long job sizes to one machine A machine pattern is speci ed by the number of long jobs of each processing size such a pattern can be denoted with a K tuple nn K We assume that the sum of the rounded processing times in any m a c hine pattern is at most D and it could be much smaller than D for example the empty pattern is allowed Our strategy will be to focus on choosing a set of m machine patterns one for each m a c hine and given those patterns generating a schedule with length slightly larger than D whose weight is at least as good as any s c hedule conforming to that choice of patterns Then by trying every possible combination of patterns we will be guaranteed to nd a schedule whose weight i s s u p e r optimal and whose length is only slightly more than D By setting and judiciously w e will be able to ensure that there is at most a polynomial number of pattern combinations to try while simultaneously ensuring that upon inserting the original processing times for the rounded times we can still achieve a s c hedule length of D We will call a choice of m patterns feasible if there exists a sucient n umber of long jobs of each t ype to actually ll out the patterns Lemma Given a feasible choice o f p atterns there i s a n On log n 􀀀time algorithm to construct a s c h e dule whose length with respect to the rounded p r ocessing times is at most D such that the sum of the weights of all jobs in the schedule is as large as in any schedule of length at most D that conforms to the choice o f p atterns Proof Let us assume that the m chosen patterns together require Nk jobs of type k fo r k K F or each k w e order the jobs of that type according to nonincreasing wj and we select PK the rst Nk jobs on the list to be in the schedule Next let T mD the total k Nkpk amount o f m a c hine time left for scheduling the short jobs Let us assume that the set of short jobs is fjj n􀀀 g ordered so that wpwp wn pn􀀀 Consider the index s for which 􀀀 sXXs pj Tpj jj P 􀀀 n or let sn if pj T Consider the partial schedule given by the selected long jobs scheduled j according to the machine patterns We will augment t h i s s c hedule with the short jobs jj s in such a w ay that all of these short jobs get scheduled and the overall length of the new schedule with respect to the rounded processing times is at most D This can be done as follows assign these s shortjobs in order and foreach such job j merely identify some machine i which is currently processing jobs of total rounded length less than D and schedule job j on machine i b y a n a veraging argument the de nition of T and s ensures that there must always exist such a m achine i Consequently the total processing load assigned to each m a c hine i exceeds D by less than the maximum length of any short job We claim that the resulting schedule has total weight at least as large as any s c hedule for the original problem that conforms to the machine patterns of length at most D First among all long jobs we h a ve clearly chosen a set that maximizes the weight of the selected machine patterns Moreover T is an upper bound on the total amount of processing time available for scheduling short jobs in any s c hedule conforming to the chosen machine patterns since we h a ve c hosen the short jobs greedily and have either scheduled all of them or a set of them that has processing time at least T their total weight m ust equal or exceed the weight of the short jobs in any s c hedule with the properties described Thus the weight of the constructed schedule is superoptimal relative t o the chosen set of machine patterns The running time of the algorithm is clearly linear once the jobs of every rounded size have been sorted Itremainstoshow that w e can choose and inaway thatany such schedule whenthe processing times are unrounded has length at most D while simultaneously ensuring that the number of possible combinations of m machine patterns is at most polynomial in the size of the input The number of possible long jobs that could t on one machine in a schedule of length D is bounded above b y bD c and the total number of job sizes is bounded by bD c t h us an upper bound on the number of distinct machine patterns is MD D To bound thenumber of ways of selecting a combination of these patterns for m machines note that each pattern describes at most m machines therefore the total number of pattern combinations is bounded above b y mM In fact complete enumeration is not necessary and the algorithm can be made much more ecient by employing a simple dynamic programming approach In a greedily constructed schedule based on machine patterns the length of any s c hedule is bounded by DD where the last term reects the increase caused by the unrounding of at most D long jobs we wish to restrict this to depending doubly exponentially on and so there are at most a polynomial numb e r m of be at most D D V alues of and that achieve this bound while making M suciently small are D a n d D We observe that these values imply that M is a constant albeit M distinct pattern combinations to try Since a schedule corresponding to a pattern can be computed in On log n time we h a ve obtained the following theorem Theorem There i s a d u a l 􀀀approximation algorithm for the maximum scheduled weight problem in the identical parallel machine scheduling environment P Corollary For P jrj j wj Cj GreedyInterval yields an on􀀀line 􀀀approximation algorithm We next turn to the case in which w e h a ve a network of unrelated parallel machines each job j originates on some machine k a n d m a y be transferred to some other machine i through the network we let rij denote the earliest time at which j o b j can begin processing on machine i which is the sum of its release date and the time required to transfer the job to machine i The machines themselves are unrelated each j o b j requires pij time units of processing when scheduled on machine ii m Phillips Stein Wein gave an o line approximation algorithm for minimizing the schedule length in a network of unrelated machines we w i l l s h o w h o w to adapt this result to obtain the required subroutine for GreedyInterval for this scheduling environment Consider the maximum scheduled weight problem in this environment we are given a set of jobs N and a deadline D for each jN and each machine im w e are also given pij and rij t h e m a c hinedependent processing and allowed starting times respectively Consider the following linear program Xm Xn maximize wj xij ij subject to Xm xij jN i X pijxij D im jN xij if D r ij pij xij i mjN This linear program is a relaxation of the maximum scheduled weight problem if we consider the optimal schedule for the latter problem and set xij whenever job j is scheduled by time D on machine i th en x is a feasible integer solution for the linear program We will derive a dual approximation algorithm by applying Theorem to round the optimal solution to this linear program Let x denote the optimal solution to the linear program If we set cij wj fo r PP m each i mjN and C then x is a feasible solution to the linear i jN wj xij relaxation of the generalized assignment problem As a result we can invoke Theorem and round x to obtain an integer solution x By this theorem we k n o w that mm XX XX wj xij wj xij ijN ijN ee that is if we let S denote the set of jobs j forwhich som e com ponent" xij then wS is at least the LP optimum and is consequently at least the optimal value for the maximum scheduled weight problem e We will show that the set of jobs S can be scheduled by t i m e D and hence derive a dual e approximation algorithm By Theorem the set S can be partitioned into Bi Si im For each jo b jBi Si xij w henever rij pij D and so by xij implies that rij pij D This implies that the job j in Bi if it exists can be scheduled on machine i from P time Dpij to time D F urthermore we k n o w that jSi pij D and hence all of the jobs in Si c a n b e s c heduled on machine i from time D to D Theorem For scheduling on a network of unrelated p arallel machines there i s a dual approximation algorithm for the maximum scheduled weight problem P Corollary For minimizing wj Cj in a network of unrelated p arallel machines GreedyInterval yields an on􀀀line 􀀀approximation algorithm If each job can be transferred between machines without delay then we h a ve reduced the problem to ordinary unrelated machines and so we obtain the following corollary P Corollary For Rjrj j wj Cj GreedyInterval yields an on􀀀line 􀀀approximation algorithm Acknowledgments We are grateful to Cor Hurkens Cindy Phillips Maurice Queyranne Ar avind Srinivasan Cli Stein and Marjan Van den Akker for helpful discussions and to the anony mous referees for their very detailed comments Preliminary presentations of parts of this research were given in the conference papers of Hall Shmoys Wein and Schulz b The re search of the rst author was partially supported by NSF Research Initiation Award DMI  The research of the second author was partially supported by the graduate school Algorithmische Diskrete Mathematik grant W e The research of the third author was partially supported by NSF grants CCR DMS and ONR grant N O The research o f the fourth author was partially supported by NSF Research Initiation Award CCR  and a g r a n t from the New York State Science and Technology Foundation through its Center for Advanced Technology in Telecommunications References Awerbuch B  S Kutten D Peleg Competitive distributed job scheduling Proceedings of the th Annual ACM Symposium on the Theory of Computing Balas E On the facial structure of scheduling polyhedra Math Programming Stud Blum A  P Chalasani D Coppersmith B Pulleyblank P Raghavan M Sudan The minimum latency problem Proceedings of the th Annual ACM Symposium on the Theory of Computing Bruno J L  E G Coman Jr  R Sethi Scheduling independent tasks to reduce mean nishing time Comm ACM Chakrabarti S  S Muthukrishnan Job scheduling for practical parallel database and scienti c applications Proceedings of the th Annual ACM Symposium on Parallel Algorithms and Architectures Chakrabarti S  C Phillips A S Schulz D B Shmoys C Stein J Wein Improved scheduling algorithms for minsum criteria F Meyer auf der Heide B Monien eds  Automata Languages and Programming Proceedings of the  rd International Colloquium ICALP Lec􀀀 ture Notes in Computer Science Springer Berlin Chekuri C  R Motwani B Natarajan C Stein Approximation techniques for average completion time scheduling Proceedings of the th Annual ACM􀀀SIAM Symposium on Discrete Algorithms Chudak F  D B Shmoys Approximation algorithms for precedenceconstrained scheduling problems on parallel machines that run at dierent speeds Proceedings of the th Annual ACM􀀀 SIAM Symposium on Discrete Algorithms Deng X  H Liu J Long B Xiao Deterministic load balancing in computer networks Proceedings of the nd Annual IEEE Symposium on Parallel and Distributed P r ocessing Dyer M E L A Wolsey Formulating the single machine sequencing problem with release dates as a mixed integer program Discrete Appl Math Even G  J Naor S Rao B Schieber Divideandconquer approximation algorithms via spreading metrics Proceedings of the th Annual IEEE Symposium on Foundations of Computer Science Goemans M X A supermodular relaxation for scheduling with release dates W H Cunningham S T McCormick M Queyranne eds  Integer Programming and Combinatorial Optimization Proceedings of the th International IPCO Conference Lecture Notes in Computer Science Springer Berlin Goemans M X Improved approximation algorithms for scheduling with release dates Proceedings of the th Annual ACM􀀀SIAM Symposium on Discrete Algorithms Graham R L Bounds for certain multiprocessing anomalies Bell System Tech J Graham R L E L Lawler J K Lenstra A H G Rinnooy Kan Optimization and approximation in deterministic sequencing and scheduling a survey Ann Discrete Math Hall L A  D B Shmoys J Wein Scheduling to minimize average completion time o line and online algorithms Proceedings of the th Annual ACM􀀀SIAM Symposium on Discrete Algorithms Hochbaum D S D B Shmoys Using dual approximation algorithms for scheduling problems practical and theoretical results J Assn Comput Mach Ibarra O H C E Kim Fast approximation algorithms for the knapsack and sum of subset problems J Assn Comput Mach Kawaguchi T S Kyan Worst case bound of an LRF schedule for the mean weighted owtime problem SIAM J Comput Kellerer H  T Tautenhahn G J Woeginger Approximability and nonapproximability results for minimizing total ow time on a single machine Proceedings of the  th Annual ACM Symposium on the Theory of Computing Lai TC Earliest completion time and shortest remaining processing time sequencing rules Preprint College of Management National Taiwan University Lenstra J K  A H G Rinnooy Kan P Brucker Complexity of machine scheduling problems Ann Discrete Math Lenstra J K  D B Shmoys E Tardos Approximation algorithms for scheduling unrelated parallel machines Math Programming Lin J H  J S Vitter approximation with minimum packing constraint violation Pro􀀀 ceedings of the th Annual ACM Symposium on the Theory of Computing Margot F  M Queyranne Personal communication Mohring R H M W Schater A S Schulz Scheduling jobs with communication de lays Using infeasible solutions for approximation J Diaz M Serna eds  Algorithms ESA  Proceedings of the Fourth Annual European Symposium on Algorithms Lecture Notes in Computer Science Springer Berlin Munier A J C Konig A heuristic for a scheduling problem with communication delays Internal Report LRI Universite d e P arissud Orsay F rance Phillips C  C Stein J Wein Task scheduling in networks E M Schmidt S Skyum eds  Algorithm Theo r y S W AT P r oceedings of the th Scandinavian Workshop on Algorithm Theory Lecture Notes in Computer Science Springer Berlin Phillips C  C Stein J Wein Scheduling jobs that arrive o ver time S G Akl F Dehne J R Sack N Santoro eds  Algorithms and Data Structures Proceedings of the th International Workshop WADS Lecture Notes in Computer Science Springer Berlin Potts C N An algorithm for the single machine sequencing problem with precedence constraints Math Programming Stud Queyranne M Structure of a simple scheduling polyhedron Math Programming Queyranne M Personal communication Queyranne M  A S Schulz Polyhedral approaches to machine scheduling Preprint N o Department of Mathematics Technical University of Berlin Berlin Germany Queyranne M  A S Schulz Scheduling unit jobs with compatible release dates on parallel machines with nonstationary speeds Balas E  J Clausen eds  Integer Programming and Com􀀀 binatorial Optimization Proceedings of the th International IPCO Conference Lecture Notes in Computer Science Springer Berlin Queyranne M  Y Wang Singlemachine scheduling polyhedra with precedence constraints Math Oper Res Queyranne M  Y Wang Personal communication Ravi R A Agrawal P Klein Ordering problems approximated singleprocesssor schedul ing and interval graph completion J Leach Albert B Monien M Rodriguez Artalejo eds  Au􀀀 tomata Languages and Programming Proceedings of the th International Colloquium ICALP Lecture Notes in Computer Science Springer Berlin Schulz A S a Scheduling and Polytopes PhD thesis Technical University of Berlin Berlin Germany Schulz A S b Scheduling to minimize total weighted completion time performance guar antees of LP based heuristics and lower bounds W H Cunningham S T McCormick M Queyranne eds  Integer Programming and Combinatorial Optimization Proceedings of the th International IPCO Conference Lecture Notes in Computer Science Springer Berlin Schulz A S  M Skutella Randomization strikes in LP􀀀based scheduling Improved ap􀀀 proximations for min􀀀sum criteria Preprint Department of Mathematics Technical University of Berlin Berlin Germany Shmoys D B E Tardos An approximation algorithm for the generalized assignment problem Math Programming Shmoys D B J Wein D P Williamson Scheduling parallel machines online SIAM J Comput Smith W Various optimizers for singlestage production Naval Res Logist Quart Sousa J P L A Wolsey A timeindexed formulation of nonpreemptive singlemachine scheduling problems Math Programming Trick M Scheduling multiple variable speed machines Operations Research Van den Akker J M LP􀀀based solution methods for single􀀀machine scheduling problems PhD thesis Eindhoven University o f T echnology Eindhoven The Netherlands Van den Akker J M  C A J Hurkens M W P S a velsbergh A time􀀀indexed formulation for single􀀀machine scheduling problems branch and cut Preprint Wang Y a On the 􀀀approximation of scheduling with release dates Technical Report Max Planck Institut fur Informatik Saarbrucken Germany Wang Y b Bicriteria job scheduling with release dates Technical Report Max Planck Institut fur Informatik Saarbrucken Germany Wolsey L A Mixed i n t e ger programming formulations for production planning and schedul􀀀 ing problems Invited talk at the th International Symposium on Mathematical Programming MIT Cambridge Wolsey L A Formulating single machine scheduling problems with precedence constraints J J Gabsewicz J F Richard L A Wolsey eds  Economic Decision Making Games Economet􀀀 rics and Optimisation Contributions in Honour of Jacques Dreze NorthHolland Amsterdam