251 pág.

# Pinedo_problemas_deterministicos

Pré-visualização50 páginas

not increase the value of Lmax. The branching rule is thus fairly easy. There are several ways in which bounds for nodes can be obtained. An easy lower bound for a node at level k \u2212 1 can be established by scheduling the remaining jobs J according to the preemptive EDD rule. The preemptive EDD rule is known to be optimal for 1 | rj , prmp | Lmax (see Exercise 3.24) and 46 3 Single Machine Models (Deterministic) Lower bound = 5 Lower bound = 6 Lower bound = 7 Level 1 Level 0 Level 2 Level 3Value of objectivefunction is 5 1, 2, *, * 1, 3, *, * 1, *, *, * 2, *, *, * 3, *, *, * *, *, *, * 4, *, *, * 1, 3, 4, 2 Fig. 3.5 Branch-and-bound procedure for Example 3.2.5 thus provides a lower bound for the problem at hand. If a preemptive EDD rule results in a nonpreemptive schedule, then all nodes with a higher lower bound may be disregarded. Example 3.2.5 (Branch-and-Bound for Minimizing Maximum Lateness) Consider the following 4 jobs. jobs 1 2 3 4 pj 4 2 6 5 rj 0 1 3 5 dj 8 12 11 10 At level 1 of the search tree there are four nodes: (1, \u2217, \u2217, \u2217), (2, \u2217, \u2217, \u2217), (3, \u2217, \u2217, \u2217) and (4, \u2217, \u2217, \u2217). It is easy to see that nodes (3, \u2217, \u2217, \u2217) and (4, \u2217, \u2217, \u2217) may be disregarded immediately. Job 3 is released at time 3; if job 2 would start its processing at time 1, job 3 still can start at time 3. Job 4 is released at time 5; if job 1 would start its processing at time 0, job 4 still can start at time 5 (see Figure 3.5). 3.3 The Number of Tardy Jobs 47 Computing a lower bound for node (1, \u2217, \u2217, \u2217) according to the preemptive EDD rule results in a schedule where job 3 is processed during the time interval [4,5], job 4 during the time interval [5,10], job 3 (again) during interval [10,15] and job 2 during interval [15,17]. The Lmax of this schedule, which provides a lower bound for node (1, \u2217, \u2217, \u2217), is 5. In a similar way a lower bound can be obtained for node (2, \u2217, \u2217, \u2217). The value of this lower bound is 7. Consider node (1, 2, \u2217, \u2217) at level 2. The lower bound for this node is 6 and is determined by the (nonpreemptive) schedule 1, 2, 4, 3. Proceed with node (1, 3, \u2217, \u2217) at level 2. The lower bound is 5 and determined by the (nonpreemptive) schedule 1,3,4,2. From the fact that the lower bound for node (1, \u2217, \u2217, \u2217) is 5 and the lower bound for node (2, \u2217, \u2217, \u2217) is larger than 5 it follows that schedule 1, 3, 4, 2 has to be optimal. || The problem 1 | rj , prec | Lmax can be handled in a similar way. This prob- lem, from an enumeration point of view, is easier than the problem without precedence constraints, since the precedence constraints allow certain schedules to be ruled out immediately. 3.3 The Number of Tardy Jobs Another due date related objective is \u2211 Uj. This objective may at \ufb01rst appear somewhat arti\ufb01cial and of no practical interest. However, in the real world it is a performance measure that is often monitored and according to which managers are being measured. It is equivalent to the percentage of on time shipments. An optimal schedule for 1 || \u2211Uj takes the form of one set of jobs that will meet their due dates and that are scheduled \ufb01rst followed by the set of remaining jobs that will not meet their due dates and that are scheduled last. It follows from the results in the previous section that the \ufb01rst set of jobs have to be scheduled according to EDD in order to make sure that Lmax is negative; the order in which the second set of jobs is scheduled is immaterial. The problem 1 || \u2211Uj can be solved easily using a forward algorithm. Re- order the jobs in such a way that d1 \u2264 d2 \u2264 · · · \u2264 dn. The algorithm goes through n iterations. In iteration k of the algorithm jobs 1, 2, . . . , k are taken into consideration. Of these k jobs, the subset J refers to jobs that, in an opti- mal schedule, may be completed before their due dates and the subset Jd refers to jobs that already have been discarded and will not meet their due dates in the optimal schedule. In iteration k the set Jc refers to jobs k+1, k+2, . . . , n. Algorithm 3.3.1 (Minimizing Number of Tardy Jobs) Step 1. Set J = \u2205, Jc = {1, . . . , n}, and Jd = \u2205. Set the counter k = 1. 48 3 Single Machine Models (Deterministic) Step 2. Add job k to J . Delete job k from Jc. Go to Step 3. Step 3. If \u2211 j\u2208J pj \u2264 dk, go to Step 4. Otherwise, let , denote the job that satis\ufb01es p\ufffd = max j\u2208J (pj). Delete job , from J . Add job , to Jd. Step 4. Set Jk = J . If k = n STOP, otherwise set k = k + 1 and go to Step 2. || In words the algorithm can be described as follows. Jobs are added to the set of on-time jobs in increasing order of their due dates. If including job k to the set of scheduled jobs implies that job k would be completed late, then the scheduled job with the longest processing time, say job ,, is marked late and discarded. Since the algorithm basically orders the jobs according to their due dates, the worst case computation time is that of a simple sort, i.e., O(n log(n)). Note that the algorithm creates in its last step n job sets J1, . . . , Jn. Set Jk is a subset of jobs {1, . . . , k}, consisting of those jobs that are candidates for meeting their due dates in the \ufb01nal optimal schedule. Set Jn consists of all jobs that meet their due dates in the optimal schedule generated. Theorem 3.3.2. Algorithm 3.3.1 yields an optimal schedule for 1 ||\u2211Uj. Proof. The proof uses the following notation and terminology. A job set J is called feasible if the jobs, scheduled according to EDD, all meet their due dates. A job set J is called l\u2212optimal if it is a feasible subset of jobs 1, . . . , l and if it has, among all feasible subsets of jobs 1, . . . , l, the maximum number of jobs. The proof consists of three steps. The \ufb01rst step of the proof shows that the job sets J1, . . . , Jn created in Step 4 of the algorithm are all feasible. This can be shown by induction (see Exercise 3.27). The second step of the proof shows that for l > k, there exists an l\u2212optimal set that consists of a subset of jobs Jk and a subset of jobs k + 1, . . . , l. To show this, assume it is true for k\u2212 1, i.e., there exists an l\u2212optimal set J \u2032 that consists of a subset of jobs from set Jk\u22121 and a subset of jobs k, k + 1, . . . , l. 3.3 The Number of Tardy Jobs 49 It can be shown that an l\u2212optimal set J \u2032\u2032 can be created from Jk and jobs k + 1, . . . , l by considering three cases: Case 1: Set Jk consists of set Jk\u22121 plus job k. In order to create set J \u2032\u2032, just take set J \u2032. Case 2: Set Jk consists of set Jk\u22121 plus job k minus some job q which is not an element of set J \u2032. Again, in order to create set J \u2032\u2032, just take set J \u2032. Case 3: Set Jk is equal to set Jk\u22121 plus job k minus some job q which is an element of set J \u2032. The argument is now a little bit more complicated. Since Jk\u22121 plus k is not a feasible set, there must exist in the set that comprises Jk\u22121 and k a job r that is not an element of J \u2032. Take any such r. Now, to create set J \u2032\u2032, take set J \u2032, include job r and delete job q. Clearly, set J \u2032\u2032 is a subset of set Jk and jobs k + 1, . . . , n. Since the number of jobs in J \u2032\u2032 is the same as the number of jobs in J \u2032, it only remains to be shown that J \u2032\u2032 is feasible. Since J \u2032\u2032 di\ufb00ers from J \u2032 only in its intersection with jobs {1, . . . , k}, it su\ufb03ces to verify two properties, namely that the job set which is the intersection of set J \u2032\u2032 and set {1, . . . , k} is feasible and that the total processing time of the jobs in the intersection of J \u2032\u2032 and {1, . . . , k} is less than or equal to the total processing time of the jobs in the intersection of J \u2032 and {1, . . . , k}. The feasibility of the intersection of J \u2032\u2032 and set {1, . . . , k} follows from the fact that it is a subset of Jk, which is feasible because of the \ufb01rst step of the proof. The second property follows from the fact that pr \u2264 pq. The third and \ufb01nal step of the proof shows that set Jk is k\u2212optimal for k = 1, . . . , n. It is clearly true for k = 0 and k = 1. Suppose it is true for k\u2212 1. From the previous step it follows that the set that comprises