Généralisation max-plus des bornes de Lageweg, Lenstra et Rinnooy Kan
RAIRO - Operations Research - Recherche Opérationnelle, Volume 37 (2003) no. 4, pp. 273-289.

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.

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.

@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},
     mrnumber = {2065243},
     zbl = {1092.90024},
     language = {fr},
     url = {http://archive.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
SP  - 273
EP  - 289
VL  - 37
IS  - 4
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ro:2004006/
DO  - 10.1051/ro:2004006
LA  - fr
ID  - RO_2003__37_4_273_0
ER  - 
%0 Journal Article
%A Lenté, Christophe
%A Bouquard, Jean-Louis
%T Généralisation max-plus des bornes de Lageweg, Lenstra et Rinnooy Kan
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2003
%P 273-289
%V 37
%N 4
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ro:2004006/
%R 10.1051/ro:2004006
%G fr
%F RO_2003__37_4_273_0
Lenté, Christophe; Bouquard, Jean-Louis. Généralisation max-plus des bornes de Lageweg, Lenstra et Rinnooy Kan. RAIRO - Operations Research - Recherche Opérationnelle, Volume 37 (2003) no. 4, pp. 273-289. doi : 10.1051/ro:2004006. http://archive.numdam.org/articles/10.1051/ro:2004006/

[1] F. Baccelli, G. Cohen, G. Olsder and J.P. Quadrat, Synchronisation and Linearity: An Algebra for Discrete Event Systems. John Wiley and Sons, New York (1992). | MR | Zbl

[2] K.R. Baker, Scheduling groups of jobs in the two machine flow shop. Math. Comput. Modeling 13 (1990) 29-36. | MR

[3] T.S. Blyth, Matrices over ordered algebraic structures. J. Lond. Math. Soc. 39 (1964) 427-432. | MR | Zbl

[4] T.S. Blyth and M.F. Janowitz, Residuation Theory. Pergamon Press (1972). | MR | Zbl

[5] F.C. Cetinkaya, Lot streaming in a two stage flow shop with setup, processing and removal times separated. J. Oper. Res. Soc. 45 (1994) 1445-1455. | Zbl

[6] G. Cohen, D. Dubois, J.P. Quadrat and M. Viot, 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 | Zbl

[7] Y. Dar-Li and C. Maw-Sheng, Two-machine flowshop group scheduling problem. Comput. Oper. Res. 27 (2000) 75-985. | MR | Zbl

[8] M.R. Garey, D.S. Johnson and R. Sethi, The complexity of flowshop and jobshop scheduling. Math. Oper. Res. 1 (1976) 117-129. | MR | Zbl

[9] S. Gaubert, Théorie des systèmes linéaires dans les dioïdes. Thèse de doctorat, École des mines de Paris (1992).

[10] S. Gaubert and J. Mairesse, Modeling and analysis of timed petri nets using heaps of pieces. IEEE Trans. Autom. Control 44 (1999) 683-698. | MR | Zbl

[11] B. Giffler, Schedule algebras and their use in formulating general systems simulations, in Industrial scheduling. Muth and Thompson, Prentice Hall, New Jersey, USA (1963).

[12] M. Gondran and M. Minoux, Graphes et algorithmes1995). | MR | Zbl

[13] J. Gunawardena, Idempotency. Publications of the Newton Institute, Cambridge University Press (1998). | MR

[14] C. Hanen and A. Munier, 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

[15] J.R. Jackson, An extention of johnson's results on job-lot scheduling. Naval Res. Log. Quart. 3 (1956) 201-203.

[16] S.M. Johnson, Optimal two- and three-stage production schedules with setup times included. Naval Res. Log. Quart. 1 (1954) 61-68.

[17] B.J. Lageweg, J.K. Lenstra and A.H.G. Rinnooy Kan, A general bounding scheme for the flow-shop problem. Oper. Res. 26 (1978) 53-67. | Zbl

[18] C. Lenté, Analyse Max-Plus de problèmes d'ordonnancement de type Flowshop. Thèse de doctorat, Université François Rabelais, Tours (novembre 2001).

[19] C. Lenté and J.C. Billaut, Une application des algèbres tropicales aux problèmes d'ordonnancement de type flowshop, in MOSIM'99, Annecy, France (octobre 1999) 177-182.

[20] C. Lenté, J.C. Billaut and J.L. Bouquard, 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] C. Lenté, J.C. Billaut and J.L. Bouquard, Max-plus generalization of a flowshop problem lower and upper bounds, in (INCOM'01), Vienne, Autriche (sept. 2001).

[22] C. Lenté, F. Chevaleyre and N. Neel, Flowshops et minimisation de produits matriciels max 599-603.

[23] L.G. Mitten, Sequencing n jobs on two machines with arbitrary time lags. Manage. Sci. 5 (1959) 293-298. | MR | Zbl

[24] I. Nabeshima and S. Maruyama, 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] D.R. Sule, Sequencing n jobs on two machines with setup, processing and removal times separated. Naval Res. Log. Quart. 29 (1982) 517-519. | Zbl

[26] T. Yoshida and K. Hitomi, Optimal two-stage production scheduling with setup times separated. AIIE Transactions 11 (1979) 261-263.

Cited by Sources: