Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Introduction Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

5. Parallel Machine Models (Deterministic)

verfasst von : Michael L. Pinedo

Erschienen in: Scheduling

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

A bank of machines in parallel is a setting that is important from both a theoretical and a practical point of view. From a theoretical point of view it is a generalization of the single machine, and a special case of the flexible flow shop. From a practical point of view, it is important because the occurrence of resources in parallel is common in the real world. Also, techniques for machines in parallel are often used in decomposition procedures for multi-stage systems.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Advanced Single Machine Models (Deterministic)
Nächstes Kapitel Flow Shops and Flexible Flow Shops (Deterministic)
Literatur
J. Bruno and T. Gonzalez (1976) “Scheduling Independent Tasks with Release Dates and Due Dates on Parallel Machines”, Technical Report 213, Computer Science Department, Pennsylvania State University.
N.-F. Chen and C.L. Liu (1975) “On a Class of Scheduling Algorithms for Multiprocessors Computing Systems”, in Parallel Processing, T.-Y. Feng (ed.), Lecture Notes in Computer Science, No. 24, pp. 1–16, Springer Verlag, Berlin.
Z.-L. Chen and W.B. Powell (1999) “Solving Parallel Machine Scheduling Problems by Column Generation”, INFORMS Journal of Computing, Vol. 11, pp. 78–94.CrossRefMathSciNetMATH
E.G. Coffman, Jr., M.R. Garey and D.S. Johnson (1978) “An Application of Bin-Packing to Multiprocessor Scheduling”, SIAM Journal of Computing, Vol. 7, pp. 1–17.CrossRefMathSciNetMATH
R.W. Conway, W.L. Maxwell, L.W. Miller (1967) Theory of Scheduling, Addison-Wesley, Reading, MA.MATH
E. Davis and J.M. Jaffe (1981) “Algorithms for Scheduling Tasks on Unrelated Processors”, Journal of the Association of Computing Machinery, Vol. 28, pp. 721–736.CrossRefMathSciNetMATH
G. Dobson (1984) “Scheduling Independent Tasks on Uniform Processors”, SIAM Journal of Computing, Vol. 13, pp. 705–716.CrossRefMathSciNetMATH
J. Du and J.Y.-T. Leung (1989) “Scheduling Tree-Structured Tasks on Two Processors to Minimize Schedule Length“, SIAM Journal of Discrete Mathematics, Vol. 2, pp. 176–196.CrossRefMathSciNetMATH
J. Du, J.Y.-T. Leung and G.H. Young (1990) “Minimizing Mean Flow Time with Release Time Constraint”, Theoretical Computer Science, Vol. 75, pp. 347–355.CrossRefMathSciNetMATH
J. Du, J.Y.-T. Leung and G.H. Young (1991) “Scheduling Chain-Structured Tasks to Minimize Makespan and Mean Flow Time”, Information and Computation, Vol. 92, pp. 219–236.CrossRefMathSciNetMATH
B. Eck and M. Pinedo (1993) “On the Minimization of the Makespan Subject to Flow Time Optimality”, Operations Research, Vol. 41, pp. 797–800.CrossRefMATH
S.E. Elmaghraby and S.H. Park (1974) “Scheduling Jobs on a Number of Identical Machines”, AIIE Transactions, Vol. 6, pp. 1–12.CrossRefMathSciNet
A. Federgruen and H. Groenevelt (1986) “Preemptive Scheduling of Uniform Machines by Ordinary Network Flow Techniques”, Management Science, Vol. 32, pp. 341–349.CrossRefMathSciNetMATH
S. French (1982) Sequencing and Scheduling: an Introduction to the Mathematics of the Job Shop, Horwood, Chichester, England.MATH
D.K. Friesen (1984a) “Tighter Bounds for the Multifit Processor Scheduling Algorithm”, SIAM Journal of Computing, Vol. 13, pp. 170–181.CrossRefMathSciNetMATH
D.K. Friesen (1984b) “Tighter Bounds for LPT Scheduling on Uniform Processors”, SIAM Journal of Computing, Vol. 16, pp. 554–560.CrossRefMathSciNet
D.K. Friesen and M.A. Langston (1983) “Bounds for Multifit Scheduling on Uniform Processors”, SIAM Journal of Computing, Vol. 12, pp. 60–70.CrossRefMathSciNetMATH
M.R. Garey, D.S. Johnson, B.B. Simons and R.E. Tarjan (1981) “Scheduling Unit-Time Tasks with Arbitrary Release Times and Deadlines”, SIAM Journal of Computing, Vol. 10, pp. 256–269.CrossRefMathSciNetMATH
T. Gonzalez, J.Y.-T. Leung and M. Pinedo (2006) “Minimizing Total Completion Time on Uniform Machines with Deadline Constraints”, ACM Transactions on Algorithms, Vol. 2, pp. 95–115.CrossRefMathSciNet
T. Gonzalez and S. Sahni (1978a) “Preemptive Scheduling of Uniform Processor Systems”, Journal of the Association of Computing Machinery, Vol. 25, pp. 92–101.CrossRefMathSciNetMATH
R.L. Graham (1966) “Bounds for Certain Multiprocessing Anomalies”, Bell System Technical Journal, Vol. 45, pp. 1563–1581.CrossRef
R.L. Graham (1969) “Bounds on Multiprocessing Timing Anomalies”, SIAM Journal of Applied Mathematics, Vol. 17, pp. 263–269.
E. Horowitz and S. Sahni (1976) “Exact and Approximate Algorithms for Scheduling Nonidentical Processors”, Journal of the Association of Computing Machinery, Vol. 23, pp. 317–327.CrossRefMathSciNetMATH
E.C. Horvath, S. Lam and R. Sethi (1977) “A Level Algorithm for Preemptive Scheduling”, Journal of the Association of Computing Machinery, Vol. 24, pp. 32–43.CrossRefMathSciNetMATH
T.C. Hu (1961) “Parallel Sequencing and Assembly Line Problems”, Operations Research, Vol. 9, pp. 841–848.CrossRefMathSciNet
H.-C. Hwang, K. Lee, and S.Y. Chang (2005) “The Effect of Machine Availability on the Worst-Case Performance of LPT”, Discrete Applied Mathematics, Vol. 148, pp. 49–61.CrossRefMathSciNetMATH
T. Kawaguchi and S. Kyan (1986) “Worst Case Bound of an LRF Schedule for the Mean Weighted Flow Time Problem”, SIAM Journal of Computing, Vol. 15, pp. 1119–1129.CrossRefMathSciNetMATH
M. Kunde (1976) “Beste Schranken Beim LP-Scheduling”, Bericht 7603, Institut für Informatik and und Praktische Mathematik, Universität Kiel.
J. Labetoulle, E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan (1984) “Preemptive Scheduling of Uniform Machines subject to Release Dates”, in Progress in Combinatorial Optimization, W.R. Pulleyblank (ed.), pp. 245–261, Academic Press, NY.
E.L. Lawler and J. Labetoulle (1978) “On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming”, Journal of the Association of Computing Machinery, Vol. 25, pp. 612–619.CrossRefMathSciNetMATH
E.L. Lawler and C.U. Martel (1989) “Preemptive Scheduling of Two Uniform Machines to Minimize the Number of Late Jobs”, Operations Research, Vol. 37, pp. 314–318.CrossRefMathSciNetMATH
C.-Y. Lee and J.D. Massey (1988) “Multi-Processor Scheduling: Combining LPT and MULTIFIT”, Discrete Applied Mathematics, Vol. 20, pp. 233–242.CrossRefMathSciNetMATH
K. Lee, J. Y.-T. Leung, and M. Pinedo (2010) “Makespan Minimization in Online Scheduling with Machine Eligibility”, 4OR, Vol. 8, pp. 331–364.CrossRefMathSciNetMATH
K. Lee, J. Y.-T. Leung, and M. Pinedo (2011) “Scheduling Jobs with Equal Processing Times subject to Machine Eligibility Constraints”, Journal of Scheduling, Vol. 14, pp. 27–38.CrossRefMathSciNetMATH
Y.H. Lee and M. Pinedo (1997) “Scheduling Jobs on Parallel Machines with Sequence-Dependent Setup Times”, European Journal of Operational Research, Vol. 100, pp. 464–474.CrossRefMATH
J.K. Lenstra and A.H.G. Rinnooy Kan (1978) “Computational Complexity of Scheduling under Precedence Constraints”, Operations Research, Vol. 26, pp. 22–35.CrossRefMathSciNetMATH
J.Y.-T. Leung and C.-L. Li (2008) “Scheduling with Processing Set Restrictions: A Survey”, International Journal of Production Economics, Vol. 116, pp. 251–262.CrossRef
J.Y.-T. Leung and M. Pinedo (2003) “Minimizing Total Completion Time on Parallel Machines with Deadline Constraints”, SIAM Journal of Computing, Vol. 32, pp. 1370–1388.CrossRefMathSciNetMATH
J.Y.-T. Leung and M. Pinedo (2004) “Scheduling Jobs on Parallel Machines that are subject to Breakdowns”, Naval Research Logistics, Vol. 51, pp. 60–71.CrossRefMathSciNetMATH
C.-L. Li (2006) “Scheduling Unit-Length Jobs with Machine Eligibility Restrictions”, European Journal of Operational Research, Vol. 174, pp. 1325–1328.CrossRefMATH
Y. Lin and W. Li (2004) “Parallel Machine Scheduling of Machine-Dependent Jobs with Unit-Length”, European Journal of Operational Research, Vol. 156, pp. 261–266.CrossRefMathSciNetMATH
C.U. Martel (1982) “Preemptive Scheduling with Release Times, Deadlines and Due Times”, Journal of the Association of Computing Machinery, Vol. 29, pp. 812–829.CrossRefMathSciNetMATH
T. Matsumoto (1992) “Competitive Analysis of the Round Robin Algorithm”, in Proceedings of 3rd International Symposium on Algorithms and Computation (ISAAC), Lecture Notes in Computer Science (LNCS), Vol. 650, pp. 71–77, Springer.
S.T. McCormick and M. Pinedo (1995) “Scheduling n Independent Jobs on m Uniform Machines with both Flow Time and Makespan Objectives: a Parametric Analysis,” ORSA Journal of Computing, Vol. 7, pp. 63–77.CrossRefMATH
R. Motwani, S. Phillips, and E. Torng (1994) “Nonclairvoyant Scheduling”, Theoretical Computer Science, Vol. 130, pp. 17–47.CrossRefMathSciNetMATH
K. Pruhs, J. Sgall, and E. Torng (2004) “Online Scheduling”, Chapter 15 in Handbook of Scheduling, J. Y-T. Leung (ed.), Chapman and Hall/CRC, Boca Raton, Florida.
S. Sahni and Y. Cho (1979b) “Scheduling Independent Tasks with Due Times on a Uniform Processor System”, Journal of the Association of Computing Machinery, Vol. 27, pp. 550–563.CrossRefMathSciNet
S.C. Sarin, S. Ahn and A.B. Bishop (1988) “An Improved Branching Scheme for the Branch and Bound Procedure of Scheduling n Jobs on m Machines to Minimize Total Weighted Flow Time”, International Journal of Production Research, Vol. 26, pp. 1183–1191.CrossRefMATH
U. Schwiegelshohn (2011) “An Alternative Proof of the Kawaguchi-Kyan Bound for the Largest-Ratio-First Rule”, Operations Research Letters, Vol. 39.
R. Sethi (1977) “On the Complexity of Mean Flow Time Scheduling”, Mathematics of Operations Research, Vol. 2, pp. 320–330.CrossRefMathSciNetMATH
J. Sgall (1998) “On-line Scheduling”, Chapter 9 in Online Algorithms: The State of the Art, A. Fiat and G. Woeginger (eds.), Lecture Notes in Computer Science, No. 1442, Springer Verlag, Berlin.
D.B. Shmoys, J. Wein and D.P. Williamson (1995) “Scheduling Parallel Machines On-line”, SIAM Journal of Computing, Vol. 24, pp. 1313–1331.CrossRefMathSciNetMATH
B. Simons (1983) “Multiprocessor Scheduling of Unit-Time Jobs with Arbitrary Release Times and Deadlines”, SIAM Journal of Computing, Vol. 12, pp. 294–299.CrossRefMathSciNetMATH
J.M. Van den Akker, J.A. Hoogeveen, and S.L. Van de Velde (1999) “Parallel Machine Scheduling by Column Generation”, Operations Research, Vol. 47, pp. 862–872.CrossRefMathSciNetMATH
Metadaten
Titel
Parallel Machine Models (Deterministic)
verfasst von
Michael L. Pinedo
Copyright-Jahr
2016
Buch
Scheduling

Print ISBN: 978-3-319-26578-0

Electronic ISBN: 978-3-319-26580-3

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-26580-3_5

Premium Partner

    Bildnachweise