Page 1 of 1
1. Suppose that there are m machines of positive processing speeds si s S2 S... 5 Sm and n unit-demand jobs of positive
Posted: Mon May 09, 2022 1:35 pm
by 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 26 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.