it's game theory question please do itself don't do from internet otherwise I will report it Exercise

it's game theory question please do itself don't do from internet otherwise I will report it

 

Transcribed Image Text:

Exercise 5: Consider the scheduling problem Pm||Cmax. In this problem, we have m machines and n tasks. Each task i (1 in) has a processing time p, and we aim to schedule the tasks on the machines in order to minimize the makespan Cmax, which is the completion time of the last task. Throughout the exercise, we assume that if a task lies, it declares a processing time greater than its actual duration. We consider the weak model in which if a task lies about its duration, it recovers its result at the time it started execution plus its declared duration (not its actual duration). We consider the following algorithm (with non- polynomial complexity): "Construct a schedule oLPT using the LPT greedy list algorithm. Let C. be the completion time of task i in the schedule oLPT. Construct an optimal schedule with minimum makespan COPT max. Let p(i) be the machine on which task i is executed in this optimal schedule. Return the following schedule: For 1 i n, task i is executed on machine p(i) at the time ((4/3) - (1/(3m))) COPT max - Ci." Show that this algorithm has a guaranteed accuracy. Exercise 5: Consider the scheduling problem Pm||Cmax. In this problem, we have m machines and n tasks. Each task i (1 in) has a processing time p, and we aim to schedule the tasks on the machines in order to minimize the makespan Cmax, which is the completion time of the last task. Throughout the exercise, we assume that if a task lies, it declares a processing time greater than its actual duration. We consider the weak model in which if a task lies about its duration, it recovers its result at the time it started execution plus its declared duration (not its actual duration). We consider the following algorithm (with non- polynomial complexity): "Construct a schedule oLPT using the LPT greedy list algorithm. Let C. be the completion time of task i in the schedule oLPT. Construct an optimal schedule with minimum makespan COPT max. Let p(i) be the machine on which task i is executed in this optimal schedule. Return the following schedule: For 1 i n, task i is executed on machine p(i) at the time ((4/3) - (1/(3m))) COPT max - Ci." Show that this algorithm has a guaranteed accuracy.