Le traditionnel problème d'ordonnancement de type flowshop se généralise en un problème d'optimisation matricielle dans l'algèbre Max-Plus. Une famille de bornes inférieures est présentée pour ce nouveau problème et la preuve est apportée que ces bornes généralisent les bornes de Lageweg et al.
The traditional flowshop scheduling problem can be generalised to a matricial optimisation problem in Max-Plus algebra. A family of lower bounds is developped for this new problem and proof is given that these bounds are a generalisation of the lower bounds of Lageweg et al.
@article{RO_2003__37_4_273_0,
author = {Lent\'e, Christophe and Bouquard, Jean-Louis},
title = {G\'en\'eralisation max-plus des bornes de {Lageweg,} {Lenstra} et {Rinnooy} {Kan}},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {273--289},
publisher = {EDP-Sciences},
volume = {37},
number = {4},
year = {2003},
doi = {10.1051/ro:2004006},
zbl = {1092.90024},
mrnumber = {2065243},
language = {fr},
url = {http://www.numdam.org/articles/10.1051/ro:2004006/}
}
TY - JOUR AU - Lenté, Christophe AU - Bouquard, Jean-Louis TI - Généralisation max-plus des bornes de Lageweg, Lenstra et Rinnooy Kan JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2003 DA - 2003/// SP - 273 EP - 289 VL - 37 IS - 4 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro:2004006/ UR - https://zbmath.org/?q=an%3A1092.90024 UR - https://www.ams.org/mathscinet-getitem?mr=2065243 UR - https://doi.org/10.1051/ro:2004006 DO - 10.1051/ro:2004006 LA - fr ID - RO_2003__37_4_273_0 ER -
Lenté, Christophe; Bouquard, Jean-Louis. Généralisation max-plus des bornes de Lageweg, Lenstra et Rinnooy Kan. RAIRO - Operations Research - Recherche Opérationnelle, Tome 37 (2003) no. 4, pp. 273-289. doi : 10.1051/ro:2004006. http://www.numdam.org/articles/10.1051/ro:2004006/
[1] ,, and, Synchronisation and Linearity: An Algebra for Discrete Event Systems. John Wiley and Sons, New York (1992). | MR 1204266 | Zbl 0824.93003
[2] , Scheduling groups of jobs in the two machine flow shop. Math. Comput. Modeling 13 (1990) 29-36. | MR 1047077
[3] , Matrices over ordered algebraic structures. J. Lond. Math. Soc. 39 (1964) 427-432. | MR 167438 | Zbl 0154.01104
[4] and, Residuation Theory. Pergamon Press (1972). | MR 396359 | Zbl 0301.06001
[5] , Lot streaming in a two stage flow shop with setup, processing and removal times separated. J. Oper. Res. Soc. 45 (1994) 1445-1455. | Zbl 0814.90045
[6] ,, and, A linear system-theoretic view of discret-event processes and its use for performance evaluation in manufacturing. IEEE Trans. Autom. Control 30 (1985) 210-220. | MR 778424 | Zbl 0557.93005
[7] and, Two-machine flowshop group scheduling problem. Comput. Oper. Res. 27 (2000) 75-985. | MR 1762925 | Zbl 0970.90037
[8] , and, The complexity of flowshop and jobshop scheduling. Math. Oper. Res. 1 (1976) 117-129. | MR 418895 | Zbl 0396.90041
[9] , Théorie des systèmes linéaires dans les dioïdes. Thèse de doctorat, École des mines de Paris (1992).
[10] and, Modeling and analysis of timed petri nets using heaps of pieces. IEEE Trans. Autom. Control 44 (1999) 683-698. | MR 1684424 | Zbl 0955.68082
[11] , Schedule algebras and their use in formulating general systems simulations, in Industrial scheduling. Muth and Thompson, Prentice Hall, New Jersey, USA (1963).
[12] and, Graphes et algorithmes1995). | MR 868083 | Zbl 0497.05023
[13] , Idempotency. Publications of the Newton Institute, Cambridge University Press (1998). | MR 1608365
[14] and, Cyclic scheduling on parallel processors: An overview, in Scheduling Theory and its Applications, edited by P. Chretienne, E. Coffman, J. Lenstra and Z. Liu. John Wiley (1995) 193-226. | MR 1376614
[15] , An extention of johnson's results on job-lot scheduling. Naval Res. Log. Quart. 3 (1956) 201-203.
[16] , Optimal two- and three-stage production schedules with setup times included. Naval Res. Log. Quart. 1 (1954) 61-68.
[17] , and, A general bounding scheme for the flow-shop problem. Oper. Res. 26 (1978) 53-67. | Zbl 0371.90059
[18] , Analyse Max-Plus de problèmes d'ordonnancement de type Flowshop. Thèse de doctorat, Université François Rabelais, Tours (novembre 2001).
[19] and, Une application des algèbres tropicales aux problèmes d'ordonnancement de type flowshop, in MOSIM'99, Annecy, France (octobre 1999) 177-182.
[20] , and, Modélisation unifiée de flowshops à deux machines, in conférence francophone de modélisation et simulation, (MOSIM'01), Troyes, France (avril 2001) 599-603.
[21] , and, Max-plus generalization of a flowshop problem lower and upper bounds, in (INCOM'01), Vienne, Autriche (sept. 2001).
[22] , and, Flowshops et minimisation de produits matriciels max 599-603.
[23] , Sequencing n jobs on two machines with arbitrary time lags. Manage. Sci. 5 (1959) 293-298. | MR 101164 | Zbl 0995.90539
[24] and, A note on the two-machine flow shop scheduling problem with separated setup and cleanup times, time lags and transportation times. Rep. Univ. Electro-com 34 (1983).
[25] , Sequencing n jobs on two machines with setup, processing and removal times separated. Naval Res. Log. Quart. 29 (1982) 517-519. | Zbl 0511.90073
[26] and, Optimal two-stage production scheduling with setup times separated. AIIE Transactions 11 (1979) 261-263.
Cité par Sources :
