Automated Design of Multipass Heuristics for Resource-Constrained Job Scheduling With Self-Competitive Genetic Programming

Resource constraint job scheduling is an important combinatorial optimization problem with many practical applications. This problem aims at determining a schedule for executing jobs on machines satisfying several constraints (e.g., precedence and resource constraints) given a shared central resourc...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on cybernetics 2022-09, Vol.52 (9), p.8603-8616
Main Authors: Nguyen, Su, Thiruvady, Dhananjay, Zhang, Mengjie, Alahakoon, Damminda
Format: Article
Language:English
Subjects:
Algorithms
Combinatorial analysis
Constraints
Dispatching
Genetic algorithms
Genetic programming (GP)
Heuristic
Heuristic algorithms
Heuristic methods
heuristics
Job shop scheduling
Learning systems
Optimization
Resource scheduling
Scalability
Schedules
scheduling
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Resource constraint job scheduling is an important combinatorial optimization problem with many practical applications. This problem aims at determining a schedule for executing jobs on machines satisfying several constraints (e.g., precedence and resource constraints) given a shared central resource while minimizing the tardiness of the jobs. Due to the complexity of the problem, several exact, heuristic, and hybrid methods have been attempted. Despite their success, scalability is still a major issue of the existing methods. In this study, we develop a new genetic programming algorithm for resource constraint job scheduling to overcome or alleviate the scalability issue. The goal of the proposed algorithm is to evolve effective and efficient multipass heuristics by a surrogate-assisted learning mechanism and self-competitive genetic operations. The experiments show that the evolved multipass heuristics are very effective when tested with a large dataset. Moreover, the algorithm scales very well as excellent solutions are found for even the largest problem instances, outperforming existing metaheuristic and hybrid methods.
ISSN:2168-2267
2168-2275
DOI:10.1109/TCYB.2021.3062799