1641. Batch scheduling problems using interval and set decision variables with Hexaly
Invited abstract in session WA-12: Batch scheduling, stream Scheduling and Project Management.
Wednesday, 8:30-10:00Room: Clarendon SR 1.02
Authors (first author is the speaker)
| 1. | Agathe L'HERMITE
|
| Hexaly | |
| 2. | Léa Blaise
|
| Hexaly |
Abstract
Hexaly is a “model and run” mathematical optimization solver based on various exact and heuristic methods. In this talk, we will focus on how its modelling formalism can be used to express batch scheduling problems using interval and set decision variables. Batch scheduling problems are scheduling problems where tasks can be grouped into batches and made synchronously. These models are very intuitive and compact, thanks to high-level decision variables and set-based operators. A set variable represents a subset of tasks using their indices, representing a batch’s content. Interval variables will represent the position in time of the batches.
The algorithms implemented within the solver take advantage of these compact formulations based on interval and set decision variables. For example, the solver's local search component comprises various local neighborhoods working on set decision variables. We adapted these existing moves to batch scheduling problems by making them efficiently work on the interval variables as well: whenever the value of a set variable is changed, the value of the interval variable corresponding to the same batch is changed accordingly. These algorithms, as well as other methods implemented, enable Hexaly to achieve very good performances on batch scheduling problems: an average of 4.5% in one minute with up to 100.000 tasks.
Keywords
- Scheduling
- Metaheuristics
- Modeling Systems and Languages
Status: accepted
Back to the list of papers