Consider the following scheduling problem: There are 10 tasks, each of which require a certain amount of processing time and have a value, as illustrated in the table below:
Task: 1 2 3 4 5 6 7 8 9 10 Value: 2 3 4 5 6 7 6 5 4 3 Processing Time: 1 2 3 4 5 6 7 6 5 4
(a) Suppose that there is a single machine with total capacity of 23 units of time, and that one gets partial credit for partially processing a task, so that processing a task of value Vi for time t when the requirements are Ti units provides value t(Vi/Ti). What is the optimal set of tasks to schedule, and the value achieved by this optimal schedule?
(b) Suppose that there are 3 machines: Machines 1 has capacity 10, Machine 2 has capacity 11, and Machine 3 has capacity 13. Suppose also that there is no partial credit, so that you only receive value for a task if it is processed fully. Find an optimal set of tasks to schedule on each machine, and the total value scheduled across all of the machines. (Hint: Think really hard before you resort to computation)