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 frominput)
A532B321
C    110
D    523
E    431

Sort the list by LST

    Due  Effort  LST
C    110
E    431B321A532
D    523

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

01234#1CBB#2EEE

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).

01234#1BBAAA#2EEE#3C

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

Does this get you moving?