Consider the problem (Pm): Om||Cmax of minimizing maximum completion time on a set of m machines....

 

Transcribed Image Text:

Consider the problem (Pm): Om||Cmax of minimizing maximum completion time on a set of m machines. We further consider the problem (Qm): Om/pmtn Cmax of minimizing maximum comple- tion time on a set of m machines, where we allow jobs to be preempted. (a) Consider an arbitrary instance I of P₂. So we have say n jobs, each consisting of two operations, to be processed on two machines, where pj denotes the processing time required by job jon machine i, for i=1, 2, and j = 1,...,n. Describe how to compute an optimal schedule in a number of steps that is linear in n. Prove that your approach yields a minimum length schedule. (b) Apparently the problem is much more difficult for three machines than for two machines. Provide an instance I' with three machines and three or four jobs (each with three operations), such that problems P3(I) and Qs(1') have solutions of different values. Prove that your solution of Q3(I') is indeed optimal, and argue that any solution to Ps(1') has a strictly higher value than the optimal solution to Q3(1'). (c) Consider the instance I" of Q₁, defined by the following 4 by 4 matrix of processing times, where rows correspond to machines. jobs j1234 Plj P2j P3j 2377 8 417 4674 Compute an optimal solution for this instance, minimizing makespan, and allowing for preemption. Consider the problem (Pm): Om||Cmax of minimizing maximum completion time on a set of m machines. We further consider the problem (Qm): Om/pmtn Cmax of minimizing maximum comple- tion time on a set of m machines, where we allow jobs to be preempted. (a) Consider an arbitrary instance I of P₂. So we have say n jobs, each consisting of two operations, to be processed on two machines, where pj denotes the processing time required by job jon machine i, for i=1, 2, and j = 1,...,n. Describe how to compute an optimal schedule in a number of steps that is linear in n. Prove that your approach yields a minimum length schedule. (b) Apparently the problem is much more difficult for three machines than for two machines. Provide an instance I' with three machines and three or four jobs (each with three operations), such that problems P3(I) and Qs(1') have solutions of different values. Prove that your solution of Q3(I') is indeed optimal, and argue that any solution to Ps(1') has a strictly higher value than the optimal solution to Q3(1'). (c) Consider the instance I" of Q₁, defined by the following 4 by 4 matrix of processing times, where rows correspond to machines. jobs j1234 Plj P2j P3j 2377 8 417 4674 Compute an optimal solution for this instance, minimizing makespan, and allowing for preemption.

Answer rating: 100% (QA)

a Lineartime algorithm for P on two machines Let I be an instance of P with n jobs and two machines We can compute an optimal schedule in a number of steps that is linear in n as follows Sort the jobs ... View the full answer