Job Shop Scheduling with Routing Flexibility and Sequence Dependent Setup-Times

July 2011

Job Shop Scheduling with Routing Flexibility and Sequence Dependent Setup-Times

Authors:

A. Oddi, R. Rasconi, A. Cesta, and S. F. Smith

Abstract:

This paper presents a meta-heuristic algorithm for solving a job shop scheduling problem involving both sequence dependent setup-times and the possibility of selecting alternative routes among the available machines. The proposed strategy is a variant of the Iterative Flattening Search (IFS) schema. This work provides three separate results: (1) a constraint-based solving procedure that extends an existing approach for classical Job Shop Scheduling; (2) a new variable and value ordering heuristic based on temporal flexibility that take into account both sequence dependent setup-times and flexibility in machine selection; (3) an original relaxation strategy based on the idea of randomly breaking the execution orders of the activities on the machines with a activity selection criteria based on their proximity to the solution's critical path. The efficacy of the overall heuristic optimization algorithm is demonstrated on a new benchmark set which is an extension of a well-known and difficult benchmark for the Flexible Job Shop Scheduling Problem.
@workshop{Oddi-2011-120511,
author = {A. Oddi And R. Rasconi And A. Cesta And S. F. Smith},
title = {Job Shop Scheduling with Routing Flexibility and Sequence Dependent Setup-Times},
booktitle = {Proceedings of RCRA '11 International Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion},
year = {2011},
month = {July},
pages = {96 – 110},
}
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.