4.7 Article

Genetic programming with local search to evolve priority rules for scheduling jobs on a machine with time-varying capacity

Journal

SWARM AND EVOLUTIONARY COMPUTATION
Volume 66, Issue -, Pages -

Publisher

ELSEVIER
DOI: 10.1016/j.swevo.2021.100944

Keywords

One machine scheduling; Priority rules; Local search; Genetic programming; Memetic algorithm

Funding

  1. Spanish Government [TIN2016-79190-R, PID2019106263RBI00]
  2. Principality of Asturias [IDI/2018/000176, FPI17/BES201708203]

Ask authors/readers for more resources

The proposed Memetic Algorithm combines Genetic Program and Local Search algorithm to evolve priority rules for scheduling a set of jobs on a machine with time-varying capacity, with specifically designed neighborhood structures for the problem. Experimental results demonstrate that proper selection and combination of neighborhood structures allow the Memetic Algorithm to outperform previous approaches to the same problem.
Priority rules combined with schedule generation schemes are a usual approach to online scheduling. These rules are commonly designed by experts on the problem domain. However, some automatic method may be better as it could capture some characteristics of the problem that are not evident to the human eye. Furthermore, automatic methods could devise priority rules adapted to particular sets of instances of the problem at hand. In this paper we propose a Memetic Algorithm, which combines a Genetic Program and a Local Search algorithm, to evolve priority rules for the problem of scheduling a set of jobs on a machine with time-varying capacity. We propose a number of neighbourhood structures that are specifically designed to this problem. These structures were analyzed theoretically and also experimentally on the version of the problem with tardiness minimization, which provided interesting insights on this problem. The results of the experimental study show that a proper selection and combination of neighbourhood structures allows the Memetic Algorithm to outperform previous approaches to the same problem.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.7
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available