Resource Cost Aware Scheduling Problems

Rodrigo Carrasco

Resource Cost Aware Scheduling Problems
Carrasco, Rodrigo
Thesis Advisor(s):
Stein, Clifford
Industrial Engineering and Operations Research
Persistent URL:
Ph.D., Columbia University.
Managing the consumption of non-renewable and/or limited resources has become an important issue in many different settings. In this dissertation we explore the topic of resource cost aware scheduling. Unlike the purely scheduling problems, in the resource cost aware setting we are not only interested in a scheduling performance metric, but also the cost of the resources consumed to achieve a certain performance level. There are several ways in which the cost of non-renewal resources can be added into a scheduling problem. Throughout this dissertation we will focus in the case where the resource consumption cost is added, as part of the objective, to a scheduling performance metric such as weighted completion time and weighted tardiness among others. In our work we make several contributions to the problem of scheduling with non-renewable resources. For the specific setting in which only energy consumption is the important resource, our contributions are the following. We introduce a model that extends the previous energy cost models by allowing more general cost functions that can be job-dependent. We further generalize the problem by allowing arbitrary precedence constraints and release dates. We give approximation algorithms for minimizing an objective that is a combination of a scheduling metric, namely total weighted completion time and total weighted tardiness, and the total energy consumption cost. Our approximation algorithm is based on an interval-and-speed-indexed IP formulation. We solve the linear relaxation of this IP and we use this solution to compute a schedule. We show that these algorithms have small constant approximation ratios. Through experimental analysis we show that the empirical approximation ratios are much better than the theoretical ones and that in fact the solutions are close to optimal. We also show empirically that the algorithm can be used in additional settings not covered by the theoretical results, such as using flow time or an online setting, with good approximation and competitiveness ratios.
Industrial engineering
Applied mathematics
Item views
text | xml
Suggested Citation:
Rodrigo Carrasco, , Resource Cost Aware Scheduling Problems, Columbia University Academic Commons, .

Center for Digital Research and Scholarship at Columbia University Libraries | Policies