Polynomial time algorithms for special open shop problems with precedence constraints and unit processing times

Heidemarie Bräsel; Dagmar Kluge; Frank Werner

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

  • Volume: 30, Issue: 1, page 65-79
  • ISSN: 0399-0559

How to cite

top

Bräsel, Heidemarie, Kluge, Dagmar, and Werner, Frank. "Polynomial time algorithms for special open shop problems with precedence constraints and unit processing times." RAIRO - Operations Research - Recherche Opérationnelle 30.1 (1996): 65-79. <http://eudml.org/doc/105120>.

@article{Bräsel1996,
author = {Bräsel, Heidemarie, Kluge, Dagmar, Werner, Frank},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {open shop problems; unit processing times; two machines; arbitrary precedence constraints; polynomial time algorithm; minimization of the makespan; worst case complexity; intree constraints},
language = {eng},
number = {1},
pages = {65-79},
publisher = {EDP-Sciences},
title = {Polynomial time algorithms for special open shop problems with precedence constraints and unit processing times},
url = {http://eudml.org/doc/105120},
volume = {30},
year = {1996},
}

TY - JOUR
AU - Bräsel, Heidemarie
AU - Kluge, Dagmar
AU - Werner, Frank
TI - Polynomial time algorithms for special open shop problems with precedence constraints and unit processing times
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 1996
PB - EDP-Sciences
VL - 30
IS - 1
SP - 65
EP - 79
LA - eng
KW - open shop problems; unit processing times; two machines; arbitrary precedence constraints; polynomial time algorithm; minimization of the makespan; worst case complexity; intree constraints
UR - http://eudml.org/doc/105120
ER -

References

top
  1. 1. H. BRÄSEL, Lateinische Rechtecke und Maschinenbelegung, Habilitationsschrift, TU Magdeburg, 1990. 
  2. 2. H. BRÄSEL and M. KLEINAU, On number problems for the open shop problem. System Modelling and Optimization, Proceedings of the 15th 1FIP Conference, Zurich, Switzerland, Springer-Verlag, 1992, pp. 145-155. Zbl0788.90037MR1182331
  3. 3. H. BRÄSEL, D. KLUGE and F. WERNER, A polynomial algorithm for the [ n/m/O, tij, tree/Cmax] open shop problem, European J. Oper. Res., 1994, 72, pp. 125-134. Zbl0798.90081
  4. 4. H. BRÄSEL, D. KLUGE and F. WERNER, A polynomial algorithm for an open shop problem with unit processing times and tree constraints, to appear 1994 in Discrete Applied Mathematics. Zbl0833.90066MR1326714
  5. 5. P. BRUCKER, B. JURISCH and M. JURISCH, Open shop problems with Unit time operations, ZOR, 1993, 37, pp. 59-73. Zbl0776.90033MR1213678
  6. 6. P. BRUCKER, B. JURISCH, T. TAUTENHAHN and F. WERNER, Scheduling unit time open shops to minimize the weighted number of late jobs, OR Letters, 1994, 14, pp. 245-250. Zbl0793.90028MR1264095
  7. 7. R. E. GRAHAM, E. L. LAWLWER and J. K. LENSTRA, Rinnooy Kan, A. H. G.: Optimization and approximation in deterministic sequencing and scheduling - a survey, Ann. Discrete Mathematics, 1979, 5, pp. 287-326. Zbl0411.90044MR558574
  8. 8. T. GONZALES and S. SAHNI, Open shop scheduling to minimize finish time, J. Assoc. Comput. Mach., 1976, 23, pp. 665-679. Zbl0343.68031MR429089
  9. 9. W. KUBIAK, C. SRISKANDARAJAH and K. ZARAS, A note on the complexity of open-shop scheduling problems, INFOR, 1991, 29, pp. 284-294. Zbl0778.90027
  10. 10. C. Y. Liu and R. L. BULFIN, Scheduling open shops with unit execution times to minimize functions of due dates, Operations Research, 1988, 36, No. 4, pp. 553-559. Zbl0652.90063MR960255
  11. 11. R. MCNAUGHTON, Scheduling with deadlines and loss functions, Management Science, 1959, 6, pp. 1-12. Zbl1047.90504MR110585
  12. 12. V. S. TANAEV, SOTSKOV, N. YU and V. A. STRUSEVICH, Scheduling theory. Multistage system, Kluwer Academie Publishers, 1994. Zbl0925.90224
  13. 13. T. TAUTENHAHNOpen-shop-Probleme mit Einheitsbearbeitungszeiten, Dissertation, Otto-von-Guericke-Universitàt, Magdeburg, 1993. 

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.