I have a modified assignment problem for which I'm having difficulty formulating the constraints mathematically.

I have a set of workers and a set of tasks which should be completed in the minimum time possible. Each worker is unique and will take a different amount of time to do each task than the other workers. Some workers cannot do certain tasks, but each task can be completed by at least one worker. Additionally, there is the constraint that some tasks have "prerequisite" tasks which must be completed before that task can start.

How could I formulate this problem and its constraints efficiently/mathematically? It seems reasonable to make the decision variable a binary vector of length $$WT$$ if there are $$W$$ workers and $$T$$ tasks. Then in the first $$W$$ variables, only one of them can be $$1$$ and the rest $$0$$, meaning that the first task is assigned to a particular worker. But mainly I'm having trouble incorporating the "prerequisite" constraints on tasks, because they are affected by which prerequisite is assigned to which worker, and how long it will take the worker to complete the prerequisite.

• Thanks, that is quite helpful. I managed to implement a variant of the SO link using Google's ortools. Now struggling with the objective function: I want to minimize the largest "task finish time", is it equivalent to minimizing the sum of all finish times? I couldn't find a function like solver.Minimize(max(finish_times)) Oct 15 '20 at 2:45
• @tphillips, it sounds like a resource-constrained project schedule problem with minimizing the completion time or makespan. Oct 15 '20 at 18:13