Policy refinement with genetic algorithms for job-shop scheduling problems

Abstract

Evolutionary approach has been a well known and widely used method in solving scheduling problems besides other soft computing techniques. Genetic Algorithm (GA) is a popular evolutionary approach 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, job-shop scheduling (JSS) problem remains as challenging NP-hard combinatorial problem, which attracts researchers since its very beginning of its invention. 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 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. A policy refinement approach is proposed to optimise a sequence of Dispatching Rules (DRs) for a time-window 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. In other words, the set of dispatching rules are considered as policies for allocation of jobs to a number of resources (machines) and these policies are refined through evolution with use of GA for optimisation. The objective of this research is to refine scheduling policies to gain better results for solving job-shop scheduling problems. The criterion considered to be optimised in this research are makespan and mean tardiness in single and multi-objective context.