Show the steps of deriving your answers. Points will be deducted for answers without adequate steps discussed. Submit your homework via Blackboard as one PDF or Word document.
(25) [Greedy packing] Textbook Exercise 3 in Chapter 4. Hint: One possible measure of
“staying ahead” is the number of boxes that fit in any given number of trucks. Prove by induction, that is, first prove the base case and then state an inductive hypothesis and prove the inductive case.
(25) ) [Minimum lateness job scheduling] Consider the four jobs (Job i, i = 1, 2, 3, 4) in the table below, where ti is the processing time and di is the deadline of each Job i. Show a job schedule that is optimal but does not follow the earliest-deadline-first strategy and contains at least one inversion. Then, repeatedly remove inversions until we have an optimal schedule that can be generated using the earliest-deadline-first strategy. Show the job schedule after removing each inversion.
Job i
1
2
3
4
ti
3
2
1
4
di
6
8
9
11
Last modified: September 19, 2019
