•  Gurobi Staff

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

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

Regards

Bhartendu

•  Gurobi Staff

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

•   Thank you Riley. Learnt something new from your note.

Regards

Bhartendu

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

•  Gurobi Staff

Please do not share e-mail addresses in public forums. A better alternative is to use a service like GitHub gists or Pastebin.com.

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

•   Please find below the code listing :

import gurobipy as gpfrom gurobipy import GRBimport itertools# ------- DATA -------#NbHouses = 5WorkerNames = ["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 variabledv_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 = durationTaskNames_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)] - itvs[(h, t)] == Duration[i])        TaskNames_ids[_name] = i# ensure that tasks respect the precedences declared earlierfor h in Houses:    for p in Precedences:        model.addConstr(itvs[(h, p)] >= itvs[(h, p)])# all tasks executed for a house should be within the confines# of house start and end decision variablefor h in Houses:    model.addGenConstrMin(dv_house[h], [itvs[(h, t)] for t in TaskNames])    model.addGenConstrMax(dv_house[h], [itvs[(h, t)] for t in TaskNames])# identify for each worker what tasks he/she is designated to perform# for all housesworkers = {}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 housefor 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]        two = workers[w][n]        transition_time = transitionTimes[n, n]        model.addGenConstrIndicator(            no_overlap_binary[m], 1, two >= one + transition_time        )        model.addGenConstrIndicator(            no_overlap_binary[m], 0, two + transition_time <= one        )# 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 completionduration_house = {}for h in Houses:    duration_house[h] = model.addVar(lb=0, ub=max_dueDate)    model.addConstr(duration_house[h] == dv_house[h] - dv_house[h])# calculate number of days (if any) by which each house# was completed post the due datediff_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] - 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()
• Thank you, Bhartendu. Really appreciate.