《2016 A general approach for optimizing regular criteria in the job-shop scheduling problem》.pdf

European Journal of Operational Research 212 (2011) 33–42 Contents lists available at ScienceDirect European Journal of Operational Research journal homepage: www.else /locate/ejor Discrete Optimization A general approach for optimizing regular criteria in the job-shop scheduling problem Yazid Mati a, Stèphane Dauzère-Pérès b, Chams Lahlou c,⇑ a College of Business Economics, Al-Qassim University Almelaida, P.O. Box 6633, Saudi Arabia b Department of Manufacturing Sciences and Logistics Centre Microélectronique de Provence, Site Georges Charpak Ecole des Mines de Saint-Etienne 880 avenue de Mimet, F-13541 Gardanne, France c Ecole des Mines de Nantes - IRCCyN CNRS-UMR 6597 4 rue A. Kastler, La Chantrerie, BP 20722 F-44307 Nantes Cedex 3, France a r t i c l e i n f o a b s t r a c t Article history: Even though a very large number of solution methods has been developed for the job-shop scheduling Received 3 November 2008 problem, a majority has been designed for the makespan criterion. In this paper, we propose a general Accepted 24 January 2011 approach for optimizing any regular criterion in the job-shop scheduling problem. The approach is a local Available online 1 February 2011 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 Keywords: