Scheduling with Gurobi - how to order / sequence tasks
AnsweredI am using Gurobi to solve a popular scheduling problem. I am struggling to add a constraint which requires sequencing of different tasks. I am sharing some background around the problem below. Also, I have added all the other constraints, and I get an optimal solution as well. Having solved scheduling problems in a constraint programming solver, I am familiar with interval_varibles, span, sequence constraints etc, but I am trying to understand how to express the same with Gurobi.
There are five houses to be built by two workers. For each house, there are ten house building tasks, each with a given duration, or size. Each house also has a given earliest starting date. For each task, there is a list of tasks that must be completed before the task can start. Each task must be performed by a given worker, and there is a transition time associated with a worker transferring from one house to another house. There are costs associated with completing eachhouse after its preferred due date and with the length of time it takes to complete each house.
There are constraints that specify a particular task may not begin until one or more given tasks have been completed. In addition, there are constraints that specify that a worker can be assigned to only one task at a time and that it takes time for a worker to travel from one house to the other.
The objective is to minimize the cost incurred through tardiness and length costs.
Below is my attempt:
import gurobipy as gp
from gurobipy import GRB
import itertools
# ------- DATA -------#
NbHouses = 5
WorkerNames = ["Joe", "Jim"]
TaskNames = [
"masonry",
"carpentry",
"plumbing",
"ceiling",
"roofing",
"painting",
"windows",
"facade",
"garden",
"moving",
]
Duration = [35, 15, 40, 15, 5, 10, 5, 10, 5, 5]
Worker = {
"masonry": "Joe",
"carpentry": "Joe",
"plumbing": "Jim",
"ceiling": "Jim",
"roofing": "Joe",
"painting": "Jim",
"windows": "Jim",
"facade": "Joe",
"garden": "Joe",
"moving": "Jim",
}
ReleaseDate = [0, 0, 151, 59, 243]
DueDate = [120, 212, 304, 181, 425]
Weight = [100, 100, 100, 200, 100]
Precedences = [
("masonry", "carpentry"),
("masonry", "plumbing"),
("masonry", "ceiling"),
("carpentry", "roofing"),
("ceiling", "painting"),
("roofing", "windows"),
("roofing", "facade"),
("plumbing", "facade"),
("roofing", "garden"),
("plumbing", "garden"),
("windows", "moving"),
("facade", "moving"),
("garden", "moving"),
("painting", "moving"),
]
Houses = range(NbHouses)
# -----------------------#
model = gp.Model("")
# for each house, create start and end decision variable
dv_house = {}
max_dueDate = max(DueDate)
for i in Houses:
dv_house[i] = (
model.addVar(lb=ReleaseDate[i], ub=max_dueDate, name="start_" + str(i)),
model.addVar(lb=ReleaseDate[i], ub=max_dueDate, name="end_" + str(i)),
)
# for each house, create task's start and end decision variables
# since we know the duration of each task,
# add a constraint : task_end - task_start = duration
TaskNames_ids = {}
itvs = {}
for h in Houses:
for i, t in enumerate(TaskNames):
_name = str(h) + "_" + str(t)
itvs[(h, t)] = (
model.addVar(lb=0, ub=max_dueDate, name="start_" + _name),
model.addVar(lb=0, ub=max_dueDate, name="end_" + _name),
)
model.addConstr(itvs[(h, t)][1] - itvs[(h, t)][0] == Duration[i])
TaskNames_ids[_name] = i
# ensure that tasks respect the precedences declared earlier
for h in Houses:
for p in Precedences:
model.addConstr(itvs[(h, p[1])][0] >= itvs[(h, p[0])][1])
# all tasks executed for a house should be within the confines
# of house start and end decision variable
for h in Houses:
model.addGenConstrMin(dv_house[h][0], [itvs[(h, t)][0] for t in TaskNames])
model.addGenConstrMax(dv_house[h][1], [itvs[(h, t)][1] for t in TaskNames])
# identify for each worker what tasks he/she is designated to perform
# for all houses
workers = {}
for w in WorkerNames:
workers[w] = [itvs[(h, t)] for h in Houses for t in TaskNames if Worker[t] == w]
# add no overlap constraint
# a worker cannot perform 2 tasks at the same time - same or different house
for w in WorkerNames:
lst = list(itertools.combinations(range(len(workers[w])), 2))
no_overlap_binary = model.addVars(len(lst), vtype="B")
for m, n in enumerate(lst):
one = workers[w][n[0]]
two = workers[w][n[1]]
model.addGenConstrIndicator(no_overlap_binary[m], 1, two[0] >= one[1])
model.addGenConstrIndicator(no_overlap_binary[m], 0, two[1] <= one[0])
# each worker while making a move from one house to another
# should adhere to transition time
# the transition time between task_house_1 and task_house_2 (say) is amount of time that must elapse
# between the end of task_house_1 and the beginning of task_house_2.
transitionTimes = {}
for i in Houses:
for j in Houses:
transitionTimes[i, j] = (i, j, int(abs(i - j)))
# sequence constraint
# NEED HELP HERE
# My initial thought was to enumerate all possible sequences of tasks
# for each house for a worker say, Joe
# tasks_joe = [masonry_house_0, masonry_house_1, ... garden_house_4]
# above is one possible sequence. So if Len of tasks_joe = 5
# we can have 120 possible sequences - not all will be valid since we have
# precedence constraints also. Then for each sequence, I will have a binary
# variable, and I will say if binary_varb_i = 1 => (all tasks)_i adhere
# to transition times. Sum_binary_varb == 1. So only one sequence
# will be valid for a worker, and that sequence will respect transition
# times between tasks performed at different houses
# But, number of such sequences (and constraints) will explode exponentially as number of tasks
# for a worker will increase. Can lazy constraints help here.
# Sorry, if above does not makes sense
# for each house calculate the time for completion
duration_house = {}
for h in Houses:
duration_house[h] = model.addVar(lb=0, ub=max_dueDate)
model.addConstr(duration_house[h] == dv_house[h][1] - dv_house[h][0])
# calculate number of days (if any) by which each house
# was completed post the due date
diff_house_end_date_due_date = {}
max_zero_house_end_date_due_date = {}
for h in Houses:
diff_house_end_date_due_date[h] = model.addVar(lb=0, ub=max_dueDate)
max_zero_house_end_date_due_date[h] = model.addVar(lb=0, ub=max_dueDate)
model.addConstr(diff_house_end_date_due_date[h] == dv_house[h][1] - DueDate[h])
model.addGenConstrMax(
max_zero_house_end_date_due_date[h], [0, diff_house_end_date_due_date[h]]
)
model.setObjective(
gp.quicksum(
Weight[h] * max_zero_house_end_date_due_date[h] + duration_house[h]
for h in Houses
),
sense=GRB.MINIMIZE,
)
model.optimize()
-
Hi Bhartendu,
Your no_overlap_binary variables are doing more than just ensuring no overlap, they are defining the sequence between two jobs. I think it would make sense to extend the definition of these variables to all jobs - not just ones for the same worker - and incorporate the transition times into these constraints so that the start time of a job is at least as great as the end time of previous job plus any transition time needed.
I'd also encourage you to strengthen your model with transitive constraints wherever possible. For example, in formulations with variables \(x_{ij}\) where the \(x_{ij}\) = 1 means job i precedes job j, you would typically have the following necessary constraints:
\[x_{ij} + x_{ji} = 1, \quad \quad \forall i,j\]
but also the following strengthening constraints
\[x_{ij} + x_{jk} \leq 1 + x_{ik}, \quad \quad \forall i,j,k\]
so that if i precedes j, and j precedes k, then i must precede k.
You can also strengthen by adding constraints for the house precedence constraints. Say (i,j) and (j,k) are in your house precedences, at the moment you are adding the equivalent of the following constraints (note that "end" variables aren't really necessary):
\[\begin{eqnarray}start(j) \geq start(i) + duration(i) \\
start(k) \geq start(j) + duration(j)\end{eqnarray}\]but you can also add the following to strengthen
\[start(k) \geq start(i) + duration(i) + duration(j)\]
which you can extend to an arbitrary number of precedence chainings for the same house.
I think you may find the following paper interesting which shows different approaches to modelling these sorts of scheduling problems Mixed Integer Programming Models for Job Shop
Scheduling: A Computational Analysis.- Riley
0 -
Thank you Riley. I was able to extend the no overlap constraint to include transition time constraints. It works.
I will also, incorporate your strengthening constraints, but even without it Gurobi finds an optimal solution in < 10 seconds in my local machine.
Purely from the perspective of increasing my understanding, could you help me with below (yet to go through the papers that you have shared)
1) Could you please help me how would these strengthening constraints help - would it help in finding LP relaxation solution faster, will help in getting a better initial best bound, etc.
2) For large scale problems, wouldn't classical MIP formulations lead to large number of decision variables, constraints - since with scheduling we have time indexes, disjunctions etc, which could potentially lead to loose LP relaxations. This is just my hypothesis, and I could be wrong also.Thanks again, your response is super-helpful.
Regards
Bhartendu
0 -
Hi Bhartendu,
If you're getting good results already then it may not be worth adding the strengthening constraints. Strong formulations don't necessarily solve the linear relaxation faster, in fact I'd expect that in general the linear relaxation solves slower due to the addition of constraints needed to make a strong formulation, but it will give a better dual bound, which is then used in more aggressive pruning of the branch and bound tree, and a more efficient search of the solution space. Weak models are often characterized by large MIP gaps which do not reduce very quickly and so optimality as a termination criteria becomes impractical.
As I think you alluded to there can be a trade off between size of the model and how tight a linear relaxation is. Time indexed models (for scheduling) for example are known to generally have relatively tight linear relaxations, however the size of the model grows quickly with the number of jobs and becomes impractical to solve to optimality. There are other aspects to consider when choosing a formulation too, such as how easily additional requirements can be incorporated (eg workers must have a break after a certain amount of time). The best formulation may also depend on the problem instances too - how many jobs, how long is their duration etc.
If you're interested in further discussion on strong vs weak formulations you can find a couple of relevant videos in our Tech Talks playlist.- Riley
0 -
Thank you Riley. Learnt something new from your note.
Regards
Bhartendu
0 -
Dear Bhartendu,
Thanks for your post. Is it possible for me to get the final correct code from you? If yes, I will leave my email address in the following comment. Thank you, and Riley, both of you are so great in this problem.
0 -
Please do not share e-mail addresses in public forums. A better alternative is to use a service like GitHub gists or Pastebin.com.
0 -
Thanks, Matthias, for the thoughtful advice. So, I would be more than grateful if Bhartendu you could share your GitHub repos or something else with me. Thank you again.
0 -
Please find below the code listing :
import gurobipy as gp
from gurobipy import GRB
import itertools
# ------- DATA -------#
NbHouses = 5
WorkerNames = ["Joe", "Jim"]
TaskNames = [
"masonry",
"carpentry",
"plumbing",
"ceiling",
"roofing",
"painting",
"windows",
"facade",
"garden",
"moving",
]
Duration = [35, 15, 40, 15, 5, 10, 5, 10, 5, 5]
Worker = {
"masonry": "Joe",
"carpentry": "Joe",
"plumbing": "Jim",
"ceiling": "Jim",
"roofing": "Joe",
"painting": "Jim",
"windows": "Jim",
"facade": "Joe",
"garden": "Joe",
"moving": "Jim",
}
ReleaseDate = [0, 0, 151, 59, 243]
DueDate = [120, 212, 304, 181, 425]
Weight = [100, 100, 100, 200, 100]
Precedences = [
("masonry", "carpentry"),
("masonry", "plumbing"),
("masonry", "ceiling"),
("carpentry", "roofing"),
("ceiling", "painting"),
("roofing", "windows"),
("roofing", "facade"),
("plumbing", "facade"),
("roofing", "garden"),
("plumbing", "garden"),
("windows", "moving"),
("facade", "moving"),
("garden", "moving"),
("painting", "moving"),
]
Houses = range(NbHouses)
# -----------------------#
model = gp.Model("")
# for each house, create start and end decision variable
dv_house = {}
max_dueDate = max(DueDate)
for i in Houses:
dv_house[i] = (
model.addVar(lb=ReleaseDate[i], ub=max_dueDate, name="start_" + str(i)),
model.addVar(lb=ReleaseDate[i], ub=max_dueDate, name="end_" + str(i)),
)
# for each house, create task's start and end decision variables
# since we know the duration of each task,
# add a constraint : task_end - task_start = duration
TaskNames_ids = {}
itvs = {}
for h in Houses:
for i, t in enumerate(TaskNames):
_name = str(h) + "_" + str(t)
itvs[(h, t)] = (
model.addVar(lb=0, ub=max_dueDate, name="start_" + _name),
model.addVar(lb=0, ub=max_dueDate, name="end_" + _name),
)
model.addConstr(itvs[(h, t)][1] - itvs[(h, t)][0] == Duration[i])
TaskNames_ids[_name] = i
# ensure that tasks respect the precedences declared earlier
for h in Houses:
for p in Precedences:
model.addConstr(itvs[(h, p[1])][0] >= itvs[(h, p[0])][1])
# all tasks executed for a house should be within the confines
# of house start and end decision variable
for h in Houses:
model.addGenConstrMin(dv_house[h][0], [itvs[(h, t)][0] for t in TaskNames])
model.addGenConstrMax(dv_house[h][1], [itvs[(h, t)][1] for t in TaskNames])
# identify for each worker what tasks he/she is designated to perform
# for all houses
workers = {}
for w in WorkerNames:
# workers[w] = [itvs[(h, t)] for h in Houses for t in TaskNames if Worker[t] == w]
workers[w] = {
(h, t): itvs[(h, t)] for h in Houses for t in TaskNames if Worker[t] == w
}
# each worker while making a move from one house to another
# should adhere to transition time
# the transition time between task_house_1 and task_house_2 (say) is amount of time that must elapse
# between the end of task_house_1 and the beginning of task_house_2.
transitionTimes = {}
for i in Houses:
for j in Houses:
transitionTimes[i, j] = (i, j, int(abs(i - j)))
# add no overlap constraint
# a worker cannot perform 2 tasks at the same time - same or different house
for w in WorkerNames:
lst = list(itertools.combinations(workers[w].keys(), 2))
no_overlap_binary = model.addVars(len(lst), vtype="B")
for m, n in enumerate(lst):
one = workers[w][n[0]]
two = workers[w][n[1]]
transition_time = transitionTimes[n[0][0], n[1][0]][2]
model.addGenConstrIndicator(
no_overlap_binary[m], 1, two[0] >= one[1] + transition_time
)
model.addGenConstrIndicator(
no_overlap_binary[m], 0, two[1] + transition_time <= one[0]
)
# sequence constraint
# workers_house_tasks = {}
# for w in WorkerNames:
# for h in Houses:
# for t in TaskNames:
# if Worker[t] == w:
# workers_house_tasks[(w, h, t)] = itvs[(h, t)]
# if w == "Joe":
# task_orders_1 = ["masonry", "carpentry", "roofing", "facade", "garden"]
# task_orders_2 = ["masonry", "carpentry", "roofing", "garden", "facade"]
# for each house calculate the time for completion
duration_house = {}
for h in Houses:
duration_house[h] = model.addVar(lb=0, ub=max_dueDate)
model.addConstr(duration_house[h] == dv_house[h][1] - dv_house[h][0])
# calculate number of days (if any) by which each house
# was completed post the due date
diff_house_end_date_due_date = {}
max_zero_house_end_date_due_date = {}
for h in Houses:
diff_house_end_date_due_date[h] = model.addVar(lb=0, ub=max_dueDate)
max_zero_house_end_date_due_date[h] = model.addVar(lb=0, ub=max_dueDate)
model.addConstr(diff_house_end_date_due_date[h] == dv_house[h][1] - DueDate[h])
model.addGenConstrMax(
max_zero_house_end_date_due_date[h], [0, diff_house_end_date_due_date[h]]
)
model.setObjective(
gp.quicksum(
(Weight[h] * max_zero_house_end_date_due_date[h]) + duration_house[h]
for h in Houses
),
sense=GRB.MINIMIZE,
)
model.optimize()0 -
Thank you, Bhartendu. Really appreciate.
0
Please sign in to leave a comment.
Comments
9 comments