RI Homepage Carnegie Mellon Homepage RI Homepage

The Robotics Institute

Carnegie Mellon Robotics Institute

Iterative Flattening Search for the Flexible Job Shop Scheduling Problem

Angelo Oddi, Riccardo Rasconi, Amedeo Cesta, and Stephen Smith
Proceedings 22nd International Joint Conference on Artificial Intelligence, Barcelona, Spain, July, 2011. , July, 2011.


Download
  • Adobe portable document format (pdf) (270KB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract
This paper presents a meta-heuristic algorithm for solving the Flexible Job Shop Scheduling Problem (FJSSP). This strategy, known as Iterative Flatten-ing Search (IFS), iteratively applies a relaxation-step, in which a subset of scheduling decisions are randomly retracted from the current solution; and a solving-step, in which a new solution is incremen-tally recomputed from this partial schedule. This work contributes two separate results: (1) it pro-poses a constraint-based procedure extending an existing approach previously used for classical Job Shop Scheduling Problem; (2) it proposes an origi-nal relaxation strategy on feasible FJSSP solutions based on the idea of randomly breaking the exe-cution orders of the activities on the machines and opening the resource options for some activities se-lected at random. The efficacy of the overall heuris-tic optimization algorithm is demonstrated on a set of well-known benchmarks.

Notes

Text Reference
Angelo Oddi, Riccardo Rasconi, Amedeo Cesta, and Stephen Smith , "Iterative Flattening Search for the Flexible Job Shop Scheduling Problem," Proceedings 22nd International Joint Conference on Artificial Intelligence, Barcelona, Spain, July, 2011. , July, 2011.

BibTeX Reference
@inproceedings{Oddi_2011_7052,
   author = "Angelo Oddi and Riccardo Rasconi and Amedeo Cesta and Stephen {Smith }",
   title = "Iterative Flattening Search for the Flexible Job Shop Scheduling Problem",
   booktitle = "Proceedings 22nd International Joint Conference on Artificial Intelligence, Barcelona, Spain, July, 2011. ",
   month = "July",
   year = "2011",
   number= "CMU-RI-TR-",
}

The Robotics Institute is part of the School of Computer Science, Carnegie Mellon University.
Contact Us | Update Instructions