Skip to main content

2013 | OriginalPaper | Buchkapitel

Lower and Upper Bounds for the Preemptive Single Machine Scheduling Problem with Equal Processing Times

verfasst von : Mikhail Batsyn, Boris Goldengorin, Pavel Sukhov, Panos M. Pardalos

Erschienen in: Models, Algorithms, and Technologies for Network Analysis

Verlag: Springer New York

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

search-config
loading …

Abstract

The preemptive single machine scheduling problem of minimizing the total weighted completion time with equal processing times and arbitrary release dates is one of the four single machine scheduling problems with an open computational complexity status. In this chapter we present lower and upper bounds for the exact solution of this problem based on the assignment problem. We also investigate properties of these bounds and worst-case behavior.

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!

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!

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!

Literatur
1.
Zurück zum Zitat Baker, K.R.: Introduction to Sequencing and Scheduling. Wiley, New York (1974), 305 pp. Baker, K.R.: Introduction to Sequencing and Scheduling. Wiley, New York (1974), 305 pp.
2.
3.
Zurück zum Zitat Bouma, H.W., Goldengorin, B.: A polytime algorithm based on a primal LP model for the scheduling problem 1|pmtn;p j =2;r j |∑w j C j . Proceedings of the 2010 American Conference on Applied Mathematics, AMERICAN-MATH’10, Stevens Point, Wisconsin, USA, pp. 415–420. World Scientific and Engineering Academy and Society (WSEAS) (2010) Bouma, H.W., Goldengorin, B.: A polytime algorithm based on a primal LP model for the scheduling problem 1|pmtn;p j =2;r j |∑w j C j . Proceedings of the 2010 American Conference on Applied Mathematics, AMERICAN-MATH’10, Stevens Point, Wisconsin, USA, pp. 415–420. World Scientific and Engineering Academy and Society (WSEAS) (2010)
4.
Zurück zum Zitat Brucker, P., Kravchenko, S.A.: Scheduling jobs with equal processing times and time windows on identical parallel machines. J. Sched. 11, 229–237 (2008) MathSciNetCrossRefMATH Brucker, P., Kravchenko, S.A.: Scheduling jobs with equal processing times and time windows on identical parallel machines. J. Sched. 11, 229–237 (2008) MathSciNetCrossRefMATH
5.
Zurück zum Zitat Goemans, M.X., Wein, J.M., Williamson, D.P.: A 1.47-approximation algorithm for a preemptive single-machine scheduling problem. Oper. Res. Lett. 26, 149–154 (2000) MathSciNetCrossRefMATH Goemans, M.X., Wein, J.M., Williamson, D.P.: A 1.47-approximation algorithm for a preemptive single-machine scheduling problem. Oper. Res. Lett. 26, 149–154 (2000) MathSciNetCrossRefMATH
6.
Zurück zum Zitat Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math., 5, 287–326 (1979) MathSciNetCrossRefMATH Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math., 5, 287–326 (1979) MathSciNetCrossRefMATH
7.
Zurück zum Zitat Herrman, J., Lee, C., Snowdon, J.: A classification of static scheduling problems. In: Pardalos, P.M. (ed.) Complexity in Numerical Optimization, pp. 203–253. World Scientific, Singapore (1993) CrossRef Herrman, J., Lee, C., Snowdon, J.: A classification of static scheduling problems. In: Pardalos, P.M. (ed.) Complexity in Numerical Optimization, pp. 203–253. World Scientific, Singapore (1993) CrossRef
8.
Zurück zum Zitat Labetoulle, J., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Preemptive scheduling of uniform machines subject to release dates. In: Progress in Combinatorial Optimization, pp. 245–261. Academic Press, Toronto (1984) Labetoulle, J., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Preemptive scheduling of uniform machines subject to release dates. In: Progress in Combinatorial Optimization, pp. 245–261. Academic Press, Toronto (1984)
9.
Zurück zum Zitat Lenstra, J.K., Rinnooy Kan, A.H.G., Brucker, P.: Complexity of machine scheduling problems. studies in integer programming. In: Hammer, P.L., Johnson, E.L., Korte, B.H., Nemhauser, G.L. (eds.) Annals of Discrete Mathematics, vol. 1, pp. 343–362. North-Holland, Amsterdam (1977) Lenstra, J.K., Rinnooy Kan, A.H.G., Brucker, P.: Complexity of machine scheduling problems. studies in integer programming. In: Hammer, P.L., Johnson, E.L., Korte, B.H., Nemhauser, G.L. (eds.) Annals of Discrete Mathematics, vol. 1, pp. 343–362. North-Holland, Amsterdam (1977)
10.
Zurück zum Zitat Pinedo, M.L.: Scheduling: Theory, Algorithms, and Systems, 4th edn. Springer, Berlin (2012), 673 pp. CrossRef Pinedo, M.L.: Scheduling: Theory, Algorithms, and Systems, 4th edn. Springer, Berlin (2012), 673 pp. CrossRef
11.
Zurück zum Zitat Smith, W.E.: Various optimizers for single-stage production. Nav. Res. Logist. Q. 3, 59–66 (1956) CrossRef Smith, W.E.: Various optimizers for single-stage production. Nav. Res. Logist. Q. 3, 59–66 (1956) CrossRef
Metadaten
Titel
Lower and Upper Bounds for the Preemptive Single Machine Scheduling Problem with Equal Processing Times
verfasst von
Mikhail Batsyn
Boris Goldengorin
Pavel Sukhov
Panos M. Pardalos
Copyright-Jahr
2013
Verlag
Springer New York
DOI
https://doi.org/10.1007/978-1-4614-8588-9_2