DisciplinaPlanejamento da Producao27 materiais • 261 seguidores
the same amount of processing to do. Now Cmax(LPT ) \u2264 pn + \u2211n\u22121 j=1 pj m = pn(1\u2212 1 m ) + \u2211n j=1 pj m . Since Cmax(OPT ) \u2265 \u2211n j=1 pj m the following series of inequalities holds for the counterexample: 4 3 \u2212 1 3m < Cmax(LPT ) Cmax(OPT ) \u2264 pn(1\u2212 1/m) + \u2211n j=1 pj/m Cmax(OPT ) = pn(1\u2212 1/m) Cmax(OPT ) + \u2211n j=1 pj/m Cmax(OPT ) \u2264 pn(1 \u2212 1/m) Cmax(OPT ) + 1. 114 5 Parallel Machine Models (Deterministic) Thus 4 3 \u2212 1 3m < pn(1 \u2212 1/m) Cmax(OPT ) + 1 and Cmax(OPT ) < 3pn. Note that this last inequality is a strict inequality. This implies that for the smallest counterexample the optimal schedule may result in at most two jobs on each machine. It can be shown that if an optimal schedule is a schedule with at most two jobs on each machine then the LPT schedule is optimal and the ratio of the two makespans is equal to one (see Exercise 5.11.b). This contradiction completes the proof of the theorem. unionsq Example 5.1.2 (A Worst Case Example of LPT) Consider 4 parallel machines and 9 jobs, whose processing times are given in the table below: jobs 1 2 3 4 5 6 7 8 9 pj 7 7 6 6 5 5 4 4 4 Scheduling the jobs according to LPT results in a makespan of 15. It can be shown easily that for this set of jobs a schedule can be found with a makespan of 12 (see Figure 5.1). This particular instance is thus a worst case when there are 4 machines in parallel. || What would the worst case be, if instead of LPT an arbitrary priority rule is used? Consider the case where at time t = 0 the jobs are put in an arbitrary list. Whenever a machine is freed the job that ranks, among the remaining jobs, highest on the list is put on the machine. It can be shown that the worst case of this arbitrary list rule satis\ufb01es the inequality Cmax(LIST ) Cmax(OPT ) \u2264 2\u2212 1 m . (This result can be shown via arguments that are similar to the proof of Theo- rem 5.6.1 in the section on online scheduling.) However, there are also several other heuristics for the Pm || Cmax problem that are more sophisticated than LPT and that have tighter worst-case bounds. These heuristics are beyond the scope of this book. Consider now the same problem with the jobs subject to precedence con- straints, i.e., Pm | prec | Cmax. From a complexity point of view this problem has to be at least as hard as the problem without precedence constraints. To obtain some insights into the e\ufb00ects of precedence constraints, a number of special cases have to be considered. The special case with a single machine 5.1 The Makespan without Preemptions 115 0 4 8 12 16 4 3 5 6 2 1 Cmax(LPT) = 15 7 8 9 t 0 4 8 12 87 3 9 4 2 1 Cmax(OPT) = 12 5 6 t Fig. 5.1 Worst case example of LPT is clearly trivial. It is enough to keep the machine continuously busy and the makespan will be equal to the sum of the processing times. Consider the special case where there are an unlimited number of machines in parallel, or where the number of machines is at least as large as the number of jobs, i.e., m \u2265 n. This problem may be denoted by P\u221e | prec | Cmax. This is a classical problem in the \ufb01eld of project planning and its study has led to the development of the well-known Critical Path Method (CPM) and Project Evaluation and Re- view Technique (PERT). The optimal schedule and the minimum makespan are determined through a very simple algorithm. Algorithm 5.1.3 (Minimizing the Makespan of a Project) Schedule the jobs one at a time starting at time zero. Whenever a job has been completed, start all jobs of which all predecessors have been completed (that is, all schedulable jobs.) || That this algorithm leads to an optimal schedule can be shown easily. The proof is left as an exercise. It turns out that in P\u221e | prec | Cmax the start of the processing of some jobs usually can be postponed without increasing the makespan. These jobs are referred to as the slack jobs. The jobs that cannot be postponed are referred to as the critical jobs. The set of critical jobs is referred to 116 5 Parallel Machine Models (Deterministic) 1 2 4 5 6 7 8 9 3 Fig. 5.2 Precedence constraints graph with critical path in Example 5.1.4 as the critical path(s). In order to determine the critical jobs, perform the same procedure applied in Algorithm 5.1.3 backwards. Start at the makespan, which is now known, and work towards time zero, while adhering to the precedence relationships. Doing this, all jobs are completed at the latest possible completion times and therefore started at their latest possible starting times as well. Those jobs whose earliest possible starting times are equal to their latest possible starting times are the critical jobs. Example 5.1.4 (Minimizing the Makespan of a Project) Consider nine jobs with the following processing times. jobs 1 2 3 4 5 6 7 8 9 pj 4 9 3 3 6 8 8 12 6 The precedence constraints are depicted in Figure 5.2. The earliest completion time C\u2032j of job j can be computed easily. jobs 1 2 3 4 5 6 7 8 9 C\u2032j 4 13 3 6 12 21 32 24 30 This implies that the makespan is 32. Assuming that the makespan is 32, the latest possible completion times C\u2032\u2032j can be computed. jobs 1 2 3 4 5 6 7 8 9 C\u2032\u2032j 7 16 3 6 12 24 32 24 32 Those jobs of which the earliest possible completion times are equal to the latest possible completion times are said to be on the critical path. So the critical path is the chain 3\u2192 4\u2192 5\u2192 8\u2192 7. 5.1 The Makespan without Preemptions 117 Level 5 Level 4 Level 3 Level 2 Level 1 Level 5 Level 4 Level 3 Level 2 Level 1 Fig. 5.3 Intree and outtree The critical path in this case happens to be unique. The jobs that are not on the critical path are said to be slack. The amount of slack time for job j is the di\ufb00erence between its latest possible completion time and its earliest possible completion time. || In contrast to 1 | prec | Cmax and P\u221e | prec | Cmax, the Pm | prec | Cmax is strongly NP-hard when 2 \u2264 m < n. Even the special case with all processing times equal to 1, i.e., Pm | pj = 1, prec | Cmax, is not easy. However, constraining the problem further and assuming that the precedence graph takes the form of a tree (either an intree or an outtree) results in a problem, i.e., Pm | pj = 1, tree | Cmax, that is easily solvable. This particular problem leads to a well-known scheduling rule, the Critical Path (CP) rule, which gives the highest priority to the job at the head of the longest string of jobs in the precedence graph (ties may be broken arbitrarily). Before presenting the results concerning Pm | pj = 1, tree | Cmax it is necessary to introduce some notation. Consider an intree. The single job with no successors is called the root and is located at level 1. The jobs immediately preceding the root are at level 2; the jobs immediately preceding the jobs at level 2 are at level 3, and so on. In an outtree all jobs with no successors are located at level 1. Jobs that have only jobs at level 1 as their immediate successors are said to be at level 2; jobs that have only jobs at levels 1 and 2 as their immediate successors are at level 3, and so on (see Figure 5.3). From this de\ufb01nition it follows that the CP rule is equivalent to the Highest Level \ufb01rst rule. The number of jobs at level l is denoted by N(l). Jobs with no predecessors are referred to as starting jobs; the nodes in the graph corresponding to these jobs are often referred to in graph theory terminology as leaves. The highest level in the graph is denoted by lmax. Let H(lmax + 1\u2212 r) = r\u2211 k=1 N(lmax + 1\u2212 k). 118 5 Parallel Machine Models (Deterministic) Clearly, H(lmax+1\u2212 r) denotes the total number of nodes at level lmax+1\u2212 r or higher, that is, at the highest r levels. Theorem 5.1.5. The CP rule is optimal for Pm | pj = 1, intree | Cmax and for Pm | pj = 1, outtree | Cmax. Proof. The proof for intrees is slightly harder than the proof for outtrees. In what follows only the proof for intrees is given (the proof for outtrees is left as an exercise). In the proof for intrees a distinction has to be made between two cases. Case I.