A New Heuristic for the Flow 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 : It is commonly assumed in the scheduling literature that machines are available during the whole planning horizon. This paper addresses the flow shop scheduling problem with availability constraints (FSPAC). In such a problem one has to schedule n jobs on m machines with minimum cost under the assumption that these machines are not continuously available for processing jobs. The unavailability periods are supposed to be known in advance as a preventive maintenance activity and the operations of jobs are not preemptable. Being an extension of the classical flow shop, the problem is NP-hard in the strong sense. In a precedent work [1], a genetic algorithm and a tabu search based algorithm have been developed to approximately solve instances with several machines and several maintenance tasks on each machine. Here a new heuristic for solving the non-preemptive FSPAC is presented. The flow shop problem with two jobs and availability constraints is first considered. We show that the problem is polynomialy solvable by using a generalization of the classical geometric approach [2]. Based on this extension a heuristic, which consists in scheduling one by one and according to a sequence the remaining jobs to process, is then developed for solving the general case with more than two jobs. Finally, numerical experiments are performed on the randomly generated instances used in [1] to test the efficiency of the proposed approach. The results obtained by the new heuristic outperform in a significant way the previous ones. [1] Aggoune, R., (2001). Minimizing the makespan for the flow shop scheduling problem with availability constraints. ORP3'01, Operational Research Peripatetic Postgraduate Programme, Paris, France. [2] Brucker, P. and Jurisch, B., (1993). A new lower bound for the job-shop scheduling problem. European Journal of Operational Research 64, 156-167.
Type de document :
Communication dans un congrès
International Symposium on Combinatorial Optimization - CO'02, Apr 2002, Paris, France, 1 p, 2002
Liste complète des métadonnées

https://hal.inria.fr/inria-00100962
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-00100962, version 1

Collections

Citation

Riad Aggoune, Marie-Claude Portmann. A New Heuristic for the Flow Shop Scheduling Problem with Availability Constraints. International Symposium on Combinatorial Optimization - CO'02, Apr 2002, Paris, France, 1 p, 2002. 〈inria-00100962〉

Partager

Métriques

Consultations de la notice

116