A New Heuristic for the Flow Shop Scheduling Problem with Availability Constraints - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2002

A New Heuristic for the Flow Shop Scheduling Problem with Availability Constraints

Résumé

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.
Fichier non déposé

Dates et versions

inria-00100962 , version 1 (26-09-2006)

Identifiants

  • HAL Id : inria-00100962 , version 1

Citer

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. ⟨inria-00100962⟩
57 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More