Généralisation max-plus des bornes de Lageweg, Lenstra et Rinnooy Kan
RAIRO - Operations Research - Recherche Opérationnelle, Volume 37 (2003) no. 4, p. 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.

     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},
     publisher = {EDP-Sciences},
     volume = {37},
     number = {4},
     year = {2003},
     pages = {273-289},
     doi = {10.1051/ro:2004006},
     zbl = {1092.90024},
     mrnumber = {2065243},
     language = {fr},
     url = {http://www.numdam.org/item/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://www.numdam.org/item/RO_2003__37_4_273_0/

[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 1204266 | Zbl 0824.93003

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

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

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

[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 0814.90045

[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 778424 | Zbl 0557.93005

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

[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 418895 | Zbl 0396.90041

[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 1684424 | Zbl 0955.68082

[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 868083 | Zbl 0497.05023

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

[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 1376614

[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 0371.90059

[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 101164 | Zbl 0995.90539

[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 0511.90073

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