Main Article Content
Une étude d'approches heuristiques pour l'ordonnancement des jobs dans le "flowshop"
Abstract
A Study of Heuristics Approach for Scheduling jobs within the "flowshop"
Since the flowshop scheduling problem has found to be an NP-complete problem, the development of heuristic algorithms that give better solutions become necessary. In this paper we discuss how to resolve the flowshop problem using heuristic methodes, we were based on the study of [RAJ 91] in which three heuristic algorithms with the objective of minimizing total flowtime are proposed. In our paper we have detailed the concept introduced and given proofs of the principle formulas used in the algorithms presented. Our paper can be viewed as a contribution to understand better how to develop heuristic solution choosing the best minimizing criteria.
Key-words: The flowshop problem/ Heuristics/ Job scheduling/ Total flowtime.
Une étude d'approches heuristiques pour l'ordonnancement des jobs dans le "flowshop"*
Puisque l'ordonnancement des jobs dans les problèmes de flowshop représente un problème NP-complet, le développement des algorithmes heuristiques qui donnent des solutions approchées devient nécessaire. Cet article discute la résolution du problème flowshop en utilisant les méthodes heuristiques, il est axé sur l'analyse de l'article [RAJ 91] de Rajendran et Chaudhuri dans lequel trois nouveaux algorithmes sont proposés dans le but de fournir des solutions proches des solutions optimales et meilleures de celles trouvées par les méthodes qui existent déjà. Dans notre étude, nous détaillons les concepts introduits et nous donnons quelques preuves concernants les principales formules mathématiques utilisées dans les algorithmes présentés. Notre article peut être vue comme une contribution pour comprendre les mécanismes de base du développement des solutions heuristiques.
Mots- clés : Le problème de flowshop/ Heuristiques/ Ordonnancement de job/ Flowtime total.
Revue d'Information Scientifique & Technique Vol.11(2) 2001: 69-82
Since the flowshop scheduling problem has found to be an NP-complete problem, the development of heuristic algorithms that give better solutions become necessary. In this paper we discuss how to resolve the flowshop problem using heuristic methodes, we were based on the study of [RAJ 91] in which three heuristic algorithms with the objective of minimizing total flowtime are proposed. In our paper we have detailed the concept introduced and given proofs of the principle formulas used in the algorithms presented. Our paper can be viewed as a contribution to understand better how to develop heuristic solution choosing the best minimizing criteria.
Key-words: The flowshop problem/ Heuristics/ Job scheduling/ Total flowtime.
Une étude d'approches heuristiques pour l'ordonnancement des jobs dans le "flowshop"*
Puisque l'ordonnancement des jobs dans les problèmes de flowshop représente un problème NP-complet, le développement des algorithmes heuristiques qui donnent des solutions approchées devient nécessaire. Cet article discute la résolution du problème flowshop en utilisant les méthodes heuristiques, il est axé sur l'analyse de l'article [RAJ 91] de Rajendran et Chaudhuri dans lequel trois nouveaux algorithmes sont proposés dans le but de fournir des solutions proches des solutions optimales et meilleures de celles trouvées par les méthodes qui existent déjà. Dans notre étude, nous détaillons les concepts introduits et nous donnons quelques preuves concernants les principales formules mathématiques utilisées dans les algorithmes présentés. Notre article peut être vue comme une contribution pour comprendre les mécanismes de base du développement des solutions heuristiques.
Mots- clés : Le problème de flowshop/ Heuristiques/ Ordonnancement de job/ Flowtime total.
Revue d'Information Scientifique & Technique Vol.11(2) 2001: 69-82
