Determining the Characteristic of Difficult Job Shop Scheduling Instances for a Heuristic Solution Method

Many heuristic methods have been proposed for the job-shop scheduling problem. Different solution methodologies outperform other depending on the particular problem instance under consideration. Therefore, one is interested in knowing how the instances differ in structure and determine when a particular heuristic solution is likely to fail and explore in further detail the causes. In order to achievethis, we seek to characterise features for different difficulties. Preliminary experiments show there are different significant features that distinguish between easy and hard JSSP problem, and that they vary throughout the scheduling process. The insight attained by investigating the relationship between problem structure and heuristic performance can undoubtedly lead to better heuristic design that is tailored to the data distribution under consideration.

Citation

@incollection{InRu12,
  year      = {2012},
  isbn      = {978-3-642-34412-1},
  booktitle = {Learning and Intelligent Optimization},
  series    = {Lecture Notes in Computer Science},
  editor    = {Hamadi, Youssef and Schoenauer, Marc},
  doi       = {10.1007/978-3-642-34413-8_36},
  title     = {Determining the Characteristic of Difficult Job Shop Scheduling Instances 
              for a Heuristic Solution Method},
  url       = {http://dx.doi.org/10.1007/978-3-642-34413-8_36},
  publisher = {Springer Berlin Heidelberg},
  author    = {Ingimundardottir, Helga and Runarsson, Thomas Philip},
  pages     = {408-412},
  language  = {English}
}