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
Journal of Scheduling
Erschienen in: Journal of Scheduling 4/2019

18.08.2018

Preemptive parallel-machine scheduling problem of maximizing the number of on-time jobs

verfasst von: Hui-Chih Hung, Bertrand M. T. Lin, Marc E. Posner, Jun-Min Wei

Erschienen in: Journal of Scheduling | Ausgabe 4/2019

Einloggen

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

search-config
loading …

Abstract

This paper investigates the classical preemptive parallel-machine scheduling problem of maximizing number of on-time jobs. While the problem is known to be NP-hard, no theoretical analysis of approximation algorithms exists in the literature. As part of the analysis, a new non-standard mixed integer formulation is developed. We propose heuristics based on different design strategies. These heuristics have asymptotically tight relative errors of 1/2. Experimental tests evaluate the computational performance of the procedures.
Vorheriger Artikel Malleable scheduling for flows of jobs and applications to MapReduce
Nächster Artikel Parallel machine makespan minimization subject to machine availability and total completion time constraints

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 "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
Literatur
Błażewicz, J., Ecker, K. H., Pesch, E., Schmidt, G., & Wȩglarz, J. (2007). Handbook on scheduling: From theory to applications. Berlin: Springer.
Chen, B., Potts, C. N., & Woeginger, G. J. (1998). A review of machine scheduling: Complexity, algorithms and approximability. In Handbook of combinatorial optimization (pp. 1493–1641). New York: Springer.
Cheng, T. C. E., & Sin, C. C. (1990). A state-of-the-art review of parallel-machine scheduling research. European Journal of Operational Research, 47(3), 271–292.CrossRef
Galvin, P. B., Gagne, G., & Silberschatz, A. (2013). Operating system concepts. New York: Wiley.
Graham, R. L., Lawler, E. L., Lenstra, J. K., & Rinnoy Kan, A. H. G. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5, 287–326.CrossRef
Garey, M. R., & Johnson, D. S. (1978). “Strong” NP-completeness results: motivation, examples, and implications. Journal of the Association of Computing Machinery, 25(3), 499–508.CrossRef
Ibarra, O. H., & Kim, C. E. (1978). Approximation algorithms for certain scheduling problems. Mathematics of Operations Research, 3(3), 197–204.CrossRef
Lawler, E. L. (1979). Preemptive scheduling of uniform parallel machines to minimize the weighted number of late jobs. Report BW 105, Centre for Mathematics and Computer Science, Amsterdam.
Lawler, E. L. (1983). Recent results in the theory of machine scheduling. In A. Bachem, M. Groetschel, & B. Korte (Eds.), Mathematical programming: The State of the Art (Bonn, 1982) (pp. 202–234). Berlin: Springer.CrossRef
Lawler, E. L., & Martel, C. U. (1989). Preemptive scheduling of two uniform machines to minimize the number of late jobs. Operations Research, 37(2), 314–318.CrossRef
Lee, K., Leung, J. Y. T., Jia, Z. H., Li, W., Pinedo, M. L., & Lin, B. M. T. (2014). Fast approximation algorithms for bi-criteria scheduling with machine assignment costs. European Journal of Operational Research, 238(1), 54–64.CrossRef
Leung, J. Y. (Ed.). (2004). Handbook of scheduling: Algorithms, models, and performance analysis. Boca Raton, FL: CRC Press.
McNaughton, R. (1959). Scheduling with deadlines and loss functions. Management Science, 6(1), 1–12.CrossRef
Mokotoff, E. (2001). Parallel machine scheduling problems: A survey. Asia-Pacific Journal of Operational Research, 18, 193–242.
Moore, J. M. (1968). An \(n\) job, one machine sequencing algorithm for minimizing the number of late jobs. Management Science, 15(1), 102–109.CrossRef
Pinedo, M. L. (2015). Scheduling: Theory, algorithms, and systems. New York: Springer.
Prot, D., Bellenguez-Morineau, O., & Lahlou, C. (2013). New complexity results for parallel identical machine scheduling problems with preemption, release dates and regular criteria. European Journal of Operational Research, 231(3), 282–287.CrossRef
Sahni, S., & Cho, Y. (1980). Scheduling independent tasks with due time on a uniform processor system. Journal of the Association for Computing Machinery, 27(3), 550–563.CrossRef
Singh, S., & Chana, J. (2016). A survey on resource scheduling in cloud computing: Issues and challenges. Journal of Grid Computing, 14(2), 217–264.CrossRef
Sturm, L. B. J. M. (1970). A simple optimality proof of Moore’s sequencing algorithm. Management Science, 17(1), 116–118.CrossRef
Tanenbaum, A. S., & Bos, H. (2014). Modern Operating Systems. New Jersey: Prentice Hall Press.
Tucker, A., & Gupta, A. (1989). Process control and scheduling issues for multiprogrammed shared-memory multiprocessors. ACM SIGOPS Operating Systems Review, 23(5), 159–166.CrossRef
Metadaten
Titel
Preemptive parallel-machine scheduling problem of maximizing the number of on-time jobs
verfasst von
Hui-Chih Hung
Bertrand M. T. Lin
Marc E. Posner
Jun-Min Wei
Publikationsdatum
18.08.2018
Verlag
Springer US
Erschienen in
Journal of Scheduling / Ausgabe 4/2019
Print ISSN: 1094-6136
Elektronische ISSN: 1099-1425
DOI
https://doi.org/10.1007/s10951-018-0584-y

Weitere Artikel der Ausgabe 4/2019

Journal of Scheduling 4/2019 Zur Ausgabe

OriginalPaper

Unbounded parallel-batch scheduling with drop-line tasks

OriginalPaper

Malleable scheduling for flows of jobs and applications to MapReduce

OriginalPaper

Parallel machine makespan minimization subject to machine availability and total completion time constraints

OriginalPaper

Quality of strong equilibria for selfish bin packing with uniform cost sharing

OriginalPaper

Lower bounds for online bin covering-type problems

OriginalPaper

The single-processor scheduling problem with time restrictions: complexity and related problems

Premium Partner

    Bildnachweise