2
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

Without going into a ton of detail, the usual approach is to include a variable for the start time of each task, and a variable for the end time of each task. (Your binary assignment variables are also included.) Your objective (known as the makespan) is the maximum of the task end times. The end time for a task is the start time plus the processing time (which in your case is contingent on the assigned worker). Precedence constraints are simply (end time of predecessor) <= (start time of successor).

Improve this answer
$\endgroup$
5
  • $\begingroup$ I second this. By the way, here are some examples that follow this modeling approach: Pyomo cookbook makespan scheduling and stackoverflow link. $\endgroup$
    – dhasson
    Oct 14, 2020 at 21:00
  • $\begingroup$ 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)) $\endgroup$
    – tphillips
    Oct 15, 2020 at 2:45
  • 1
    $\begingroup$ @tphillips, it sounds like a resource-constrained project schedule problem with minimizing the completion time or makespan. $\endgroup$
    – A.Omidi
    Oct 15, 2020 at 18:13
  • 2
    $\begingroup$ You add a variable for makespan, constrain it to be >= each completion time, and minimize it. $\endgroup$
    – prubin ♦
    Oct 15, 2020 at 21:10
  • $\begingroup$ Thanks all. Both for the link @A.Omidi and for helping me spot the obvious prubin ...Sorry for not seeing that, I'm not normally doing OR problems and just getting into it $\endgroup$
    – tphillips
    Oct 16, 2020 at 3:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.