## Abstract

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 language | English |
---|---|

Title of host publication | Proceedings of the 20th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR'23) |

Editors | Andre A. Cire |

Publisher | Springer |

Pages | 238-253 |

Number of pages | 16 |

ISBN (Print) | 978-3-031-33270-8 |

DOIs | |

Publication status | Published - 2023 |

Event | CPAIOR 2023 - Nice, France Duration: 29 May 2023 → 1 Jun 2023 Conference number: 20 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 13884 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | CPAIOR 2023 |
---|---|

Abbreviated title | CPAIOR 2023 |

Country/Territory | France |

City | Nice |

Period | 29/05/23 → 1/06/23 |