Job Shop Scheduling with Interval Variables

1. Beyond Integer Variables: The Need for Scheduling Abstractions

When we formulated scheduling problems as MILP models, we primarily used continuous or integer variables to represent points in time (e.g., start_time, completion_time). While this is a valid approach, it forces us to manually express all temporal logic. For example, a simple "no overlap" constraint between two operations, $i$ and $j$, on the same machine requires a disjunction and big-M formulation:

This becomes very cumbersome as the number of operations grows. Constraint Programming for scheduling introduces higher-level modeling objects that capture the essence of time and resources more directly.

To understand this motivation, let's look at a short presentation from Philippe Laborie, a key architect of IBM's CP Optimizer.

This brings us to the central building block of CP scheduling models: the interval variable.

2. The Interval Variable: A Richer Representation of an Operation

Instead of representing an operation with separate variables for its start and end times, CP combines them into a single, powerful object: an interval variable.

An interval variable represents an unknown interval of time. Its value in a solution is a specific time range [start, end). The solver's job is to determine these values. An interval variable encapsulates several key properties:

• Start: The start time of the interval.
• End: The end time of the interval.
• Length: The duration of the interval (end - start).
• Size: The required processing time. In basic cases, length equals size. We will see later that this can differ if, for example, work is not continuous (e.g., pausing over a weekend).

Crucially, an interval variable can also be optional. An optional interval has an additional state: "absent." This means the solver can decide whether to include the operation in the schedule at all. This feature is immensely powerful for modeling alternatives, which is a cornerstone of the Flexible Job Shop Problem (FJSP) you are focusing on for your thesis.

Let's ground these ideas in a more formal definition.

The image below provides a great visual summary of these concepts.

3. Temporal Constraints: Weaving Intervals Together

Once we model each operation as an interval variable, we need to define the rules that connect them. In CP, these rules are expressed using temporal constraints and global constraints.

Precedence Constraints

In a job shop, operations within the same job have a strict technological order. If operation $O_{i,j}$ must be completed before operation $O_{i,j+1}$ can begin, we can express this with a simple precedence constraint. The most common one is endBeforeStart.

endBeforeStart(a, b): This constraint ensures that if both interval variables a and b are present in the solution, the end of a must be less than or equal to the start of b.
$\text{end}(a)\le \text{start}(b)$

Resource Constraints

The defining challenge of a job shop is that multiple jobs compete for the same set of machines. A machine is a unary resource (or disjunctive resource), meaning it can only process one operation at a time.

Instead of writing pairwise disjunctions for all operations on a machine, CP offers a powerful global constraint called noOverlap.

noOverlap([a, b, c, ...]): This constraint takes a set of interval variables and ensures that no two present intervals in the set overlap in time.

This is a major advantage of CP modeling. The noOverlap constraint encapsulates the complex disjunctive logic internally. The solver has highly efficient, specialized algorithms (called "propagation") to reason about this constraint, making it far more effective than a generic MILP solver handling a large number of binary variables and disjunctions.

4. Constructing a Job Shop Model

Let's now assemble these pieces to model a standard job shop scheduling problem.

Problem Definition:

• A set of jobs $J$.
• A set of machines $M$.
• Each job $i\in J$ consists of a sequence of operations $(O_{i,1},O_{i,2},\dots )$.
• Each operation $O_{i,j}$ has a specified processing time $p_{i,j}$ and must be processed on a specific machine $m_{i,j}$.
• Objective: Minimize the makespan ($C_{max}$), which is the completion time of the last operation.

CP Model Formulation:

1. Variables:

   • For each operation $O_{i,j}$, create an interval variable op[i][j] with size = p_ij.
   • Create an integer variable Cmax to represent the makespan.

2. Constraints:

   • Precedence Constraints: For each job $i$ and for each adjacent pair of operations $(O_{i,j},O_{i,j+1})$, add a precedence constraint:
     endBeforeStart(op[i][j], op[i][j+1])
   • Resource (No-Overlap) Constraints: For each machine $k\in M$, create one noOverlap constraint. This constraint includes all interval variables corresponding to operations that require machine $k$:
     noOverlap(all (i,j) such that m_ij = k: op[i][j])
   • Makespan Definition: The makespan must be greater than or equal to the end time of every operation. A simpler way is to constrain it by the end times of only the last operation of each job:
     Cmax >= endOf(op[i][last]) for all jobs $i$.

3. Objective:

   • minimize(Cmax)

This structure is elegant and directly maps the physical problem to the model's components. To see what this looks like in a concrete modeling language (OPL), let's examine a provided model for a flow shop, which is very similar.

In the flow-shop model, the noOverlap constraint at line 19 is looped over for each machine j, and for that machine, it gathers all operations (all(i in 1..n) op[i][j]). This is exactly the logic we need for a job shop as well.

Conclusion

In this lesson, we have taken a significant step towards building practical scheduling models using Constraint Programming. We moved beyond generic integer variables and embraced the specialized, powerful abstractions that make CP so well-suited for scheduling.

Key Takeaways:

• Interval variables are the primary building blocks for modeling operations in time. They encapsulate start, end, and duration.
• Optional intervals allow the solver to decide whether an activity should be part of the final schedule, a key feature for modeling problems with alternatives like FJSP.
• Temporal constraints like endBeforeStart define the required sequencing of operations within a job.
• The noOverlap global constraint provides an elegant and efficient way to model unary resources (like machines), ensuring that no two operations on the same machine run concurrently.

Preview of the Next Lesson:

Now that we have a solid grasp of modeling a standard job shop, we'll expand our toolkit. In the next lesson, we will explore other powerful global constraints, such as the Cumulative constraint for resources that can handle multiple tasks at once (e.g., a team of workers). We will also formally see how to model the Flexible Job Shop Problem by using the alternative constraint, which allows an operation to choose between several optional intervals representing its execution on different machines. This will bring us one step closer to modeling the full complexity of your thesis problem.