Single Machine Scheduling as an MILP

1. Why Use Mathematical Programming?

You might wonder why we need a complex tool like MILP when we have simple rules like SPT and EDD. The introduction of the paper "solving the single-machine sequencing problem" by Kenneth Baker provides an excellent rationale.

In academic research, specialized algorithms are often developed for specific, clean-cut problems. However, in practice—and particularly in thesis research that aims to model real-world systems—problems rarely fit these clean molds. You might need to consider:

• Sequence-dependent setup times
• Machine availability constraints (e.g., maintenance)
• Release dates and deadlines simultaneously
• Multiple, competing objectives

A major advantage of a mathematical programming approach is its flexibility. Instead of designing a new algorithm from scratch for every new constraint, you can often simply add new variables or constraints to an existing model. For problems of small to moderate size, this is an incredibly effective approach.

2. The Core of the Formulation: Modeling a Sequence

To build an MILP, we need three components:

1. Decision Variables: Variables that represent the decisions we need to make. In scheduling, the primary decision is the sequence of jobs.
2. Objective Function: A linear expression of our decision variables that quantifies the goal (e.g., minimizing total tardiness).
3. Constraints: A set of linear inequalities or equations that define the rules of the problem (e.g., a machine can only process one job at a time).

The main challenge is representing the sequence using variables. There are several ways to do this, each leading to a different model formulation. The following reading introduces several key approaches.

3. Deconstructing the Disjunctive Formulation

The Disjunctive (DJ) formulation, based on precedence variables, is one of the most important and extensible models in scheduling. Let's break it down for the 1 | | ΣT_j problem.

Variables:

• Binary precedence variables: $y_{ij}=1$ if job $i$ precedes job $j$ at some point in the sequence, and $0$ otherwise. These are defined for all pairs of jobs $(i,j)$.
• Continuous start time variables: $s_j\ge 0$ is the time at which job $j$ begins processing.
• Continuous tardiness variables: $t_j\ge 0$ is the tardiness of job $j$.

Objective Function:
Our goal is to minimize the sum of tardiness for all jobs.
$\text{Minimize }{\sum }_{j=1}^n{t}_j$

Constraints:

1. Tardiness Calculation: For each job $j$, we link its start time, processing time ($p_j$), and due date ($d_j$) to its tardiness $t_j$. The completion time of job $j$ is $s_j+p_j$.
   $s_j+p_j-d_j\le t_j\forall j$
   Since we are minimizing $\sum t_j$ and $t_j$ must be non-negative, the solver will ensure that $t_j$ takes the smallest possible value, which is $\max (0,s_j+p_j-d_j)$.

2. Disjunctive Sequencing Constraints: This is the heart of the model. For any two jobs, $i$ and $j$, one must finish before the other one starts. This "either-or" relationship is called a disjunction.

   • Either job $i$ comes before job $j$: $s_i+p_i\le s_j$
   • Or job $j$ comes before job $i$: $s_j+p_j\le s_i$

   We use the binary variable $y_{ij}$ and a large constant $M$ (the "big M") to model this. For every pair of jobs $(i,j)$ with $i<j$:
   $s_i+p_i\le s_j+M(1-y_{ij})$
   $s_j+p_j\le s_i+M\cdot y_{ij}$

   Let's see how this works:

   • If the solver sets $y_{ij}=1$ (meaning $i$ precedes $j$):
     • The first constraint becomes $s_i+p_i\le s_j$, which correctly enforces that $j$ starts after $i$ finishes.
     • The second constraint becomes $s_j+p_j\le s_i+M$. Since $M$ is a very large number, this constraint becomes redundant and non-restrictive.
   • If the solver sets $y_{ij}=0$ (meaning $j$ precedes $i$):
     • The first constraint becomes $s_i+p_i\le s_j+M$, which is non-restrictive.
     • The second constraint becomes $s_j+p_j\le s_i$, correctly enforcing that $i$ starts after $j$ finishes.

This "big M" technique is a standard method for converting logical conditions into linear constraints in MILP.

4. Extending the Model: Handling Complexity

The true power of this MILP formulation is its extensibility. Let's see how we can adapt the basic disjunctive model to handle a more complex feature that is relevant to your thesis: sequence-dependent setup times.

A different paper provides a clear example of this. It models a problem that includes not only sequence-dependent setup times ($s_{ij}$, the setup time for job $j$ if it follows job $i$), but also a variable maintenance task.

As you saw in the reading, modifying the core disjunctive constraint is straightforward. The original constraint for job i followed by j was:
$s_i+p_i\le s_j$

To include a sequence-dependent setup time $s_{ij}$, we simply add it to the right-hand side of the completion time of job $i$. In the notation of the second paper (where I_j is the start time and C_i is the completion time):
$I_j\ge C_i+s_{ij}$
This is captured in constraint (21) of their model: $I_j\ge C_i+s_{ij}-M(1-Y_{ij})$. This is a slightly different but equivalent big-M formulation that enforces that if $Y_{ij}=1$, the start time of $j$ must be after the completion of $i$ plus the required setup.

This simple modification demonstrates the modularity of MILP models. Adding this complexity to a rule-based algorithm like SPT or EDD would require a completely new theoretical development, but in an MILP, it's often just a matter of adjusting a few constraints.

Conclusion

This lesson marks a significant step from specific algorithms to general-purpose modeling. For the complex scheduling problems you'll face in your thesis, building and solving mathematical models is an indispensable skill.

Key Takeaways:

• MILP offers a flexible and general framework for solving scheduling problems, especially those with complex side constraints that defy simple rules.
• The core of a scheduling MILP is modeling the sequence. The disjunctive formulation using precedence variables ($y_{ij}$) and "big M" constraints is a fundamental and widely used technique.
• The power of this approach lies in its extensibility. We saw how a basic model for total tardiness can be adapted to include features like sequence-dependent setup times by modifying the core constraints.

Preview of the Next Lesson:
We've now seen two very different ways to solve single-machine problems: efficient, optimal rules (for simple cases) and general, powerful MILP models (for complex cases). This distinction hints at a deep concept in computer science: the difference between "easy" and "hard" problems. In our next lesson, we will formally analyze the complexity of single machine problems with different objectives, introducing you to the concepts of P and NP-hardness, which explain why we need tools like MILP for most scheduling problems.