OR-tools: Constraining interval variables search procedure to be more compact

Question

I have been trying to modelize the job-shop problem with the following setup:

1. Variables & constraints: For each task:

• job-level variables: start (NewIntVar), end(NewIntVar), interval(NewIntervalVar)
• tardiness = max(task_end - task_due_date, 0)
• precedence constraint:

for task_before, task_after in tasks_precedence:
    model.Add(start[task_after] >= end[task_before])

For each machine:

• No overlap for all "intervals" that could be produced on the machine

for machine in machines:
    model.AddNoOverlap([intervals[machine, task] for task in machine_tasks[machine])

2. Objective: Minimising the tardiness for each job

model.Minimize(sum(tasks_tardiness))

However, when I compute the results within a given time-limit and no optimality is proven yet, some of the interval are very poorly positioned.

For instance: Schedule is not compact and the last task (red block) is very far from its due date. While it meets all of the specified constraint... It still does not make sense to place the task at this position.

Any idea on how to improve the search procedure and enables the model to infer better solutions ?

enter image description here

Answer 1

My intuition is to solve in two phases.

Solve your current model. Record the order of the intervals on each machine. Then create a second model, where you fix the order of intervals (no need for the no_overlap constraint), and change the objective to maximize compactness.