Refining scheduling policies with genetic algorithms

Aydin, Mehmet E.; Ogur, Emin; Aydin, Mehmet Emin

Abstract

Genetic Algorithms (GAs) are popular approaches in solving various complex real-world problems. However, it is required that a careful attention is to be paid to the contextual knowledge as well as the implementation of genetic material and operators. On the other hand, the job-shop scheduling (JSS) problem remains as challenging NP-hard combinatorial problem, which attracts researchers since it is invented. The dynamic version of job-shop is even more challenging due to its dynamically changing characteristics. Similar to other metaheuristic approaches, GA has not been so successful in solving this sort of problems due to instant decision making process needed in solving this type of problems. Heuristic procedures such as those so called Priority Rule or Dispatching Rules are more useful for this purpose, but, depending on the properties and purpose of use of each, the same performance is not expected from these instant decision making operators. In this paper, a policy refinement approach is proposed to optimise a sequence of Dispatching Rules (DRs) for a timewindow of scheduling process in which a GA algorithm evolves the sequences towards an optimum configuration. The preliminary results provided in this paper seem very encouraging.

• Presentation Conference Type: Conference Paper (published)
• Conference Name: GECCO 2013 - Proceedings of the 2013 Genetic and Evolutionary Computation Conference Companion
• Start Date: Jul 3, 2013
• End Date: Jul 6, 2013
• Publication Date: Aug 26, 2013
• Peer Reviewed: Peer Reviewed
• Pages: 1513-1518
• Book Title: Proceeding of the fifteenth annual conference companion on Genetic and evolutionary computation conference companion - GECCO '13 Companion
• DOI: https://doi.org/10.1145/2464576.2482730
• Keywords: dynamic job shop scheduling, hyperheuristics, genetic algorithms
• Public URL: https://uwe-repository.worktribe.com/output/929946
• Publisher URL: http://dx.doi.org/10.1145/2464576.2482730
• Additional Information: Title of Conference or Conference Proceedings : Proceedings of the 15th annual conference companion on Genetic and evolutionary computation