How To Optimize Makespan Of Worker Labor To Maximum Time Usage Given A Set Of Possible Tasks

So I'm in a bit of a difficult algorithm modeling situation and I hope you guys can help me find some directions. The problem came of logistics department of my company, and as a C

Solution 1:

Isomorphic problems have been solved. I assume that each task has a required effort, and that workers are interchangeable: for instance, Paul will be able to finish task #17 in exactly the same amount of time as Abby.

With this, scheduling turns out to be trivial: compute a "latest start time" (LST) for each task, the deadline minus the effort required. For instance, a task that takes 4 hours and is due at 18:00, has a LST of 14:00.

call the number of available workers N+1, where the +1 is the on-demand worker.

Sort the tasks by LST, and assign them to the N available workers in that order. Fill out the schedule with the obvious intervals: as each worker finishes the current task, assign the next available task.

If you reach a point in the schedule where you have a LST without an assigned worker, put that into the queue for the on-demand worker, N+1. When you get to the end, if worker N+1 has more tasks than time available, then you have no solution.

For instance, given 2+1 workers and tasks

    Due  Effort  LST (computed from input)
A    5      3     2
B    3      2     1
C    1      1     0
D    5      2     3
E    4      3     1

Sort the list by LST

    Due  Effort  LST
C    1      1     0
E    4      3     1
B    3      2     1
A    5      3     2
D    5      2     3

We now begin to lay out the schedule for each worker by hour

    0  1  2  3  4
#1  C  B  B
#2  E  E  E

At this point, we see that task A must be started, but the two normal workers are already busy. We have to assign something to #3. The overload for the job span is 1 hour (indeed, that's the entire schedule overload), so swap the 1-hour job to #3 and start the "overload" job at its LST (this will reduce the amount of backtracking and re-tries in a complex situation).

    0  1  2  3  4
#1  B  B  A  A  A
#2  E  E  E
#3  C

Now, task D is easily assigned to #2, and we're done.

Does this get you moving?