《2016 Iterative Flattening Search for the Flexible Job Shop Scheduling Problem》.pdf

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence Iterative Flattening Search for the Flexible Job Shop Scheduling Problem Angelo Oddi 1 and Riccardo Rasconi 1 and Amedeo Cesta 1 and Stephen F. Smith 2 1 Institute of Cognitive Science and Technology, CNR, Rome, Italy {angelo.oddi, riccardo.rasconi, amedeo.cesta}@r.it 2 Robotics Institute, Carnegie Mellon University, Pittsburgh, PA, USA sfs@ Abstract be processed on any one of a designated set of available ma- chines. The FJSSP is more difficult than the classical Job This paper presents a meta-heuristic algorithm for Shop Scheduling Problem (which is itself NP-hard), since it solving the Flexible Job Shop Scheduling Problem is not just a sequencing problem. In addition to deciding how (FJSSP). This strategy, known as Iterative Flatten- to sequence activities that require the same machine, it is also ing Search (IFS), iteratively applies a relaxation- necessary to choose a routing policy, that is which machine step, in which a subset of scheduling decisions are will process each activity. The objective remains that of min- randomly retracted from the current solution; and a imizing makespan. The problem is motivated by interest in solving-step, in which a new solution is incremen- developing Flexible Manufacturing Systems (FMS), as un- tally recomputed from this partial schedule. This [