We consider the problem of scheduling a set J of jobs on M N uniform parallel...

Transcribed Image Text:

We consider the problem of scheduling a set J of jobs on M N uniform parallel machines. Each job j J has a processing requirement p; = N which denotes the number of days needed to process the job on any one of the machines. Each job also comes with a release date r; N, representing the beginning of the day the job j becomes available for processing, and a due date d; r; +pj, representing the beginning of the day by the end of which job j must be completed (d; is also a natural number). We start our count of days from day 0. Any machine can process only one job in a single day, and any job can be processed by at most one machine on a given day. However, we allow preemptions, i.e., we can interrupt a job and process it on different machines on different days (recall that all machines are uniform, i.e., have the same processing speed). The scheduling problem is determine if there exists a feasible schedule of jobs assigned to machines on different days such that all jobs are processed in their respective windows. Give an algorithm that decides in polynomial time whether a feasible schedule exists or not. The algorithm should be polynomial time in the data, that is polynomial in |J], M, e(log rj+ log dj + log pj). [Hint: The following construction could be useful: Arrange the numbers rj, d; in ascending order and create 2|J| -1 intervals of consecutive days defined by these numbers.] We consider the problem of scheduling a set J of jobs on M N uniform parallel machines. Each job j J has a processing requirement p; = N which denotes the number of days needed to process the job on any one of the machines. Each job also comes with a release date r; N, representing the beginning of the day the job j becomes available for processing, and a due date d; r; +pj, representing the beginning of the day by the end of which job j must be completed (d; is also a natural number). We start our count of days from day 0. Any machine can process only one job in a single day, and any job can be processed by at most one machine on a given day. However, we allow preemptions, i.e., we can interrupt a job and process it on different machines on different days (recall that all machines are uniform, i.e., have the same processing speed). The scheduling problem is determine if there exists a feasible schedule of jobs assigned to machines on different days such that all jobs are processed in their respective windows. Give an algorithm that decides in polynomial time whether a feasible schedule exists or not. The algorithm should be polynomial time in the data, that is polynomial in |J], M, e(log rj+ log dj + log pj). [Hint: The following construction could be useful: Arrange the numbers rj, d; in ascending order and create 2|J| -1 intervals of consecutive days defined by these numbers.]