# Constraint for scheduling worker to complete task before moving on

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.

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

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.

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