Resource Cost Aware Scheduling Problems

In our work we make several contributions to the problem of scheduling with non-renewable resources.;Theorem 0.1 Given n jobs with precedence constraints and release dates and a general non-negative resource cost function, there is an O(1)-approximation algorithm for the problem of non-preemptively minimizing a weighted sum of the completion time and resource cost..;The constants in the O(1) are modest. Given some epsilon > 0, the algorithm has a (4 + epsilon)-approximation ratio when only precedence constraints exist, and (3+2 2 + epsilon)-approximation ratio when release dates are added.;Because some of our algorithms use resource augmentation to deal with nonlinear scheduling performance metrics (like weighted tardiness), we can further extend the use of our algorithms to the setting where no resource cost is considered but a general convex non-decreasing scheduling performance metric is used. We make several contributions to the problem of scheduling jobs with non-decreasing convex cost functions: · We introduce a model that extends the previous models by allowing a more general non-linear job-dependent function of the completion time as the scheduling metric. · We propose a new approximation algorithm for minimizing the total cost, with arbitrary precedence constraints. · Our algorithm builds on both the alpha-point and resource augmentation techniques. We show that our algorithm has a small constant approximation ratio and a small speed-scaling ratio for several important scheduling metrics, namely the total weighted tardiness, the total weighted tardiness squared, and the total completion time squared. The results of our numerical experiments show that the practical performance of our algorithm is significantly superior to the theoretical bounds. · We compare the performance of our algorithm with other available methods for the total weighted tardiness problem by using the test instances from the OR Library. We show that our algorithm is capable of computing approximate optimal solutions for all the available test problems, even those with n = 100 jobs. Thus, we are able to establish lower bounds on the optimal solutions for instances where the optimal schedule is currently not known. Our algorithm takes less than a second to solve even the larger instances (with n = 100 jobs), which is at least one order of magnitude faster than current methods. Furthermore, we show that on average only a 2% speed-up is required to achieve the best known result; and, in fact, in several cases no speed-up factor is required.;Theorem 0.2 Given n jobs with arbitrary precedence constraints and convex non-decreasing cost functions fi(C i) for each job i, there is a O(1)-speed 1-approximation algorithm for the problem of minimizing the total non-linear cost fi(Ci)..;The speed scaling constant is relatively small. Given epsilon > 0 our algorithm is a (4 + epsilon)-speed ;Finally, we also consider the energy aware scheduling problem in which the size of a job is only known after the machine finishes processing it, but only the size probability distribution is known in advance. This is a common setting in CPUs. We also make several contributions to this particular setting. · We propose a dynamic programming formulation which is optimal in expectation. · We compute the optimal speeds required, given any state in the dynamic programming recursion. · We present a policy for the case where the completion time is the scheduling performance metric, and show that this policy is optimal when only two possible sizes exist. · We leave as an open conjecture that our policy is also optimal for the case with arbitrary job sizes, since we are only able to show through simulations that this is true in all the tested instances. (Abstract shortened by UMI.).