Iterative Flattening Search for the Flexible Job Shop Scheduling Problem

Oddi, Angelo; Rasconi, Riccardo; Cesta, Amedeo; Smith, Stephen F.

doi:10.5591/978-1-57735-516-8/IJCAI11-332

Iterative Flattening Search for the Flexible Job Shop Scheduling Problem

Angelo Oddi, Riccardo Rasconi, Amedeo Cesta, Stephen F. Smith

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 1991-1995.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-332

Abstract

This paper presents a meta-heuristic algorithm for solving the Flexible Job Shop Scheduling Problem (FJSSP). This strategy, known as Iterative Flattening 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 incrementally recomputed from this partial schedule. This work contributes two separate results: (1) it proposes a constraint-based procedure extending an existing approach previously used for classical Job Shop Scheduling Problem; (2) it proposes an original relaxation strategy on feasible FJSSP solutions based on the idea of randomly breaking the execution orders of the activities on the machines and opening the resource options for some activities selected at random. The efficacy of the overall heuristic optimization algorithm is demonstrated on a set of well-known benchmarks.

Angelo Oddi, Riccardo Rasconi, Amedeo Cesta, and Stephen F. Smith. 2011. Iterative Flattening Search for the Flexible Job Shop Scheduling Problem. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 1991–1995. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-332

@inproceedings{ijcai2011p332,
  title     = {Iterative Flattening Search for the Flexible Job Shop Scheduling Problem},
  author    = {Oddi, Angelo and Rasconi, Riccardo and Cesta, Amedeo and Smith, Stephen F.},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {1991--1995},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-332},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-332},
}

TY  - CPAPER
TI  - Iterative Flattening Search for the Flexible Job Shop Scheduling Problem
AU  - Oddi, Angelo
AU  - Rasconi, Riccardo
AU  - Cesta, Amedeo
AU  - Smith, Stephen F.
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 1991
EP  - 1995
DO  - 10.5591/978-1-57735-516-8/IJCAI11-332
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-332
ER  -