Skip to Main content Skip to Navigation
Journal articles

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.
Complete list of metadata
Contributor : Stéphane Dauzère-Pérès Connect in order to contact the contributor
Submitted on : Tuesday, August 2, 2011 - 9:24:16 AM
Last modification on : Wednesday, April 27, 2022 - 3:50:00 AM



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⟩



Record views