Rustogi, Kabir and Strusevich, Vitaly A. (2013) Parallel machine scheduling: Impact of adding extra machines. Operations Research, 61 (5). pp. 1243-1257. ISSN 0030-364X (Print), 1526-5463 (Online) (doi:https://doi.org/10.1287/opre.2013.1208)

Full text not available from this repository.

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.

Item Type:	Article
Uncontrolled Keywords:	production/scheduling, approximations/heuristic, production/scheduling, sequencing, deterministic, multiple machine
Subjects:	Q Science > QA Mathematics
Pre-2014 Departments:	School of Computing & Mathematical Sciences
Related URLs:	Publisher
Last Modified:	14 Oct 2016 09:25
URI:	http://gala.gre.ac.uk/id/eprint/10695

Actions (login required)

View Item