251 pág.

# Pinedo_problemas_deterministicos

Pré-visualização50 páginas

problem 1 ||\u2211hj(Cj). This chapter has also shown an application of a Fully Polynomial Time Ap- proximation Scheme (FPTAS) for a single machine scheduling problem. Over the last decade Polynomial Time Approximation Schemes (PTAS) and Fully Polynomial Time Approximation Schemes (FPTAS) have received an enormous amount of attention. Most of this attention has focused on NP-hard problems 62 3 Single Machine Models (Deterministic) that are close to the boundaries separating NP-hard problems from polynomial time problems, e.g., 1 | rj | \u2211 Cj . Most of the problems described in this chapter can be formulated as Mixed Integer Programs (MIPs). Mixed Integer Programming formulations of several single machine scheduling problems are presented in Appendix A. This appendix gives also an overview of the techniques that can be applied to MIPs. This chapter does not exhibit all the possible procedures and techniques that can be brought to bear on single machine scheduling problems. One important class of solution procedures is often referred to as constraint programming. Appendix C gives a detailed description of this class of procedures and Chapter 15 provides an example of a constraint programming procedure that can be applied to 1 | rj | \u2211 wjUj . Many heuristic procedures have been developed that can be applied to single machine scheduling problems. These procedures include the so-called composite dispatching rules as well as local search techniques. Chapter 14 provides an in- depth overview of these techniques and their applications to single machine problems. The next chapter considers more general and more complicated single ma- chine problems. It focuses on problems with non-regular objective functions and on problems with multiple objective functions. Exercises (Computational) 3.1. Consider 1 ||\u2211wjCj with the following weights and processing times. jobs 1 2 3 4 5 6 7 wj 0 18 12 8 8 17 16 pj 3 6 6 5 4 8 9 (a) Find all optimal sequences. (b) Determine the e\ufb00ect of a change in p2 from 6 to 7 on the optimal sequence(s). (c) Determine the e\ufb00ect of the change under (b) on the value of the objec- tive. 3.2. Consider 1 | chains | \u2211wjCj with the same set of jobs as in Exercise 3.1.(a). The jobs are now subject to precedence constraints which take the form of chains: 1 \u2192 2 3 \u2192 4 \u2192 5 6 \u2192 7 Find all optimal sequences. Exercises 63 3.3. Consider 1 ||\u2211wj(1\u2212e\u2212rCj) with the same set of jobs as in Exercise 3.1. (a) Assume the discount rate r is 0.05. Find the optimal sequence. Is it unique? (b) Assume the discount rate r is 0.5. Does the optimal sequence change? 3.4. Find all optimal sequences for the instance of 1 || hmax with the following jobs. jobs 1 2 3 4 5 6 7 pj 4 8 12 7 6 9 9 hj(Cj) 3 C1 77 C23 1.5C4 70 + \u221a C5 1.6 C6 1.4 C7 3.5. Consider 1 | prec | hmax with the same set of jobs as in Exercise 3.4 and the following precedence constraints. 1 \u2192 7 \u2192 6 5 \u2192 7 5 \u2192 4 Find the optimal sequence. 3.6. Solve by branch-and-bound the following instance of the 1 | rj | Lmax problem. jobs 1 2 3 4 5 6 7 pj 6 18 12 10 10 17 16 rj 0 0 0 14 25 25 50 dj 8 42 44 24 90 85 68 3.7. Consider the same problem as in the previous exercise. However, now the jobs are subject to the following precedence constraints. 2 \u2192 1 \u2192 4 6 \u2192 7 Find the optimal sequence. 3.8. Find the optimal sequence for the following instance of the 1 || \u2211Tj problem. jobs 1 2 3 4 5 6 7 8 pj 6 18 12 10 10 11 5 7 dj 8 42 44 24 26 26 70 75 64 3 Single Machine Models (Deterministic) Hint: Before applying the dynamic programming algorithm, consider \ufb01rst the elimination criterion in Lemma 3.4.1. 3.9. Consider a single machine and 6 jobs. jobs 1 2 3 4 5 6 pj 1190 810 1565 719 1290 482 dj 1996 2000 2660 3360 3370 3375 Apply the FPTAS described in Section 3.5 to this instance with 4 = 0.02. Are all sequences that are optimal for the rescaled data set also optimal for the original data set? 3.10. Find the optimal sequence for the following instance of the 1 ||\u2211wjTj problem. jobs 1 2 3 4 5 6 7 pj 6 18 12 10 10 17 16 wj 1 5 2 4 1 4 2 dj 8 42 44 24 90 85 68 Exercises (Theory) 3.11. Consider 1 ||\u2211wj(1\u2212e\u2212rCj). Assume that wj/pj \ufffd= wk/pk for all j and k. Show that for r su\ufb03ciently close to zero the optimal sequence is WSPT. 3.12. Show that if all jobs have equal weights, i.e., wj = 1 for all j, the WDSPT rule is equivalent to the Shortest Processing Time \ufb01rst (SPT ) rule for any r, 0 < r < 1. 3.13. Consider the problem 1 | prmp | \u2211hj(Cj). Show that if the functions hj are nondecreasing there exists an optimal schedule that is nonpreemptive. Does the result continue to hold for arbitrary functions hj? 3.14. Consider the problem 1 | rj | \u2211 Cj . (a) Show through a counterexample that the nonpreemptive rule that se- lects, whenever a machine is freed, the shortest job among those available for processing is not always optimal. In part (b) and (c) this rule is referred to as SPT\u2217. (b) Perform a worst case analysis of the SPT\u2217 rule, i.e., determine the maximum possible value of the ratio \u2211 Cj(SPT \u2217)/ \u2211 Cj(OPT ). Exercises 65 (c) Design a heuristic for 1 | rj | Cj that performs better than SPT\u2217. 3.15. Consider the problem 1 | rj , prmp | \u2211 Cj . Show that the preemptive Shortest Remaining Processing Time \ufb01rst (SRPT) rule is optimal. 3.16. Consider the problem 1 | prmp | \u2211Cj with the additional restriction that job j has to be completed by a hard deadline d¯j . Assuming that there are feasible schedules, give an algorithm that minimizes the total completion time and prove that it leads to optimality. 3.17. Consider the following preemptive version of the WSPT rule: if pj(t) denotes the remaining processing time of job j at time t, then a preemptive version of the WSPT rule puts at every point in time the job with the highest wj/pj(t) ratio on the machine. Show, through a counterexample, that this rule is not necessarily optimal for 1 | rj , prmp | \u2211 wjCj . 3.18. Give an algorithm for 1 | intree |\u2211wjCj and prove that it leads to an optimal schedule (recall that in an intree each job has at most one successor). 3.19. Give an algorithm for 1 | outtree |\u2211wjCj and show that it leads to an optimal schedule (recall that in an outtree each job has at most one predecessor). 3.20. Consider the problem 1 || Lmax. The Minimum Slack \ufb01rst (MS) rule selects at time t, when a machine is freed, among the remaining jobs the job with the minimum slack max(dj \u2212 pj \u2212 t, 0). Show through a counterexample that this rule is not necessarily optimal. 3.21. Perform an Adjacent Sequence Interchange for the weighted discounted \ufb02ow time cost function. That is, state and prove a result similar to Lemma 3.1.2. 3.22. Consider the problem 1 | chains | \u2211wj(1 \u2212 e\u2212rCj). Describe the algo- rithm that solves this problem and prove that it results in an optimal sequence. 3.23. Consider the problem 1 | prec | max(h1(S1), . . . , hn(Sn)), where Sj de- notes the starting time of job j. The cost function hj , j = 1, . . . , n is decreasing. Unforced idleness of the machine is not allowed. Describe a dynamic program- ming type algorithm for this problem similar to the one in Section 3.2. Why does one have to use here forward dynamic programming instead of backward dynamic programming? 3.24. Consider the problem 1 | rj , prmp | Lmax. Determine the optimal sched- ule and prove its optimality. 3.25. Show that (a) SPT is optimal for 1 | brkdwn |\u2211Cj , (b) Algorithm 3.3.1 is optimal for 1 | brkdwn |\u2211Uj , (c) WSPT is not necessarily optimal for 1 | brkdwn |\u2211wjCj . 66 3 Single Machine Models (Deterministic) 3.26. Consider 1 ||\u2211wjTj . Prove or disprove the following statement: If wj/pj > wk/pk, pj < pk, and dj < dk, then there exists an optimal sequence in which job j appears before job k. 3.27. Complete the \ufb01rst step of the proof of Theorem 3.3.2. Comments and References The optimality of the WSPT rule for 1 ||\u2211wjCj appears in the seminal paper byW.E. Smith (1956). Lawler (1978), Monma and Sidney (1979, 1987), Mo¨hring and Radermacher (1985a) and Sidney and Steiner