Parallel Machine Scheduling: Impact of Adding Extra Machines

Kabir Rustogi () and Vitaly A. Strusevich ()
Additional contact information
Kabir Rustogi: School of Computing and Mathematical Sciences, Old Royal Naval College, University of Greenwich, London SE10 9LS, United Kingdom
Vitaly A. Strusevich: School of Computing and Mathematical Sciences, Old Royal Naval College, University of Greenwich, London SE10 9LS, United Kingdom

Operations Research, 2013, vol. 61, issue 5, 1243-1257

Abstract: We consider the classical scheduling problems of processing jobs on identical parallel machines to minimize (i) the makespan (the maximum completion time) or (ii) the total flow time (the sum of the completion times). The focus of this study is on the impact that additional machines may have, if added to the system. We measure such a machine impact by the ratio of the value of the objective function computed with the original number of machines to the one computed with extra machines. We give tight bounds on the machine impact for the problem of minimizing the makespan, for both the preemptive and non-preemptive versions, as well as for the problem of minimizing the total flow time. We also present polynomial-time exact and approximation algorithms to make a cost-effective choice of the number of machines, provided that each machine incurs a cost and the objective function captures the trade-off between the cost of the used machines and a scheduling objective.

Keywords: production/scheduling: approximations/heuristic; production/scheduling: sequencing: deterministic: multiple machine (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2013.1208 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:61:y:2013:i:5:p:1243-1257

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().