Parallel machine scheduling: Impact Of adding extra machines

摘要

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.