Les problèmes d'ordonnancement de type « flow-shop » hybride : état de l'art

Vignier, A.; Billaut, J.-C.; Proust, C.

Vignier, A. ; Billaut, J.-C. ; Proust, C.

RAIRO - Operations Research - Recherche Opérationnelle, Tome 33 (1999) no. 2, pp. 117-183.

MR Zbl | 1 citation dans Numdam

@article{RO_1999__33_2_117_0,
     author = {Vignier, A. and Billaut, J.-C. and Proust, C.},
     title = {Les probl\`emes d'ordonnancement de type {\guillemotleft} flow-shop {\guillemotright} hybride : \'etat de l'art},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {117--183},
     publisher = {EDP-Sciences},
     volume = {33},
     number = {2},
     year = {1999},
     mrnumber = {1716954},
     zbl = {0960.90042},
     language = {fr},
     url = {http://archive.numdam.org/item/RO_1999__33_2_117_0/}
}

TY  - JOUR
AU  - Vignier, A.
AU  - Billaut, J.-C.
AU  - Proust, C.
TI  - Les problèmes d'ordonnancement de type « flow-shop » hybride : état de l'art
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 1999
SP  - 117
EP  - 183
VL  - 33
IS  - 2
PB  - EDP-Sciences
UR  - http://archive.numdam.org/item/RO_1999__33_2_117_0/
LA  - fr
ID  - RO_1999__33_2_117_0
ER  -

%0 Journal Article
%A Vignier, A.
%A Billaut, J.-C.
%A Proust, C.
%T Les problèmes d'ordonnancement de type « flow-shop » hybride : état de l'art
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 1999
%P 117-183
%V 33
%N 2
%I EDP-Sciences
%U http://archive.numdam.org/item/RO_1999__33_2_117_0/
%G fr
%F RO_1999__33_2_117_0

Vignier, A.; Billaut, J.-C.; Proust, C. Les problèmes d'ordonnancement de type « flow-shop » hybride : état de l'art. RAIRO - Operations Research - Recherche Opérationnelle, Tome 33 (1999) no. 2, pp. 117-183. http://archive.numdam.org/item/RO_1999__33_2_117_0/

Bibliographie
Cité par

[ag-1995] E. H. Aghezzaf, A. Artiba, O. Moursli et C. Tahon, Hybrid flowshop problems, a decomposition based heuristic approach. In International Conference on Industrial Ingineering and Production Management (IEPM'95), avril 1995, Marrakech (Maroc), FUCAM/IFIP/INRIA, p. 43-56.

[al-1997] F. Alexandre, C. Cardeira, F. Charpillet, Z. Mammeri et M.-C. Portmann, Compu-search Methodologies II : Scheduling using Genetic Algorithms and Artificial Neural Networks, dans The Planning and Scheduling of Production System, A. Artiba et S. E. Elmaghraby, Chapman & Hall edition, 1997, p. 301-336.

[ba-1974] K. R. Baker, Introduction to sequencing and scheduling, John Willey & Sons, Inc., 1974.

[ba-1987] P. Baptiste, C. H. Cho, J. Favrel et M. Zouhri, Une caractérisation analytique des ordonnancements admissibles sous contraintes hétérogènes en flow-shop, RAIRO-APII, 1987, 25, p. 87-102. | Zbl

[be-1982] R. Bellman, A. O. Esogbue et I. Nabeshima, Mathematical aspects of scheduling and applications, volume 4 of International Series in Modern Applied Mathematics and Computer Science, Pergamon Press edition, 1982. | MR | Zbl

[ro-1996] J-C. Billaut et F. Roubellat, A new method for workshop real time scheduling, Int. J. Prod. Res., 1996, 34, n° 6, p. 1555-1579. | Zbl

[bl-1994] J. Blazewicz, K. Ecker, G. Schmidt et J. Weglarz, Scheduling in Computer and Manufacturing Systems, Springer-Verlag edition, 1994. | Zbl

[bo-1996] V. Botta-Genoulaz, Planification et ordonnancement d'une succession d'ateliers avec contraintes, PhD thesis, Université Claude Bernard-Lyon 1, décembre 1996.

[br-1991] S. A. Brah et J. L. Hunsucker, Branch and bound algorithm for the flow shop with multiple processors, European Journal of Operational Research, 1991, 57, p. 88-99. | Zbl

[br-1975] P. Bratley, M. Florian et P. Robillard, Scheduling with earliest start and due date constraints on multiple machines, Naval Research Logistics Quarterly, 1975, 22, n° 1, p. 165-173. | Zbl

[bu-1973] R. E. Buten et V. Y. Shen, A scheduling model for computer Systems with two classes of processors, Sagomore Computer Conference on Parallel Processing, 1973.

[ca-1970] H. G. Campbell, R. A. Dukek et M. L. Smith, A heuristic algorithm for the n job, m machine sequencing problem, Management Science, 1970, 16, n° 10, p. B630-B637. | Zbl

[Ca-1988] J. Carlier et P. Chretienne, Problèmes d'ordonnancement (modélisation/complexité/algorithmes), Études et Recherches en Informatique, Masson édition, 1988.

[ca-1987] J. Carlier, Scheduling jobs with release dates and tails on identical machines to minimize the makespan, European Journal of Operational Research, 1987, 29, p. 298-306. | MR | Zbl

[ch-1990] Y.-L. Chang et R. S., Sullivan, Schedule generation in a dynamic job shop, Int. J. Prod. Res., 1990, 28, n° 1, p. 65-74.

[ch-1995] B. Chen, Analysis of classes of heuristics for scheduling a two-stage flow shop with parallel machines at one stage, Journal of Operational Research Society, 1995, 46, n° 2, p. 234-244. | Zbl

[co-1994] Collectif, « Ordonnancement et Entreprises : applications concrètes et outils pour le futur ». In Journées d'études, Toulouse (France), CNRS/GdR Automatique/pôle SED/GT3. juin 1994, 315 p.

[de-1991] D. E. Deal et J. L. Hunsucker, The two stage flowshop scheduling problem with m machines at each stage, Journal of Information and Optimization Sciences, 1991, 72, p. 407-471. | Zbl

[dj-1996] L. Djerid et M.-C. Portmann, Genetic algorithm operators restricted to precedent constraints set: genetic algorithm designs with or without branch and bound approach for solving scheduling problems with disjunctive constraints, Pékin (Chine), IEEE/Systems, Man and Cybernetics (SMC'96), octobre 1996, 4, p. 2922-2927.

[fo-1996] Ph. Fortemps, Ch. Ost, M. Pirlot, J. Teghem et D. Tuyttens, A production scheduling case study in a chemical firm using metaheuristics, European Journal of Operational Research, 1996, soumis.

[fo-1993] C. Foure, D. M Gay et B.W. Kernighan, AMPL: A Modeling Language for Mathematical Programming, The Scientific Press edition, 1993. | Zbl

[go-1993] Gotha Les problèmes d'ordonnancement, RAIRO Rech. Opér., 1993, 27, n° 1, p. 77-150. | Numdam | MR

[gr-1979] R. L. Graham, E. L. Lawler, J. K. Lenstra et A. H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling theory: a survey, Ann. Discrete Math., 1979, 5, p. 287-326. | MR | Zbl

[gr-1966] R. L. Graham, Bounds for certain multiprocessing anomalies, The Bell System Technical Journal, 1966, 45, p. 1563-1581. | Zbl

[gu-1995] A. Guinet, V. Botta et M. Solomon, Minimisation du plus grand retard ou de la plus grande date de fin dans les problèmes d'ordonnancement de type flowshop hybride. In Journées d'études: « Affectation et Ordonnancement », Tours (France), CNRS/GdR Automatique/pôle SED/GT3, septembre 1995, p. 95-111.

[gu-1996] A. Guinet, M. M. Solomon, P. K. Kedia et A. Dussauchoy, A computational study of heuristics for two-stage flexible flowshops, Int J. Prod. Res., 1996, 34, n° 5, p. 1399-1415. | Zbl

[gup-1995] J. N. D. Gupta, A. M. A. Hariri et C. N. Potts, Scheduling a two-stage hybrid flow shop with parallel machines at the first stage, Mathematics of Industrial Systems (Annals of operations research), 1995, à paraître. | Zbl

[gu-1991] J. N.D. Gupta et E. A. Tunc, Schedules for a two-stage hybrid flowshop with parallel machines at the second stage, Int. J. Prod. Res., 1991, 29, n° 7, p. 1489-1502.

[gu-1994] J. N. D. Gupta et E. A. Tunc, Scheduling a two-stage hybrid flowshop with separable setup and removal times, European Journal of Operational Research, 1994, 77, p. 415-428. | Zbl

[gu-1988] J. N. D. Gupta, Two-stage hybrid flowshop scheduling problem, Operational Research Society, 1988, 39, n° 4, p. 359-364. | Zbl

[ha-1979] R. H. Hayes et S. C. Wheelwright, Le cycle de vie du processus de production (i) et (ii), Harvard-L'expansion, automne 1979, p. 23-32, 99-110.

[he-1996] H. Hentous et A. Guinet, A constraint hybrid flowshop problem. In Workshop on Production Planning and Control (WPPC), septembre 1996, Mons, Belgique, FUCaM/EIASM/ICM, p. 303-306.

[ho-1974] W. A. Horn, Some simple scheduling algorithms, Naval Research Logistics Quarterly, 1974, 21, p. 177-185. | MR | Zbl

[hu-1992] J. L. Hunsucker et J. R. Shah, Performance of priority rules in a due date flow shop, OMEGA, 1992, 20, n° 1, p. 73-89.

[hu-1994] J. L. Hunsucker et J. R. Shah, Comparative performance analysis of priority rules in a constrained flow shop with multiple processors environment, European Journal of Operational Research, 1994, 72, p. 102-114. | Zbl

[ig-1965] E. Ignall et L. Schrage, Application of the branch and bound technique to some flow-shop scheduling problems, Operations Research, 1965, 13, n° 3, p. 400-412. | MR

[jo-l954] S. M. Johnson, Optimal two and three stage production schedules with setup times included, Naval Research Logistics Quarterly, 1954, 1, n° 1, p. 61-68.

[ka-1997] S. N. Kadipasaoylu, W. Xiang et B. M. Khumawola, A comparison of scheduling rules in static and dynamic hybrid flow Systems, Int. J. Prod. Res., 1997, 35, n° 5, p. 1359-1384. | Zbl

[la-1978] B. J. Lageweg, J. K. Lenstra et A. H. G. Rinnooy Kan, A general bounding scheme for the permutation flow-shop problem, Operations Research, 1978, 26, n° 1, p. 53-67. | Zbl

[la-1987] M. A. Langston, Interstage transportation planning in the deterministic flow-shop environment, Operations Research, 1987, 35, n° 4, p. 556-564.

[la-1994] J.-B. Lasserre et S. Dauzère-Pérès, Planification et ordonnancement intégrés dans un atelier de type jobshop, Bulletin de liaison n° 8 du CNRS/GdR Automatique/Ple SED/GT3, avril 1994.

[la-1982] R. Laumaille, Pratique de Gestion de Production, Les Editions d'Organisation, 1982.

[la-1989] E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan et D. B. Shmoys, Sequencing and scheduling: algorithms and complexity, Report BS-R8909, Center for Mathematics and Computer Science, The Netherlands, Amsterdam, 1989, 70 p.

[lee-1993] C. Lee, T. C. E. Cheng et B.M.T. Lin, Minimizing the makespan in the 3-machine assembly flowshop scheduling problem, Management Science, 1993, 39, n° 5, p. 616-625. | Zbl

[lee-1994] C. Y. Lee et G. L. Vairaktarakis, Minimizing makespan in hybrid flowshop, Operations Research Letters, 1994, 16, n° 3, p. 149-158. | MR | Zbl

[le-1992] A. Legait, L'intégration : quels impacts surla spécification d'un système de gestion de production assistée par ordinateur?, PhD thesis, Université de Lyon I-INSA, 1992.

[le-1979] P. Lemoal et J. C. Tarondeau, Un défi à la fonction de la production, Revue Française de Gestion, Janvier-Février 1979, p. 9-14.

[le-1994] M.-L. Levy, P. Lopez et B. Pradin, Characterization of feasible schedules for the flow-shop problem: a decomposition approach. In European Workshop on Integrated Manufacturing Systems Engineering (IMSE'94), Grenoble (France), INRIA, décembre 1994, p. 307-315.

[li-1996] S. Li, A hybrid two-stage flowshop with part family, batch production, major and minor setups, European Journal of Operational Research, 1996à paraître. | Zbl

[ma-1993] B. L. Maccarthy et J. Liu, Addressing the gapin scheduling research: a review of optimization and heuristic methods in production scheduling, Int. J. Prod. Res., 1993, 31, n° 1, p. 59-79.

[na-1959] R. Macnaughton, Scheduling with deadlines and loss functions, Management Science, 1959, 6, p. 1-12 | MR | Zbl

[mi-1959] L. G. Mitten, Sequencing n jobs on two machines with arbitrary time lags, Management Science, 1959, 5, n° 3, p. 293-298. | MR | Zbl

[mo-1983] C. L. Monma et A. H. G. Rinnooy Kan, A concise survey of efficiently solvable special cases of the permutation flow-shop problem, RAIRO Rech. Opér., 1983, 17, n° 2, p. 105-119. | Numdam | MR | Zbl

[na-1987] S. L. Narasimhan et P. M. Mangiameli, A comparison of sequencing rules for a two-stage hybrid flowshop, Decision Sciences, 1987, 18, p. 250-265.

[na-1984] S. L. Narasimhan et S. S. Panwalkar, Scheduling in a two stage manufacturing process, Int. J, Prod. Res., 1984, 22, n° 4, p. 555-564.

[na-1983] M. Nawaz, E. Enscore et I. Ham, A heuristic algorithm fort the m machine, n job flowshop sequencing problem, OMEGA, 1983, 11, n° 1, p.91-95.

[pa-1961] S. Page, An approach to the scheduling of jobs on machines, J. Roy. Statist. Soc., 1961, 23, p. 484-492. | MR

[pa-1979] R. J. Paul, A production scheduling problem in the glass-container industry, Operations Research, 1979, 27, n° 2, p. 290-302.

[po-1996] M. C. Portmann, A. Vignier, D. Dardilhac et D. Dezalay, Some hybrid flowshop scheduling by crossing branch and bound and genetic algorithms. In 5th International Workshop on Project Management and Scheduling (PMS'96), Poznan (Pologne), avril 1996, p. 186-189.

[po-1988] M.-C Portmann, Méthodes de décomposition spatiales et temporelles en ordonnancement de la production, RAIRO-APII, 1988, 22, n° 5, p. 439-451. | MR | Zbl

[pr-1995] C. Proust et E. Grunenberger, Planification de production dans un contexte de flow-shop hybride à deux étages : conception et interprogrammation d'ARIANNE 2000, RAPA, 1995, 8, n° 5, p. 715-734.

[pr-1992] C. Proust, Using Johnson's algorithm for solving flowshop scheduling problems. In Summer school on Scheduling Theory andits Applications, Bonas (France), INRIA/C3/COMETT, octobre 1992, p. 297-342.

[ra-1992b] C. Rajendran et D. Chaudhuri, A multi-stage parallel processor flowshop problem with minimum flowtime, European Journal of Operational Research, 1992, 57, p. 111-122. | Zbl

[ra-1992a] C. Rajendran et D. Chaudhuri, Scheduling in n-jobs, m stage flowshop with parallel processors to minimize makespan, Int. J. of Production Economics, 1992, 27, p. 137-143.

[ri-1995] P. Richard, C. Cavalier, N. Jacquet et C. Proust, Solving scheduling problems using petri nets and constraints logic programming. In International Conference on Emerging Technologies and Factory Automation (ETFA'95), Vol. 1, Paris (France), INRIA/IEEE, octobre 1995, p. 59-68.

[ri-1976] A. H. G. Rinnooy Kan, Machine scheduling problems: classification, complexity and computations, Nijhoff, The Hague, 1976. | Zbl

[sa-1973] M. S. Salvador, A solution to a special class of flow shop scheduling problem. In Symposium on the Theory of Scheduling and its Applications Springer-Verlag, Berlin (Allemagne), 1973, p. 83-91. | MR | Zbl

[sa-1992] E. Sanlaville, Conception et analyse d'algorithmes de liste en ordonnancement préemptif, PhD thesis, Université de Paris VI, september 1992.

[sa-1995] D. L. Santos, J. L. Hunsucker et D. E Deal, Global lower bounds for flow shop with multiple processors, European Journal of Operational Research, 1995, 80, p. 112-120. | Zbl

[saw-1993] T. J Sawik, A scheduling algorithm for flexible flow lines with limited intermediate buffers, Applied Stochastic Models and Data Analysis, 1993, 9, p. 127-138.

[saw-1995] T.J. Sawik, Scheduling flexible flow lines with no in-process buffers, Int. J. Prod. Res., 1995, 33, n° 5, p. 1357-1367. | Zbl

[sh-1972] V.Y. Shen et Y.E. Chen, A scheduling strategy for the flowshop problem in a System with two classes of processors. In Conference on Information and Systems Science, 1972, p. 645-649.

[sh-1990] H. D. Sherali, S. C. Sarin et M. S. Kodialam, Models and algorithm for a two-stage production process, Production Planning and Control, 1990, 1, n° 1, p. 27-39.

[sr-1989] C. Sriskandarajah et S. P. Sethi, Scheduling algorithms for flexible flow-shops: Worst and average case performance, European Journal of Operational Research, 1989, 43, p. 143-160. | MR | Zbl

[st-1990] E. F. Stafford et F. T. Tseng, On the Srikar-Ghosh MILP model for the nxm SDST flowshop problem, Int. J. Prod. Res., 1990, 28, n° 10, p. 1817-1830.

[su-1983] D. R. Sule et K. Y. Huang, Sequency on two and three machines with setup, processing and removal times separated, Int. J. Prod. Res., 1983, 21, n° 5, p. 723-732. | Zbl

[sz-1987] W. Szwarc et J. N. D. Gupta, A flow-shop problem with sequence-dependant additive setup times, Naval Research Logistics Quarterly, 1987, 23, p. 619-627. | MR | Zbl

[sz-1983] W. Szwarc, Flowshop problems with time lags, Management Science, 1983, 29, n° 4, p. 477-481. | Zbl

[to-1977] W. Townsend, Sequencing n jobs on m machines to minimize maximum tardiness: a branch and bound solution, Management Science, 1977, 23, n° 9, p. 1016-1019. | Zbl

[va-1994] A. Vandevelde, Minimizing the makespan in a multiprocessor flow shop, Master's thesis, avril 1994, 37 p.

[vi-1995] A. Vignier, J.-C. Billaut et C. Proust, Les problèmes de flow-shop hybride : état de l'art, Rapport Interne 155, LI/E3i/Univ. de Tours, mai 1995, 100 p.

[vi-1996a] A. Vignier, J.-C. Billaut et C. Proust, Solving k-stage hybrid flowshop scheduling problems. In Multiconference on Computational Engineering in Systems Applications (CESA'96), Symposium on Discrete Events and Manufacturing Systems (IEEE-SMC /IMACS), Lille (France), 1996, p. 250-258.

[vi-1996b] A. Vignier, J.-C. Billaut, C. Proust et V. Tkindt, Resolution of some two stage hybrid flowshop scheduling problems, Pékin (Chine), IEEE/Systems, Man and Cybernetics (SMC'96), octobre 1996, p. 2934-2941.

[vi-1996c] A. Vignier, D. Dardilhac, D. Dezalay et C. Proust, A branch and bound approach to minimize the total completion time in a k-stage hybrid flowshop. In 5th Internationnal Conference on Emerging Technologies and Factory Automation (ETFA'96), Hawaii (USA), IEEE/SICE, novembre 1996, 1, p. 215-220.

[wi-1985] R. J. Wittrock, Scheduling algorithms for flexible flow lines, IBM J. Res. Develop., juillet 1985, 29, n° 4, p. 401-412.

[wi-1988] R. J. Wittrock, An adaptable scheduling algorithm for flexible flow line, OpSearch, 1988, 36, n° 3, p. 445-453. | Zbl