A Genetic Programming Framework for Heuristic Generation for the Job-Shop Scheduling Problem

Autor:	José Carlos Ortiz-Bayliss, Iván Amaya, Xavier Sánchez-Díaz, Erick Lara-Cárdenas, Jorge M. Cruz-Duarte
Rok vydání:	2020
Předmět:	Set (abstract data type) Mathematical optimization Job shop scheduling Computer science Heuristic (computer science) Scheduling (production processes) Genetic programming Job shop scheduling problem Heuristics Empirical evidence
Zdroj:	Advances in Soft Computing ISBN: 9783030608835 MICAI (1)
DOI:	10.1007/978-3-030-60884-2_21
Popis:	The Job-Shop Scheduling problem is a combinatorial optimization problem present in many real-world applications. It has been tackled with a colorful palette of techniques from different paradigms. Particularly, hyper-heuristics have attracted the attention of researchers due to their promising results in various optimization scenarios, including job-shop scheduling. In this study, we describe a Genetic-Programming-based Hyper-heuristic approach for automatically producing heuristics (dispatching rules) when solving such a problem. To do so, we consider a set of features that characterize the jobs within a scheduling instance. By using these features and a set of mathematical functions that create interactions between such features, we facilitate the construction of new heuristics. We present empirical evidence that heuristics produced by our approach are competitive. This conclusion arises from comparing the makespan of schedules obtained from our proposed method against those of some standard heuristics, over a set of synthetic Job-Shop Scheduling problem instances.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::3a2f55e38f0f23ee4444e8dd2a6271db https://doi.org/10.1007/978-3-030-60884-2_21 Zobrazit plný text záznamu