EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

2374. MILP formulations with a logarithmic number of binary variables for planning and scheduling

Invited abstract in session WD-49: Mathematical programming for machine scheduling, stream Lot Sizing, Lot Scheduling and Production Planning.

Wednesday, 14:30-16:00
Room: M1 (building: 101)

Authors (first author is the speaker)

1. Alain HAIT
Complex Systems Engineering, ISAE-SUPAERO University of Toulouse

Abstract

The way to represent the position of an activity on the time axis is at the heart of planning and scheduling models. A first distinction is done between continuous and discrete time formulations. This work focuses on discrete-time models that consist in choosing the start time of an activity among a discrete set of successive values. For this purpose, several time-indexed formulations have been proposed. They use as many binary variables as time steps on the horizon for each activity. The number of variables
could be significantly reduced using binary encoding to represent the set of time values, but the attempts to determine activity start times this way have generally leaded to models with poor relaxations. Vielma and Nemhauser have proposed formulations to model disjunctions with a logarithmic number of variables and constraints. They study the association with SOS2 variables in order to model piecewise linear functions, but their models are also suitable for time-indexed formulations in scheduling problems.

This work presents the adaptation of Vielma and Nemhauser’s formulation to time-indexed scheduling models. The comparison is done with classical time-indexed formulations through the Resource-Constrained Project Scheduling Problem (RCPSP). Experiments give the relaxation values for both formulations. An alternate formulation is proposed, with more constraints but experimentally competitive. Then, binary encoding is explored to improve the linear relaxation.

Keywords

Status: accepted

Back to the list of papers