A new formulation for scheduling unrelated processor under precedence constraints

Nelson Maculan; Stella C. S. Porto; Celso C. Ribeiro; Cid Carvalho de Souza

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

  • Volume: 33, Issue: 1, page 87-92
  • ISSN: 0399-0559

How to cite

top

Maculan, Nelson, et al. "A new formulation for scheduling unrelated processor under precedence constraints." RAIRO - Operations Research - Recherche Opérationnelle 33.1 (1999): 87-92. <http://eudml.org/doc/105186>.

@article{Maculan1999,
author = {Maculan, Nelson, Porto, Stella C. S., Ribeiro, Celso C., Carvalho de Souza, Cid},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {parallel processing; scheduling; unrelated processors; precedence constraints; makespan},
language = {eng},
number = {1},
pages = {87-92},
publisher = {EDP-Sciences},
title = {A new formulation for scheduling unrelated processor under precedence constraints},
url = {http://eudml.org/doc/105186},
volume = {33},
year = {1999},
}

TY - JOUR
AU - Maculan, Nelson
AU - Porto, Stella C. S.
AU - Ribeiro, Celso C.
AU - Carvalho de Souza, Cid
TI - A new formulation for scheduling unrelated processor under precedence constraints
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 1999
PB - EDP-Sciences
VL - 33
IS - 1
SP - 87
EP - 92
LA - eng
KW - parallel processing; scheduling; unrelated processors; precedence constraints; makespan
UR - http://eudml.org/doc/105186
ER -

References

top
  1. 1. D. P. BERTSEKAS and J. N TSITSIKLIS, Parallel and Distributed Computation, Prentice-Hall, Englewood Cliffs, 1989. Zbl0743.65107
  2. 2. J. BLAZEWICZ, Personnal communication, 1993. 
  3. 3. J. BLAZEWICZ, W. CELLARY, R. SLOWINSKI and J. WEGLARZ, Scheduling Under Resource Constraints - Deterministic Models, J.C. Baltzer AG, Basel 1986. Zbl0668.90045
  4. 4. E. G. COFFMAN and P. J. DENNING, Operating Systems Theory, Prentice-Hall Inc., New Jersey, 1973. 
  5. 5. M. R. GAREY and D. S. JOHNSON, Strong NP-Completeness Results: Motivation, Examples and Implications, Journal of the ACM 25, 1978, pp. 499-508. Zbl0379.68035MR478747
  6. 6. M. R. GAREY and D. S. JOHNSON, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, San Francisco, 1979. Zbl0411.68039MR519066
  7. 7. J.-B. LASSERRE and M. QUEYRANNE, Generic Scheduling Polyhedra and a New Mixed-Integer Formulation for Single Machine Scheduling, in Proceedings of the II Integer Programming and Combinatorial Optimization Conference (E. Balas, G. Cornuejols, and R. Kannan, eds.), pp. 136-149. 
  8. 8. E. L. LAWLER, J. K. LENSTRA, A. H. G. RINNOOY KAN and D. B. SHMOYS, Sequencing and Scheduling: Algorithms and Complexity, Report NFI 11.89/03, Eindhoven Institute of Technology, Department of Mathematics and Computer Science, Eindhoven, 1989. 
  9. 9. D. A. MENASCÉ and S. C. S. PORTO, Processor Assignment in Heterogeneous Parallel Architectures, Proceedings of the IEEE International Parallel Processing Symposium, pp. 186-191, Beverly Hills, 1992. 
  10. 10. G. L. NEMHAUSER and L. A. WOLSEY, Integer and Combinatorial Optimization, John Wiley and Sons, 1988. Zbl0944.90001MR948455
  11. 11. S. C. PORTO and C. C. RIBEIRO, A Tabu Search Approach to Task Scheduling on Heterogeneous Processors under Precedence Constraints, International Journal of High Speed Computing 7, 1995, pp. 45-71. 
  12. 12. S. C. PORTO and C. C. RIBEIRO, Parallel Tabu Search Message-Passing Synchronous Strategies for Task Scheduling under Precedence Constraints, Journal of Heuristics 1, 1995, pp. 207-223. Zbl0853.68064
  13. 13. M. QUEYRANNE and A. SCHULZ, Polyhedral Approaches to Machine Scheduling, Report 1994-408, Technical University of Berlin, 1994. 

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.