July
2011
Job Shop Scheduling with Routing Flexibility and Sequence Dependent Setup-Times
Authors:
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.
copied = false, 2000);
">
@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},
}
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},
}