1. Suppose that there are m machines of positive processing speeds si s S2 S... 5 Sm and n unit-demand jobs of positive

[answerhappygod]

1 Suppose That There Are M Machines Of Positive Processing Speeds Si S S2 S 5 Sm And N Unit Demand Jobs Of Positive 1 (66.09 KiB) Viewed 25 times

1. Suppose that there are m machines of positive processing speeds si s S2 S... 5 Sm and n unit-demand jobs of positive weights wi S W2 <... < Wn. A scheduling for them partitions the n jobs into m sequences J1, J2, ...,Jm, and assigns Jį (possibly empty) to the machine i for 1 sism. If a job j appears as the k-th job in Jį, it would finish at time k/s; and incur a cost wjk/si. Give a polynomial-time algorithm to compute a scheduling which minimizes the total costs of all jobs.