1456. Fast bounds in Hexaly based on single-machine scheduling problems
Invited abstract in session MB-7: Advances in scheduling: From theory to practice, stream Scheduling and Project Management.
Monday, 10:30-12:00Room: Clarendon GR.01
Authors (first author is the speaker)
| 1. | Léa Petit-Jean Genat
|
| Hexaly |
Abstract
Given a scheduling problem expressed in the Hexaly framework (a model and run mathematical optimisation solver based on various exact and heuristic methods), we aim to quickly compute a reasonable lower bound within a time that is negligible compared to the total solving time of the problem. Our approach employs classical scheduling algorithms with logarithmic-linear complexity on single-machine subproblems to address this challenge.
We handle various objective functions, such as the (weighted) number of late jobs, weighted completion times, and maximum lateness, by leveraging well-known algorithms like Moore-Hodgson, Potts-Wassenhove, Smith, and Jackson. The main idea lies in detecting these expressions and exploiting the precedence constraints of the scheduling problem.
The precedence constraints allow us to distribute due dates or weights across machines, enabling more tasks to be considered in the lower bound computation. This distribution allows us to compute lower bound values for each machine and ultimately select the most promising one.
Experimental results on job-shop scheduling problems demonstrate significant improvements across different objective types. We achieved mean gap reductions of up to 31%, validating the effectiveness of our approach in quickly providing reasonable lower bounds.
Keywords
- Scheduling
- Algorithms
- Industrial Optimization
Status: accepted
Back to the list of papers