Généralisation max-plus des bornes de Lageweg, Lenstra et Rinnooy Kan

Christophe Lenté; Jean-Louis Bouquard

RAIRO - Operations Research - Recherche Opérationnelle (2003)

  • Volume: 37, Issue: 4, page 273-289
  • ISSN: 0399-0559

Abstract

top
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.

How to cite

top

Lenté, Christophe, and Bouquard, Jean-Louis. "Généralisation max-plus des bornes de Lageweg, Lenstra et Rinnooy Kan." RAIRO - Operations Research - Recherche Opérationnelle 37.4 (2003): 273-289. <http://eudml.org/doc/244678>.

@article{Lenté2003,
abstract = {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é, Christophe, Bouquard, Jean-Louis},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
language = {fre},
number = {4},
pages = {273-289},
publisher = {EDP-Sciences},
title = {Généralisation max-plus des bornes de Lageweg, Lenstra et Rinnooy Kan},
url = {http://eudml.org/doc/244678},
volume = {37},
year = {2003},
}

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
PB - EDP-Sciences
VL - 37
IS - 4
SP - 273
EP - 289
AB - 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.
LA - fre
UR - http://eudml.org/doc/244678
ER -

References

top
  1. [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). Zbl0824.93003MR1204266
  2. [2] K.R. Baker, Scheduling groups of jobs in the two machine flow shop. Math. Comput. Modeling 13 (1990) 29-36. MR1047077
  3. [3] T.S. Blyth, Matrices over ordered algebraic structures. J. Lond. Math. Soc. 39 (1964) 427-432. Zbl0154.01104MR167438
  4. [4] T.S. Blyth and M.F. Janowitz, Residuation Theory. Pergamon Press (1972). Zbl0301.06001MR396359
  5. [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. Zbl0814.90045
  6. [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. Zbl0557.93005MR778424
  7. [7] Y. Dar-Li and C. Maw-Sheng, Two-machine flowshop group scheduling problem. Comput. Oper. Res. 27 (2000) 75-985. Zbl0970.90037MR1762925
  8. [8] M.R. Garey, D.S. Johnson and R. Sethi, The complexity of flowshop and jobshop scheduling. Math. Oper. Res. 1 (1976) 117-129. Zbl0396.90041MR418895
  9. [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. [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. Zbl0955.68082MR1684424
  11. [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. [12] M. Gondran and M. Minoux, Graphes et algorithmes. Eyrolles, Paris, 3 e edn. (1995). Zbl0497.05023MR868083
  13. [13] J. Gunawardena, Idempotency. Publications of the Newton Institute, Cambridge University Press (1998). MR1608365
  14. [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. Zbl0830.68009MR1376614
  15. [15] J.R. Jackson, An extention of johnson’s results on job-lot scheduling. Naval Res. Log. Quart. 3 (1956) 201-203. 
  16. [16] S.M. Johnson, Optimal two- and three-stage production schedules with setup times included. Naval Res. Log. Quart. 1 (1954) 61-68. 
  17. [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. Zbl0371.90059
  18. [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. [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. [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. [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. [22] C. Lenté, F. Chevaleyre and N. Neel, Flowshops et minimisation de produits matriciels max+, in 3 e journées francophone de recherche opérationnelle, (FRANCORO’01), l’aide à la décision pour l’amélioration de la performance, Québec, Canada (mai 2001) 599-603. 
  23. [23] L.G. Mitten, Sequencing n jobs on two machines with arbitrary time lags. Manage. Sci. 5 (1959) 293-298. Zbl0995.90539MR101164
  24. [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. [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. Zbl0511.90073
  26. [26] T. Yoshida and K. Hitomi, Optimal two-stage production scheduling with setup times separated. AIIE Transactions 11 (1979) 261-263. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.