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 CS intern, I wasn't able to find a solution yet

The problem: Given a fixed amount of time, a fixed number of workers and a set of feaseble tasks, assign tasks to workers in such a way that all workers be as busy as possible, and the last worker of the group is only assigned to the remaining tasks that others weren't able to bear.

The purpose of this approach is the make the last worker as free as possible, so he can only work in those tasks when really needed

Constraints:

• Due time: each task has its own due time. It means that a task can be started any time by any worker as long as it finishes as last on the due time.
• No overlapping: a worker cannot work on multiple tasks, and a task cannot be divided between workers

So far I've tried...

• Job-Shop problem: it doesn't seem to be the case, since the tasks cannot be grouped as jobs, which must be processed by specific machines (workers in our case). In my scenario, the task can be fulfilled by any worker, without preferences.
• Flexible JSP: I really thought that was my case since the tasks could be processed by any machine (workers). But I couldn't figure how to group my tasks in jobs, since they don't have a clear sequence, but only due times.

I've tried approaches via google OR-Tools too, but none seemed fit to the problem. As it looks like a NP-complete problem, I don't think bruteforce combining tasks in order to find a solution is a way, although the set of tasks and workers is not that large.

Here are some articles I've read in order to find a similar solution:

• Fitness Uniform Optimization

• Flexible Job Shop Scheduling

• Job Shop Problem Approach to Order-Picking Problem

Thanks in advance!

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?