Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

06.03.2020

Single machine scheduling to maximize the number of on-time jobs with generalized due-dates

Zeitschrift:
Journal of Scheduling
Autoren:
Enrique Gerstl, Gur Mosheiov
Wichtige Hinweise

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Abstract

In scheduling problems with generalized due dates (gdd), the due dates are specified according to their position in the sequence, and the j-th due date is assigned to the job in the j-th position. We study a single-machine problem with generalized due dates, where the objective is maximizing the number of jobs completed exactly on time. We prove that the problem is NP-hard in the strong sense. To our knowledge, this is the only example of a scheduling problem where the job-specific version has a polynomial-time solution, and the gdd version is strongly NP-hard. A branch-and-bound (B&B) algorithm, an integer programming (IP)-based procedure, and an efficient heuristic are introduced and tested. Both the B&B algorithm and the IP-based solution procedure can solve most medium-sized problems in a reasonable computational effort. The heuristic serves as the initial step of the B&B algorithm and in itself obtains the optimum in most cases. We also study two special cases: max-on-time for a given job sequence and max-on-time with unit-execution-time jobs. For both cases, polynomial-time dynamic programming algorithms are introduced, and large-sized problems are easily solved.

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

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

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

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

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

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




Testen Sie jetzt 30 Tage kostenlos.

Literatur
Über diesen Artikel

Premium Partner

    Bildnachweise