Online scheduling with machine cost and a power function objective

Abstract

We will consider a power function variant of online scheduling with machine cost. Here, we have a sequence of independent jobs with positive real sizes. Jobs come one by one and we have to assign them irrevocably to a machine without any knowledge about additional jobs that may follow later on. With this problem the algorithm has no machine at first. When a job arrives, we have the option to purchase a new machine and the cost of purchasing a machine is a fixed constant. In previous studies, the objective was to minimize the sum of the makespan and the cost of the purchased machines. In this paper, we minimize the sum of the rth power of loads of the machines (r ≥ 2 is an integer) and the cost of purchasing the machines. The cost of a new machine is 1. We prove that no online algorithm has a competitive ratio smaller than 2 − 2r−1 2r −1 for this problem. Moreover, for r = 2, 3, 4 we present a 2 − 2r−1 2r −1 -competitive online algorithm with a detailed competitive analysis which applies the bin packing algorithm First Fit as a slave algorithm.