Scheduling and Capacity constraints with variable durations

Hey people!

I do have variable starting points (S) and variable Durations (D) per task. The former results from the predecessor relationships (see below), the latter from the allocation of resources to the task (j).

@constraint( model, Sequence[j = 2:AE, h in V[j]], S[h]+D[h] <= S[j]) 

I want to make sure that each worker can only be assigned to one task at a time. So my approach was to introduce a binary matrix called schedule[planning_horizon,task] and multiply with the assignment matrix X[type_of_worker, task, worker]:

@constraint( model , [w = 1:MI, o=1:Planning_horizon], sum(Schedule[o, j] * x[i,j,w] for j = 1:AE, i=1:2 ) <= 1)

My problem is to get the link between the starting and duration variable and the index of the schedule matrix, which must become 1.

For example, if t[1] = 5 and D[1] = 5 it should look like this (the five values in between must become 1):

My appraoch was to use ConditionalJuMP:

for i = 1:AE
    @implies( model , (t[i]<=j<= t[i]+DAE[i]-1) => (Schedule[j,i]==1) for j=1:Planning_horizon) 

But it`s not working. Do you have any ideas to solve this issue?

Thanks alot guys!

If I understand correctly, you want something like:

T = 4
model = Model()
@variable(model, x[1:T], Bin)
@variable(model, 1 <= S <= T, Int)
@variable(model, D >= 0, Int)
# x[t] == 1 if S <= t <= S + D???

This type of formulation is quite difficult to work with.

There are a few alternative formulations, one example is something like:

T = 4
model = Model()
# start and stop are monotonic {0, 1} variables that begin at 1 and drop to 0
# at some point. The job starts when start => 0, and it stops when stop => 0.
@variable(model, start[1:T], Bin)
@variable(model, stop[1:T], Bin)
@constraint(model, [t=2:T], start[t-1] >= start[t])
@constraint(model, [t=2:T], stop[t-1] >= stop[t])
# We can work out the activity of each job by looking at the difference. When
# they are both 1, the job hasn't started yet. When they are both 0, the job has
# stopped.
@expression(model, x[t=1:T], stop[t] - start[t])
@expression(model, D, sum(x)) # The duration is sum(x)
@expression(model, S, sum(start)) # starting block is the sum of start
# With a constraint that the duration cannot be negative.
@constraint(model, D >= 0)

You could also look into set partitioning formulations. If you search “job shop scheduling” you should be able to find a large number of papers that are similar to your problem.

1 Like

thank you!
That solves my problem:)

1 Like