Predicting the Optimal Period for Cyclic Hoist Scheduling Problems

N. Efthymiou, N. Yorke-Smith

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review


Since combinatorial scheduling problems are usually NP-hard, this paper investigates whether machine learning (ML) can accelerate exact solving of a problem instance. We adopt supervised learning on a corpus of problem instances, to acquire a function that predicts the optimal makespan for a given instance. The learned predictor is invariant to the instance size as it uses statistics of instance attributes. We provide this prediction to a solving algorithm in the form of bounds on the objective function. Specifically, this approach is applied to the well-studied Cyclic Hoist Scheduling Problem (CHSP). The goal for a CHSP instance is to find a feasible schedule for a hoist which moves objects between tanks with minimal cyclic period. Taking an existing Constraint Programming (CP) model for this problem, and an exact CP-SAT solver, we implement a Deep Neural Network, a Random Forest and a Gradient Boosting Tree in order to predict the optimal period p. Experimental results find that, first, ML models (in particular DNNs), can be good predictors of the optimal p; and, second, providing tight bounds for p around the predicted value to an exact solver significantly reduces the solving time without compromising the optimality of the solutions.
Original languageEnglish
Title of host publicationProceedings of the 20th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR'23)
EditorsAndre A. Cire
Number of pages16
ISBN (Print)978-3-031-33270-8
Publication statusPublished - 2023
EventCPAIOR 2023 - Nice, France
Duration: 29 May 20231 Jun 2023
Conference number: 20

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13884 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceCPAIOR 2023
Abbreviated titleCPAIOR 2023

Bibliographical note

Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.


Dive into the research topics of 'Predicting the Optimal Period for Cyclic Hoist Scheduling Problems'. Together they form a unique fingerprint.

Cite this