Please use this identifier to cite or link to this item: https://hdl.handle.net/10419/307628 
Year of Publication: 
2022
Citation: 
[Journal:] Central European Journal of Operations Research [ISSN:] 1613-9178 [Volume:] 31 [Issue:] 1 [Publisher:] Springer [Place:] Berlin, Heidelberg [Year:] 2022 [Pages:] 191-204
Publisher: 
Springer, Berlin, Heidelberg
Abstract: 
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=3or B=4resources are sufficient for a perfect schedule.
Subjects: 
Minimizing the number of resources
Perfect schedule
Single-processor scheduling
Mixed integer linear programming
Persistent Identifier of the first edition: 
Creative Commons License: 
cc-by Logo
Document Type: 
Article
Document Version: 
Published Version

Files in This Item:
File
Size





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.