Genetic-based Constraint Programming for Resource Constrained Job Scheduling

Created by W.Langdon from gp-bibliography.bib Revision:1.8051

@InProceedings{nguyen:2024:GECCO,

• author = "Su Nguyen and Dhananjay Thiruvady and Yuan Sun and Mengjie Zhang",
• title = "Genetic-based Constraint Programming for Resource Constrained Job Scheduling",
• booktitle = "Proceedings of the 2024 Genetic and Evolutionary Computation Conference",
• year = "2024",
• editor = "Ting Hu and Aniko Ekart and Julia Handl and Xiaodong Li and Markus Wagner and Mario Garza-Fabre and Kate Smith-Miles and Richard Allmendinger and Ying Bi and Grant Dick and Amir H Gandomi and Marcella Scoczynski Ribeiro Martins and Hirad Assimi and Nadarajen Veerapen and Yuan Sun and Mario Andres Munyoz and Ahmed Kheiri and Nguyen Su and Dhananjay Thiruvady and Andy Song and Frank Neumann and Carla Silva",
• pages = "942--951",
• address = "Melbourne, Australia",
• series = "GECCO '24",
• month = "14-18 " # jul,
• organisation = "SIGEVO",
• publisher = "Association for Computing Machinery",
• publisher_address = "New York, NY, USA",
• keywords = "genetic algorithms, genetic programming, job scheduling, constraint programming",
• isbn13 = "979-8-4007-0494-9",
• DOI = "doi:10.1145/3638529.3654046",
• size = "10 pages",
• abstract = "Resource constrained job scheduling is a hard combinatorial optimisation problem that originates in the mining industry. Off-the-shelf solvers cannot solve this problem satisfactorily in reasonable time-frames, while other solution methods such as evolutionary computation methods and matheuristics cannot guarantee optimality and require low-level customisation and specialised heuristics to be effective. This paper addresses this gap by proposing a genetic programming algorithm to discover efficient search strategies of constraint programming for resource-constrained job scheduling. In the proposed algorithm, evolved programs represent variable selectors to be used in the search process of constraint programming, and their fitness is determined by the quality of solutions obtained by constraint programming for training instances. The novelties of this algorithm are (1) a new representation of variable selectors, (2) a new fitness evaluation scheme, and (3) a pre-selection mechanism. Tests with a large set of random and benchmark instances show that the evolved variable selectors can significantly improve the efficiency of constraining programming. Compared to highly customised metaheuristics and hybrid algorithms, evolved variable selectors can help constraint programming identify quality solutions faster and proving optimality is possible if sufficiently large run-times are allowed. The evolved variable selectors are especially helpful when solving instances with large numbers of machines.",
• notes = "GECCO-2024 GP A Recombination of the 33rd International Conference on Genetic Algorithms (ICGA) and the 29th Annual Genetic Programming Conference (GP)",

}

Genetic Programming entries for Su Nguyen Dhananjay Thiruvady Yuan Sun Mengjie Zhang

Citations