Supervised Learning Linear Priority Dispatch Rules for Job-Shop Scheduling

This paper introduces a framework in which dispatching rules for job-shop scheduling problems are discovered by analysing the characteristics of optimal solutions. Training data is created via randomly generated job-shop problem instances and their corresponding optimal solution. Linear classification is applied in order to identify good choices from worse ones, at each dispatching time step, in a supervised learning fashion. The method is purely data-driven, thus less problem specific insights are needed from the human heuristic algorithm designer. Experimental studies show that the learned linear priority dispatching rules outperforms common single priority dispatching rules, with respect to minimum makespan.

Citation

@incollection{InRu11a,
  year      = {2011},
  isbn      = {978-3-642-25565-6},
  booktitle = {Learning and Intelligent Optimization},
  volume    = {6683},
  series    = {Lecture Notes in Computer Science},
  editor    = {Coello, Carlos A. Coello},
  doi       = {10.1007/978-3-642-25566-3_20},
  title     = {Supervised Learning Linear Priority Dispatch Rules for Job-Shop Scheduling},
  url       = {http://dx.doi.org/10.1007/978-3-642-25566-3_20},
  publisher = {Springer Berlin Heidelberg},
  author    = {Ingimundardottir, Helga and Runarsson, Thomas Philip},
  pages     = {263-277},
  language  = {English}
}