251 pág.

# Pinedo_problemas_deterministicos

Pré-visualização50 páginas

necessarily yield an optimal schedule. 5.26. Consider Pm | intree, prmp | Cmax with the processing time of each job at level k equal to pk. Show that a preemptive version of the generalized CP rule minimizes the makespan. 5.27. Consider Q\u221e | prec, prmp | Cmax. There are an unlimited number of machines that operate at the same speed. There is one machine that is faster. Give an algorithm that minimizes the makespan and prove its optimality. 5.28. Consider an online version of Pm | rj , prec | Cmax. An online algorithm for this problem can be described as follows. The jobs are again presented in a list; whenever a machine is freed, the job that ranks highest among the remaining jobs which are ready for processing is assigned to that machine (i.e., it must be a job that already has been released and of which all predecessors already have been completed). Show that the bound presented in Theorem 5.6.1 applies to this more general problem as well. Comments and References The worst case analysis of the LPT rule for Pm || Cmax is from the classic paper by Graham (1969). This paper gives one of the \ufb01rst examples of worst case analyses of heuristics (see also Graham (1966)). It also provides a worst case analysis of an arbitrary list schedule for Pm || Cmax. A more sophisticated heuristic for Pm || Cmax, with a tighter worst case bound, is the so-called MUL- TIFIT heuristic, see Co\ufb00man, Garey and Johnson (1978) and Friesen (1984a). Lee and Massey (1988) analyze a heuristic that is based on LPT as well as on MULTIFIT. Hwang, Lee and Chang (2005) perform a worst case analysis of the LPT rule for Pm | brkdwn | Cmax. For results on heuristics for the more gen- eral Qm || Cmax, see Friesen and Langston (1983), Friesen (1984b), and Dobson Comments and References 149 (1984). Davis and Ja\ufb00e (1981) present an algorithm for Rm || Cmax. The CPM and PERT procedures have been covered in many papers and textbooks, see for example, French (1982). The CP result in Theorem 5.1.5 is due to Hu (1961). See Lenstra and Rinnooy Kan (1978) with regard to Pm | pj = 1, prec | Cmax, Du and Leung (1989) with regard to P2 | tree | Cmax and Du, Leung and Young (1991) with regard to P2 | chains | Cmax. Chen and Liu (1975) and Kunde (1976) analyze the worst case behavior of the CP rule for Pm | pj = 1, prec | Cmax. Lin and Li (2004) and Li (2006) do a complexity analysis of Pm | pj = 1,Mj | Cmax and Qm | pj = p,Mj | Cmax. Apparently, no worst case analysis has been done for the LFJ rule. For Pm | prmp | Cmax, see McNaughton (1959). For Qm | prmp | Cmax, see Horvath, Lam and Sethi (1977), Gonzalez and Sahni (1978a) and McCormick and Pinedo (1995). Conway, Maxwell and Miller (1967) discuss the SPT rule for Pm ||\u2211Cj; they also give a characterization of the class of optimal schedules. For a discussion of Qm || \u2211Cj, see Horowitz and Sahni (1976). The worst case bound for the WSPT rule for Pm ||\u2211wjCj is from Kawaguchi and Kyan (1986). Elmaghraby and Park (1974) and Sarin, Ahn and Bishop (1988) present branch-and-bound algorithms for this problem. Eck and Pinedo (1993) present a heuristic for minimizing the makespan and the total completion time simultaneously. The optimality of the CP rule for Pm | pj = 1, outtree | \u2211Cj is due to Hu (1961). For complexity results with regard to Pm | prec | \u2211Cj, see Sethi (1977) and Du, Leung and Young (1990). For an analysis of the Qm | prmp |\u2211Cj problem, see Lawler and Labetoulle (1978), Gonzalez and Sahni (1978a), McCormick and Pinedo (1995), Leung and Pinedo (2003) and Gonzalez, Leung and Pinedo (2006). A signi\ufb01cant amount of work has been done on Qm | rj , pj = p, prmp | \u3b3; see Garey, Johnson, Simons and Tarjan (1981), Federgruen and Groenevelt (1986), Lawler and Martel (1989), Martel (1982) and Simons (1983). For results with regard to Qm | prmp | Lmax, see Bruno and Gonzalez (1976) and Labetoulle, Lawler, Lenstra and Rinnooy Kan (1984). For other due date related results, see Sahni and Cho (1979b). Chen and Powell (1999) and Van den Akker, Hoogeveen and Van de Velde (1999) applied branch-and-bound methods (including column generation) to Rm ||\u2211wjCj and Rm ||\u2211wjUj. The worst case analysis of an arbitrary list schedule for Pm || Cmax is re- garded as one of the basic results in online scheduling. Theorem 5.6.1 is due to Graham (1966). The analysis of the Round Robin rule and the total completion time objective is due to Motwani, Phillips and Torng (1994). Research in online scheduling has focused on other parallel machine scheduling problems as well; see, for example, Shmoys, Wein and Williamson (1995). For an overview of on- line scheduling on parallel machines with the makespan objective, see Fleischer and Wahl (2000). For comprehensive overviews of online scheduling, see Sgall (1998) and Pruhs, Sgall and Torng (2004). Chapter 6 Flow Shops and Flexible Flow Shops (Deterministic) 6.1 Flow Shops with Unlimited Intermediate Storage . . . . 152 6.2 Flow Shops with Limited Intermediate Storage . . . . . . 163 6.3 Flexible Flow Shops with Unlimited Intermediate Storage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 6.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 In many manufacturing and assembly facilities each job has to undergo a series of operations. Often, these operations have to be done on all jobs in the same order implying that the jobs have to follow the same route. The machines are then assumed to be set up in series and the environment is referred to as a \ufb02ow shop. The storage or bu\ufb00er capacities in between successive machines may some- times be, for all practical purposes, virtually unlimited. This is often the case when the products that are being processed are physically small (e.g., printed circuit boards, integrated circuits), making it relatively easy to store large quan- tities between machines. When the products are physically large (e.g., television sets, copiers), then the bu\ufb00er space in between two successive machines may have a limited capacity, causing blocking. Blocking occurs when the bu\ufb00er is full and the upstream machine is not allowed to release a job into the bu\ufb00er after completing its processing. If this is the case, then the job has to remain at the upstream machine, preventing a job in the queue at that machine from beginning its processing. A somewhat more general machine environment consists of a number of stages in series with a number of machines in parallel at each stage. A job has to be processed at each stage only on one of the machines. This machine environment is often referred to as a \ufb02exible \ufb02ow shop, compound \ufb02ow shop, multi-processor \ufb02ow shop, or hybrid \ufb02ow shop. Most of the material in this chapter concerns the makespan objective. The makespan objective is of considerable practical interest as its minimization is 151M.L. Pinedo, Scheduling, DOI: 10.1007/978-0-387-78935-4 c© Springer Science+Business Media, LLC 2008 6, 152 6 Flow Shops and Flexible Flow Shops (Deterministic) to a certain extent equivalent to the maximization of the utilization of the machines. The models, however, tend to be of such complexity that makespan results are already relatively hard to obtain. Total completion time and due date related objectives tend to be even harder. 6.1 Flow Shops with Unlimited Intermediate Storage When searching for an optimal schedule for Fm || Cmax the question arises whether it su\ufb03ces merely to determine a permutation in which the jobs traverse the entire system. Physically it may be possible for one job to \u201cpass\u201d another while waiting in queue for a machine that is busy. The machines may not operate according to the First Come First Served principle and the sequence in which the jobs go through the machines may change from one machine to another. Changing the sequence of the jobs waiting in a queue between two machines may at times result in a smaller makespan. However, it can be shown that there always exists an optimal schedule without job