Pinedo_problemas_deterministicos
251 pág.

Pinedo_problemas_deterministicos


DisciplinaPlanejamento da Producao27 materiais263 seguidores
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