no-wait4

no-wait4, szeregowanie zadań

[ Pobierz całość w formacie PDF ]
//-->Makespan Minimization in No-Wait Flow Shops: aPolynomial Time Approximation Scheme∗M. Sviridenko†AbstractWe investigate the approximability of no-wait permutation flow shop schedulingproblem under the makespan criterion. We present a polynomial time approxima-tion scheme (PTAS) for problem on anyfixednumber of machines.1IntroductionProblem statement.Ajob shopis a multi-stage production process with the propertythat all jobs have to pass through several stages. There arenjobsJj, withj= 1,. . . , n,where each jobJjis a chain ofmjoperationsO1j, . . . , Omjj. Every operationOijispreassigned to one ofmstagesM1, . . . , Mmof the production process. The operationOijhas to be processed forpijtime units at its stage; the valuepijis called itsprocessingtimeor itslength.We will consider a basic model where there is exactly one machineavailable for each stage; to simplify the presentation we will identify the stage with thecorresponding machine. In a feasible schedule for thenjobs, at any moment in time everyjob is processed by at most one machine and every machine executes at most one job. Foreach jobJj, operationOi−1,jalways is processed before operationOij, and each operationis processed without interruption on the machine to which it was assigned. Aflow shopis a special case of the job shop where each job has exactly one operation in each stage,and where all jobs pass through the stages in the same orderM1→M2→ · · · →Mm. Inanopen shopthe ordering of the operations in a job is not fixed and may be chosen bythe scheduler.In this paper, we are mainly interested in shop problems under theno-wait constraint.In such a no-wait shop, there is no waiting time allowed between the execution of con-secutive operations of the same job. Once a job has been started, it has to be processedJoint preliminary version of this paper appeared in proceedings of FOCS00 [23] and contained someadditional nonapproximability results for no-wait shop scheduling problems.†IBM T. J. Watson Research Center, Yorktown Heights, P.O. Box 218, NY 10598, USA; Email:sviri@us.ibm.com∗1without interruption, operation by operation, until it is completed. In a no-wait flowshop instance without operations of length zero, any feasible schedule is apermutationschedule,i.e., a schedule in which each machine processes the jobs in the same order.In theno-wait permutation flow shopproblem, only permutation schedules are feasibleschedules. Our goal is to find a feasible schedule that minimizes themakespan(orlength)Cmaxof the schedule, i.e., the maximum completion time among all jobs. The minimum∗makespan among all feasible schedules is denoted byCmax.Complexity of shop problems.The computational complexity of the classical shopproblems (without the no-wait constraint) is easy to summarize: They are polynomiallysolvable on two machines, and they areN P-hardon three and more machines; see e.g.Lawler, Lenstra, Rinnooy Kan & Shmoys [11]. For no-wait shops, the situation is moreinteresting. Sahni & Cho [19] proved that the no-wait job shop and the no-wait open shopproblem are stronglyN P-hard,even if there are only two stages and if each job consistsof only two operations. The no-wait permutation flow shop problem can be formulatedas an asymmetric traveling salesman problem (ATSP); see e.g. Piehler [15], Wismer [25].For two machines, the distance matrix of this ATSP has a very special combinatorialstructure, and the famous subtour patching technique of Gilmore & Gomory [5] yields anO(nlogn)time algorithm for the two-machine no-wait flow shop. R¨ck [17] proves thatothe three-machine no-wait flow shop is stronglyN P-hard,refining the previous complex-ity result by Papadimitriou & Kanellakis [12] for four machines. Hall & Sriskandarajah[8] provide a thorough survey of complexity and algorithms for no-wait scheduling.Approximability of shop problems.We say that an approximation algorithmhasperformance ratioorworst case ratioρfor some realρ >1, if it always delivers∗a solution with makespan at mostρCmax. Such an approximation algorithm is thencalled aρ-approximationalgorithm. A family of polynomial time (1 +ε)-approximationalgorithms over allε >0 is called apolynomial time approximation scheme(PTAS).The approximability of the the classical shop problems (without the no-wait con-straint) is fairly well understood: If the number of machines is a fixed value that is notpart of the input, then the flow shop (Hall [7]), the open shop (Sevastianov & Woeginger[20]), and the job shop (Jansen, Solis-Oba & Sviridenko [9]) possess a PTAS. On theother hand, if the number of machines is part of the input, then none of the three shopproblems has a PTAS unlessP=N P(Williamson & al. [24]).Prior to our work, only a few results were known on the approximability of the no-waitshop problems: For all shop problems onmmachines, sequencing the jobs in arbitraryorder yields a (trivial) polynomial timem-approximationalgorithm. R¨ck & Schmidto[18] improve on this for the no-wait flow shop and give an⌈m/2⌉-approximationalgo-rithm. Papadimitriou & Kanellakis [12], Glass, Gupta & Potts [6], and Sidney, Potts &Sriskandarajah [21] study various generalizations and modifications of the no-wait flow-shop problem on two machines. For all these generalizations the authors manage to designapproximation algorithms with performance guarantees strictly better than two, by build-2ing on the algorithm of Gilmore & Gomory [5]. Agnetis [1] introduces an approximationalgorithm for the no-wait flow shop with only a small number ofdistinctjob-types; asthe number of jobs in every job-type grows, the performance guarantee of this algorithmtends to one. Sidney & Sriskandarajah [22] obtain a 3/2-approximation algorithm forthe two-machine no-wait open shop problem. The preliminary joint version of this paper[23] contains few non-approximability results due to G. Woeginger. He proved that theno-wait job shop problem on three machines with at most three operations per job andthe no-wait job shop problem on two machines with at most five operations per job doesnot have a PTAS unlessP=N P.Results and organization of this paper.We design a PTAS for the no-waitpermutation flow shop problem when the numbermof machines is fixed. This result firstuses several job partition and rounding steps, and then exploits the connection of the no-wait flow shop to the asymmetric traveling salesman problem. In Section 2 we recall anddiscuss this connection between no-wait flow shop and the ATSP. In Section 3 we derivethe PTAS. Some of our rounding and job partition steps seem to be very close to therounding and job partition steps in the PTAS’s for the classical shop problems [7, 9, 20]but our technique cannot be generalized to the no-wait job shop problem because of thenegative result due to G. Woeginger [23]. The paper concludes with the statement ofseveral open problems in Section 4.2The no-wait permutation flow shop and the ATSPIt is well known (see e.g. Piehler [15] or Wismer [25]) that the no-wait permutation flowshop problem can be modeled as a special case of the asymmetric traveling salesman prob-lem (ATSP) with the triangle inequality: We add adummyjobJwith zero processingtimes on all machines to a given flow shop instance. ByGwe denote the complete, arc-weighted, directed graph with vertex set{J, J1, . . . , Jn}and with the following weights(ordistancesorlengths)dqjon the arc from jobJqtoJj. We stress the fact that ingeneraldqj=djq.immmmdqj=i=1,...,mmax{k=1pkq+k=ipkj} −k=1piq= max{i=1,...,mk=ipkj−k=i+1pkq}.(1)The intuition behind the definition of the distances in (1) is the following. Assume thatin some schedule jobJqcompletes at timet,and that jobJqis followed by jobJj, withoutunnecessary idle time between the two jobs. ThenJjcompletes at timet+dqj. Withthis it is easy to see that every feasible permutation schedule of the no-wait flow shopproblem corresponds to a directed Hamiltonian cycleCin the digraphG,such that themakespan of the schedule equals the length ofC.Conversely, if we delete the in-going arcof vertexJfrom some Hamiltonian cycleCinG,then the resulting Hamiltonian pathcorresponds to a feasible permutation schedule with the same length.3The following observations on the distancesdqjare straightforward to verify.Observation 2.1For every jobJj, denote byℓj=(i) For all≤j, q≤n, ℓj−ℓq≤dqj≤ℓjholds.(ii) For all≤j, k, q≤n, dqj≤dqk+dkj, i.e., the distancesdqjfulfill the triangleinequality.(iii) If one of the valuespijchanges topij+ ∆,then the length of any ATSP tour (andthe makespan of the corresponding feasible schedule) changes by at most±∆.Because of this correspondence between permutation schedules and ATSP tours, theresult by Frieze, Galbiati & Maffioli [4] on the ATSP with triangle inequality yieldsanO(log n)-approximationalgorithm for the no-wait permutation flow shop problem.Recently, Carr & Vempala [2] gave some theoretical evidence for the existence of a 4/3-approximation algorithm for the ATSP with triangle inequality. Of course, such a resultwould immediately yield a 4/3-approximation algorithm for the no-wait permutationflow shop on an arbitrary number of machines. We remark that the strongest knownnegative result for the general ATSP with the triangle inequality is due to Papadimitriou& Vempala [14]. They prove that unlessP=N P,the ATSP with triangle inequalitycannot have a polynomial time approximation algorithm with performance guaranteebetter than 41/40. However, this negative result does not seem to carry over to theno-wait flow shop.mk=1pkjits overall length.3Approximability of the no-wait flow shopThroughout this section we consider an instanceIof the no-wait permutation flow shopproblem where the numbermof machines is a fixed constant and not part of the input. Byℓj=mpijwe denote the total length of jobJj. LetLi=npijbe the load of machinei=1j=1∗Mi, and letLmax= maxiLibe the maximum machine load. Clearly,Lmax≤Cmax.Letε >0 be a fixed precision parameter. Our goal is to find a near optimal schedule∗for instanceIwhose makespan is at most (1 +const·ε)Cmaxfor some fixed positiveconstantconstthat only depends onm.Clearly, this will yield the PTAS. We will uselogxto denote the logarithm base 1 +εofx.Byαwe denote a rational number withεm/ε≤α≤εwhose exact value will be fixed below. From now on we will assume thatthe numbernof jobs is sufficiently large to satisfy(21/m−1) logn≥1 + log(m/ε)andαn≥logmn.(3)(2)4Ifndoes not fulfill (2) and (3), then it is bounded by a constant inmandε;suchan instance of constant size can be solved in constant time by global enumeration. Wepartition the set of jobs into three subsets as follows.B={Jj|αLmax/logmn≤ℓj},M={Jj|ε·αLmax/logmn < ℓj< αLmax/logmn},S={Jj|ℓj≤ε·αLmax/logmn}.The jobs inBare calledbig jobs,the jobs inMare calledmedium jobs,and the jobs inSare calledsmall jobs.For the operations of big, medium, and small jobs we use a similarnotation: the operations of big jobs are calledbig operations,while operations of mediumand small jobs are calledmediumandsmall operations,respectively, independently oftheir actual sizes. Sincenℓj≤mLmax, the number of big jobs is upper bounded asj=1|B| ≤mlogmn≤ε−m/εmlogmn.α(4)Sevastianov & Woeginger [20] show that the valueαcan be chosen so thatℓj≤εLmax.Jj∈M(5)This is done as follows. Consider the setsM(k)of medium jobs with respect toα=εk,wherekis some positive integer. Note that fork=k′the two setsM(k)andM(k′) aredisjoint. Since the total length of all jobs is at mostmLmax, there exists a valuek∗≤m/εfor whichM=M(k∗) satisfies the inequality (5). We setα=εk∗. Finally, we define.β=m2logmn /(εα)(6)Starting from the flow shop instanceI=I(0), we will now define a sequence of instancesI(1),I(2),I(3),I(4). The instanceI(x+1)always is a rounded and slightly simplified version(x)of instanceI(x). In instanceI(x), the processing times arepij, the optimal makespan(x)isCmax, the digraph for the underlying ATSP isG(x), and so on. In order to get anear optimal schedule for instanceI(x), it will always be sufficient to get a near optimalschedule for the simplified instanceI(x+1). Hence, by constructing a PTAS forI(4)wewill establish the existence of the desired PTAS for the no-wait permutation flow shopon a fixed number of machines.3.1How to round the instanceIn the first rounding step, we remove all medium jobs fromIand thus produce instanceAPI(1). If we have a near optimal schedule with makespanCmaxXfor the big and small jobsin instanceI(1), then we may append the medium jobs in arbitrary order at the end of5 [ Pobierz całość w formacie PDF ]

zanotowane.pl

doc.pisz.pl

pdf.pisz.pl

anio102.xlx.pl