FJSP with Alternative Interval Variables

1. From Job Shop to Flexible Job Shop

Let's start by formalizing the difference between JSSP and FJSP.

• In the JSSP, an operation is rigidly tied to one specific machine.
• In the FJSP, an operation can be processed by one machine from a given set of alternatives. This is sometimes called "machine flexibility" or having "alternative resources."

This flexibility is common in modern manufacturing, where multi-purpose machines can perform various types of tasks. The decision is now two-fold:

1. Assignment: Which machine should process each operation?
2. Sequencing: In what order should operations be run on each machine?

A formal definition is crucial for modeling. The following paper provides a concise mathematical definition of the FJSP.

2. The Modeling Strategy: Optional and Alternative Intervals

So, how do we model this choice in CP? A simple interval variable for each operation is no longer sufficient, as its duration depends on the machine we choose.

The solution in modern CP solvers is to use a powerful two-level structure involving optional intervals and an alternative constraint.

First, let's understand the concept of an optional interval.

With optional intervals, our strategy for modeling an operation o in an FJSP becomes:

1. Create an abstract "master" interval (op_o): This represents the operation itself, without being tied to any specific machine. Its start, end, and duration are yet to be determined.
2. Create a set of "mode" intervals: For each eligible machine m for operation o, create an optional interval mode_o_m. This optional interval represents the concrete choice of running operation o on machine m. Its size is set to the specific processing time p_o,m.

Now, we need to link the master interval to its possible modes. This is done with the alternative global constraint.

The alternative(op_o, [mode_o_m1, mode_o_m2, ...]) constraint is the magic that ties everything together. It enforces two critical properties:

• If the master interval op_o is present in the solution, then exactly one of its optional mode intervals (mode_o_m1, mode_o_m2, etc.) must also be present. All other modes for that operation will be absent.
• The start and end times of the master interval op_o are synchronized with the chosen mode interval.

To see this explained, let's return to the tutorial.

3. Implementing the FJSP Model

Now we have all the components to extend our JSSP model to an FJSP model. We'll use the same structure as before (variables, constraints, objective), but we'll modify it to incorporate the alternative structure.

A complete, state-of-the-art model is presented in the paper we looked at earlier. We will analyze its structure, as it perfectly demonstrates the concepts we've discussed.

Let's summarize the key adjustments from our previous JSSP model:

1. Variables:
   • We now have two sets of interval variables:
     • ops: One interval for each operation (the "master").
     • modes: One optional interval for each valid operation-machine combination.
2. Constraints:
   • Precedence Constraints (endBeforeStart): These are applied to the ops (master) variables. This is clean and intuitive, as the precedence relationship between operations exists regardless of which machines are chosen.
   • Capacity Constraints (noOverlap): These are applied to the modes (optional) variables. For each machine m, a noOverlap constraint is placed on all modes that could potentially run on it. The solver ensures that the present modes on that machine do not overlap.
   • Alternative Constraints: For each operation, an alternative constraint is added to link its master ops variable to its set of modes variables. This enforces the machine selection.

To see this in a more familiar Python-based syntax, the CP Optimizer tutorial provides a concise implementation snippet that mirrors the structure of the OR-Tools code from our last lesson.

This two-level modeling pattern is a cornerstone of advanced scheduling with Constraint Programming. It cleanly separates the logical structure of the problem (precedences between abstract operations) from the resource allocation details (assigning operations to non-overlapping slots on specific machines).

Conclusion

In this lesson, we have made the crucial leap from the standard Job Shop to the more complex and practical Flexible Job Shop Problem. You have seen how Constraint Programming provides specialized tools to manage the added complexity of machine flexibility in a declarative and powerful way.

Key Takeaways:

• The FJSP extends the JSSP by allowing each operation to be processed on one of a set of alternative machines.
• CP models this choice using a two-level structure: an abstract interval for the operation and a set of optional intervals for each machine choice (or "mode").
• The alternative global constraint is the key that links the abstract operation to its modes, ensuring exactly one is chosen and synchronizing their start/end times.
• Precedence constraints are applied to the abstract operation intervals, while NoOverlap constraints are applied to the optional mode intervals for each machine.
• This approach cleanly decomposes the problem into an assignment component (handled by alternative) and a sequencing component (handled by NoOverlap).

Preview of the Next Lesson:

We have now seen how to model both JSSP and FJSP using Constraint Programming. But as you know from your research preparation, CP is not the only tool for optimization. Mixed-Integer Linear Programming (MILP) is another major paradigm. In our next lesson, we will compare the strengths and weaknesses of CP and MILP for modeling and solving scheduling problems. We will discuss how an FJSP would be formulated in MILP and contrast that with the CP model you learned today, giving you the critical perspective needed to select and justify the right tools for your thesis.