A heuristic approach for the job shop scheduling problem with availability constraints

Riad Aggoune 1 Marie-Claude Portmann 1
1 MACSI - Industrial system modeling, analysis and operation
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : Most of papers dedicated to scheduling problems take the common assumption that the machines are available during the whole planning horizon. However, this assumption may be not true if a breakdown occurs, or if a maintenance task is to be processed on a machine. This paper addresses the job shop scheduling problem with availability constraints (JSPAC). In such a problem one has to schedule n jobs on m machines under the assumption that these machines are not continuously available for processing jobs. The objective function is to minimize the makespan. The unavailability periods are supposed to be known in advance as a preventive maintenance activity. Further, the operations of jobs are strictly not preemptable i.e. the execution of an operation can be interrupted neither by a maintenance task nor by another operation. We consider several unavailability periods arbitrarily distributed on the machines. According to the notation given in [3], the problem can be denoted by J, NCwin // Cmax. Being an extension of the classical job shop, the scheduling problem of JSPAC is NP-hard in the strong sense. To the best of our knowledge, no paper in the scheduling literature deals with the job shop problem with availability constraints. The job shop scheduling problem with two jobs subject to release dates and availability constraints is first considered. We show that the problem is polynomialy solvable by using a generalization of the classical geometric approach [1,2]. Based on this extension, a heuristic approach is then developed for solving the general case with several jobs. It consists in applying the two-job resolution procedure to pairs of jobs, according to a sequence representing a priority rule between jobs. More precisely, the two first jobs are optimally scheduled and release dates are associated to the next two jobs to be processed. The procedure is repeated until the examination of all jobs. Obviously, the quality of the solution given by the heuristic strongly depends on the job sequence. In order to optimize this sequence, a taboo search approach is employed. For lack of benchmarks devoted to the JSPAC, numerical experiments are performed on randomly generated instances to test the efficiency of the proposed approach. [1] Akers, S. B., Friedman, J., (1955). A non-numerical approach to production scheduling problems, Operations Research 3, 429-442. [2] Brucker, P., (1988). An efficient algorithm for the job-shop problem with two jobs, Computing 40, 353-359. [3] Schmidt, G., (2000). Scheduling with limited machine availability. European Journal of Operational Research 121, 1-15.
Type de document :
Communication dans un congrès
XV Conference of the European Chapter on Combinatorial Optimization - ECCO'2002, May 2002, Lugano, Switzerland, 1 p, 2002
Liste complète des métadonnées

https://hal.inria.fr/inria-00100961
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 14:53:10
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48

Identifiants

  • HAL Id : inria-00100961, version 1

Collections

Citation

Riad Aggoune, Marie-Claude Portmann. A heuristic approach for the job shop scheduling problem with availability constraints. XV Conference of the European Chapter on Combinatorial Optimization - ECCO'2002, May 2002, Lugano, Switzerland, 1 p, 2002. 〈inria-00100961〉

Partager

Métriques

Consultations de la notice

144