Constraint for scheduling worker to complete task before moving on

Specific Domains Optimization (Mathematical)
1

I have a worker-task scheduling problem that I am using a MILP on with JuMP. I want to set a constraint where once a worker starts a task they must complete that task before moving to a new task. I am looking at workers, tasks, and time. How is this constraint typically described? Can someone point me to an example?

I can imagine it as an if-else statement where: if a worker starts a task, then the work output must be greater than 0 until task completed. But not sure how that is typically formalized.

2

These are typically modeled as set partitioning models:

There is plenty of online lecture material, e.g., I just Googled:

One variation (haven’t tested, so there may be typos, etc.):

model = Model()
N = 3
# A[i, j] = 1 if task j is performed at time i
A = [
    1 0 1
    1 0 1
    0 1 1
    0 1 0
]
I, J = size(A)
# x[w,j] = 1 if assign worker w to task j
@variable(model, x[1:N, 1:J], Bin)
# Each task j needs to be done by exactly one worker
@constraint(model, [j = 1:J], sum(x[:, j]) == 1)
# Each worker w can do at most 1 task in each time period i
@constraint(model, [w = 1:N, i = 1:I], sum(A[i, j] * x[w, j] for j = 1:J) <= 1)
3

Thanks! Very interesting.

The only difference is that in my case A is also variable. So in the above situation:

A = [
    1 0 1
    1 0 1
    0 1 1
    0 1 0
]

The 1’s are always sequential - which is good. But since A is variable in my problem it can arrive at:

A = [
    1 0 1
    0 1 1
    1 0 1
    0 1 0
]

but I want to constrain this from happening. I want the 1’s to be sequential over time - i.e. there can be no 0 in between any set of 1’s along the time dimension.

4

The only difference is that in my case A is also variable

The trick is to make A data, not a variable.

Enumerate the list of start times instead. Now you might have a different A matrix for each task.

A = [
    1 0 0
    1 1 0
    0 1 1
    0 0 1
]

If you google “scheduling” “linear program” “set partitioning” (exactly one worker completes each task) “set covering” (at least one worker completes each task) you should be able to find examples and lectures on the subject.

1 Like