# Constraint for scheduling worker to complete task before moving on

**URL:** <https://discourse.julialang.org/t/constraint-for-scheduling-worker-to-complete-task-before-moving-on/60984>\
**Category:** Optimization (Mathematical)\
**Created:** [May 11, 2021, 9:52pm UTC](https://discourse.julialang.org/t/constraint-for-scheduling-worker-to-complete-task-before-moving-on/60984 "2021-05-11T21:52:40Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![eipi10](https://avatars.discourse-cdn.com/v4/letter/e/fbc32d/32.png) [@eipi10](https://discourse.julialang.org/u/eipi10)\
**Post date:** [May 11, 2021, 9:52pm UTC](https://discourse.julialang.org/t/constraint-for-scheduling-worker-to-complete-task-before-moving-on/60984/1 "2021-05-11T21:52:40Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![odow](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/odow/32/28685_2.png) [@odow](https://discourse.julialang.org/u/odow)\
**Post date:** [May 11, 2021, 10:28pm UTC](https://discourse.julialang.org/t/constraint-for-scheduling-worker-to-complete-task-before-moving-on/60984/2 "2021-05-11T22:28:02Z")

</div>

These are typically modeled as set partitioning models:

> **[Set Covering, Packing and Partitioning Problems](https://link.springer.com/referenceworkentry/10.1007/978-0-387-74759-0_599)**
>
> Keywords Applicability of the Problem Solution Approaches Reformulation of the Linear Description of the Problem Heuristics for the Set Partitioning and Covering Problems Exact Solution Approaches to the Set Covering, Packing and Partitioning...

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

> **[sppintro.pdf](https://www2.imm.dtu.dk/courses/02735/sppintro.pdf)**
>
> 1331.15 KB

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

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

```

---

<div class="post-metadata">

**Author:** ![eipi10](https://avatars.discourse-cdn.com/v4/letter/e/fbc32d/32.png) [@eipi10](https://discourse.julialang.org/u/eipi10)\
**Post date:** [May 11, 2021, 11:33pm UTC](https://discourse.julialang.org/t/constraint-for-scheduling-worker-to-complete-task-before-moving-on/60984/3 "2021-05-11T23:33:53Z")

</div>

Thanks! Very interesting.

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

```julia
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:

```julia
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.

---

<div class="post-metadata">

**Author:** ![odow](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/odow/32/28685_2.png) [@odow](https://discourse.julialang.org/u/odow)\
**Post date:** [May 12, 2021, 2:44am UTC](https://discourse.julialang.org/t/constraint-for-scheduling-worker-to-complete-task-before-moving-on/60984/4 "2021-05-12T02:44:21Z")

</div>

> 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.

```Julia
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.