A general approach for optimizing regular criteria in the job-shop scheduling problem

Abstract : Even though a very large number of solution methods has been developed for the job-shop scheduling problem, a majority has been designed for the makespan criterion. In this paper, we propose a general approach for optimizing any regular criterion in the job-shop scheduling problem. The approach is a local search method that uses a disjunctive graph model and neighborhoods generated by swapping critical arcs. The connectivity property of the neighborhood structure is proved and a novel efficient method for evaluating moves is presented. Besides its generality, another prominent advantage of the proposed approach is its simple implementation that only requires to tune the range of one parameter. Extensive computational experiments carried out on various criteria (makespan, total weighted flow time, total weighted tardiness, weighted sum of tardy jobs, maximum tardiness) show the efficiency of the proposed approach. Best results were obtained for some problem instances taken from the literature.
Type de document :
Article dans une revue
European Journal of Operational Research, Elsevier, 2011, 212, pp.33-42. 〈10.1016/j.ejor.2011.01.046〉
Liste complète des métadonnées

https://hal-emse.ccsd.cnrs.fr/emse-00613008
Contributeur : Stéphane Dauzère-Pérès <>
Soumis le : mardi 2 août 2011 - 09:24:16
Dernière modification le : mardi 16 janvier 2018 - 14:36:26

Identifiants

Citation

Yazid Mati, Stéphane Dauzère-Pérès, Chams Lahlou. A general approach for optimizing regular criteria in the job-shop scheduling problem. European Journal of Operational Research, Elsevier, 2011, 212, pp.33-42. 〈10.1016/j.ejor.2011.01.046〉. 〈emse-00613008〉

Partager

Métriques

Consultations de la notice

273