1378. A Novel Time-Indexed Formulation for the Single Machine Scheduling Problem with Sequence-Dependent Setup Times
Invited abstract in session MC-7: Mathematical Programming in Scheduling, stream Scheduling and Project Management.
Monday, 12:30-14:00Room: Clarendon GR.01
Authors (first author is the speaker)
| 1. | Wonwoo Cho
|
| Industrial engineering, Seoul National University | |
| 2. | Kyungsik Lee
|
| Industrial Engineering, Seoul National University |
Abstract
In this talk, we address time-indexed formulations for the single machine scheduling problem with sequence-dependent setup times. In these formulations, each decision variable is associated with a job-time pair, indicating whether the job starts at that time. When sequence-depenedent setup times are introduced, the ideal formulation for the machine’s capacity constraint, ensuring that the machine performs at most one processing or setup at a time, becomes unavailable. A naive formulation for the capacity constraint may either significantly weaken its linear programming (LP) relaxation or increase the number of constraints, severely hindering the model’s solvability with commercial solvers. To address this, we propose a novel time-indexed formulation that enforces the capacity constraint through clique inequalities. The cliques are constructed via a two-phase algorithm. The first phase aims to reduce the number of cliques while ensuring model validity. In the second phase, cliques are constructed by solving an LP and then maximalized. Computational results demonstrate that the proposed formulation outperforms existing time-indexed formulations in terms of the number of constraints, computation time for solving the LP relaxation, and the LP relaxation bound.
Keywords
- Scheduling
- Programming, Integer
Status: accepted
Back to the list of papers