A batch-oblivious approach for Complex Job-Shop scheduling problems

Abstract : We consider a Flexible Job-Shop scheduling problem with batching machines, reentrant flows, sequence dependent setup times and release dates while considering different regular objective functions. Semiconductor manufacturing is probably one of the most prominent practical applications of such a problem. Existing disjunctive graph approaches for this combined problem rely on dedicated nodes to explicitly represent batches. To facilitate modifications of the graph, our new modeling reduces this complexity by encoding batching decisions into edge weights. An important contribution is an original algorithm that takes batching decisions “on the fly” during graph traversals. This algorithm is complemented by an integrated move to resequence and reassign operations. This combination yields a rich neighborhood that we apply within a local search and a Simulated Annealing (SA) metaheuristic. The latter is embedded in a Greedy Randomized Adaptive Search Procedure (GRASP) which is the most efficient approach. Numerical results for benchmark instances of different problem types show the generality and applicability of our approach. The conciseness of our idea facilitates extensions towards further complex constraints needed in real-world applications.
Type de document :
Article dans une revue
European Journal of Operational Research, Elsevier, 2017, 263, pp.50-61. 〈10.1016/j.ejor.2017.04.050〉
Liste complète des métadonnées

https://hal-emse.ccsd.cnrs.fr/emse-01555744
Contributeur : Stéphane Dauzère-Pérès <>
Soumis le : mardi 4 juillet 2017 - 13:29:54
Dernière modification le : lundi 17 juillet 2017 - 12:21:44

Identifiants

Collections

Citation

Sebastian Knopp, Stéphane Dauzere-Peres, Claude Yugma. A batch-oblivious approach for Complex Job-Shop scheduling problems. European Journal of Operational Research, Elsevier, 2017, 263, pp.50-61. 〈10.1016/j.ejor.2017.04.050〉. 〈emse-01555744〉

Partager

Métriques

Consultations de la notice

96