Evolution of scheduling heuristics with genetic programming

Info: This project deals with evolving scheduling heuristics in the form of a scheduling rule (priority scheduling paradigm). This technique can be used to discover new heuristics that are efficient for a given scheduling environment and arbitrary scheduling criteria. This is especially useful in cases where no adequate heuristic exists for a certain combination of environment and criteria.

Documentation:

• Scheduling environments and heuristics

• Test cases design

• Test cases for unrelated machines

• Test cases for unrelated machines in static conditions

Papers:

• Evolution of Vehicle Routing Problem Heuristics with Genetic Programming
  Gulić, Matija; Jakobović, Domagoj, MIPRO 2013 Opatija : IEEE, 2013.

• Evolving Priority Scheduling Heuristics with Genetic Programming
  D. Jakobovic, K. Marasovic, Applied soft computing. 12 (2012)

• Evolutionary Algorithms for the Resource Constrained Scheduling Problem
  Toni Frankola, Marin Golub, Domagoj Jakobovic (2008), Information Technology Interfaces (ITI) 2008
  Abstract: This paper investigates the use of evolutionary algorithms for solving resource constrained scheduling problem. This problem is in the class of NP complete problems. It involves finding optimal sequence of activities with given resource constraints. Evolutionary algorithms used in this paper are genetic algorithms and genetic programming, for which an adequate scheduling mechanism is defined. Presented solutions are compared with existing heuristic or optimal results.

• Genetic Programming Heuristics for Multiple Machine Scheduling
  D. Jakobović, L. Jelenkovic, L. Budin, (2007) EuroGP 2007, Lecture Notes in Computer Science 4445, pp. 321-330.
  Abstract: In this paper we present a method for creating scheduling heuristics for parallel proportional machine scheduling environment and arbitrary performance criteria. Genetic programming is used to synthesize the priority function which, coupled with an appropriate meta-algorithm for a given environment, forms the priority scheduling heuristic. We show that the procedures derived in this way can perform similarly or better than existing algorithms. Additionally, this approach may be particularly useful for those combinations of scheduling environment and criteria for which there are no adequate scheduling algorithms.

• Dynamic Scheduling with Genetic Programming
  D. Jakobović, L. Budin, (2006) EuroGP 2006, Lecture Notes in Computer Science 3905, pp. 73-84
  (Dynamic Scheduling with Genetic Programming: presentation in PDF)
  Abstract: This paper investigates the use of genetic programming in automatized synthesis of scheduling heuristics. The applied scheduling technique is priority scheduling, where the next state of the system is determined based on priority values of certain system elements. The evolved solutions are compared with existing scheduling heuristics for single machine dynamic problem and job shop scheduling with bottleneck estimation.