On the minimum number of resources for a perfect schedule

  • In the single-processor scheduling problem with time restrictions there is one main processor and B resources that are used to execute the jobs. A perfect schedule has no idle times or gaps on the main processor and the makespan is therefore equal to the sum of the processing times. In general, more resources result in smaller makespans, and as it is in practical applications often more economic not to mobilize resources that will be unnecessary and expensive, we investigate in this paper the problem to find the smallest number B of resources that make a perfect schedule possible. We show that the decision version of this problem is NP-complete, derive new structural properties of perfect schedules, and we describe a Mixed Integer Linear Programming (MIP) formulation to solve the problem. A large number of computational tests show that (for our randomly chosen problem instances) only B=3 or B=4 resources are sufficient for a perfect schedule.

Volltext Dateien herunterladen

Metadaten exportieren

Metadaten
Verfasserangaben:Rachid Benmansour, Oliver BraunORCiD
URN:urn:nbn:de:hbz:tr5-1147
DOI:https://doi.org/10.1007/s10100-022-00803-7
Titel des übergeordneten Werkes (Englisch):Central European Journal of Operations Research
Verlag:Springer Nature
Dokumentart:Wissenschaftlicher Artikel (Fachzeitschriften)
Sprache:Englisch
Datum des OPUS-Uploads:03.09.2022
Datum der Erstveröffentlichung:26.05.2022
Veröffentlichende Hochschule:Hochschule Trier
Datum der Freischaltung:05.09.2022
Freies Schlagwort / Tag:minimizing the number of resources; mixed integer linear programming; perfect schedule; single-processor scheduling
GND-Schlagwort:Lineare Optimierung
Jahrgang:2022
Seitenzahl:14
Erste Seite:1
Letzte Seite:14
Einrichtungen:FB Umweltwirtschaft/-recht (UCB)
DDC-Klassifikation:3 Sozialwissenschaften / 33 Wirtschaft
5 Naturwissenschaften und Mathematik / 51 Mathematik
Lizenz (Deutsch):License LogoCreative Commons - CC BY - Namensnennung 4.0 International