1294. Compact set-based modeling for scheduling problems with Hexaly
Invited abstract in session TD-43: Toolboxes & APIs, stream Software for Optimization.
Tuesday, 14:30-16:00Room: Newlyn GR.07
Authors (first author is the speaker)
| 1. | Léa Blaise
|
| Hexaly |
Abstract
Hexaly is a model & run global optimization solver based on exact and heuristic techniques. In this talk, we will focus on its performance on scheduling problems in general (problems with precedence constraints and disjunctive or cumulative resources, minimizing makespan, weighted sum of tardiness, etc.). Hexaly's nonlinear and set-based modeling formalism makes it very straightforward to express many academic and industrial scheduling problems, using only generic operators. These models combine two kinds of decision variables: intervals and lists. On the one hand, we use interval decisions to model the time span of the tasks. Besides, we use list decisions (decisions whose values are permutations) to represent the order in which the tasks are scheduled on each disjunctive resource.
These interval and list-based models have the advantage of being compact, enabling the solver to handle large-scale problems. Indeed, the algorithms implemented within Hexaly exploit this modeling and enable it to achieve very good performance on various scheduling problems: less than 2% optimality gap in one minute with up to 2,000 tasks on classical problems such as the Job Shop, the Flexible Job Shop, the Open Shop, or the Resource-Constrained Project Scheduling Problems. We will also show that models written in Hexaly's set-based formalism are more compact than their equivalents in the linear or constraint programming formalisms used by other classical solvers, such as Gurobi or CP Optimizer.
Keywords
- Scheduling
- Software
Status: accepted
Back to the list of papers