EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

1393. Disjunctive scheduling using interval decision variables with Hexaly Optimizer

Invited abstract in session TC-60: Advanced heuristics for machine scheduling, stream Project Management and Scheduling.

Tuesday, 12:30-14:00
Room: S09 (building: 101)

Authors (first author is the speaker)

1. Léa Blaise
Hexaly

Abstract

Hexaly Optimizer, formerly known as LocalSolver, is a "model and run" mathematical optimization solver based on various exact and heuristic methods. The presentation will introduce the different components of Hexaly Optimizer's local search through disjunctive scheduling problems.
We will first show how its modeling formalism can be used to express various academic and industrial scheduling problems using interval and list decision variables. These models are very compact, which enables the solver to handle even large-scale problems.
Detecting non-overlap constraints in the model provides the solver with valuable information, which can be exploited through various scheduling-specific movements implemented in Hexaly Optimizer's local search. However, due to the tightness of precedence and non-overlap constraints in good solutions to disjunctive scheduling problems (Job Shop Scheduling Problem, for example), such a small-neighborhood search alone struggles to obtain good performance.
Hexaly Optimizer overcomes this issue by reinforcing its local search component with a solution repair algorithm based on constraint propagation. When a move renders the solution infeasible, it is gradually repaired, one constraint at a time, by heuristically shifting the variables just enough to repair. To extend the local transformation rather than cancel it, and to ensure the procedure is fast, we impose never to backtrack on a previous decision to increase or decrease a variable's value.

Keywords

Status: accepted

Back to the list of papers