TY - JOUR

T1 - Resource cost aware scheduling

AU - Carrasco, Rodrigo A.

AU - Iyengar, Garud

AU - Stein, Cliff

N1 - Funding Information:
This research was partially supported by NSF grants CCF-0728733 and CCF-0915681 ; NSF grant DMS-1016571 , ONR grant N000140310514, and DOE grants DEFG02-08ER25856 and DE-AR0000235 ; Fulbright/Conicyt Chile, Fondecyt Project 1151098 , and Conicyt PIA Anillo ACT 1407.
Funding Information:
This research was partially supported by NSF grants CCF-0728733 and CCF-0915681; NSF grant DMS-1016571, ONR grant N000140310514, and DOE grants DEFG02-08ER25856 and DE-AR0000235; Fulbright/Conicyt Chile, Fondecyt Project 1151098, and Conicyt PIA Anillo ACT 1407.
Publisher Copyright:
© 2018 Elsevier B.V.

PY - 2018/9/1

Y1 - 2018/9/1

N2 - We are interested in the scheduling problem where there are several different resources that determine the speed at which a job runs and we pay depending on the amount of each resource that we use. This work is an extension of the resource dependent job processing time problem and the energy aware scheduling problems. We develop a new constant factor approximation algorithm for resource cost aware scheduling problems: the objective is to minimize the sum of the total cost of resources and the total weighted completion time in the one machine non-preemptive setting, allowing for arbitrary precedence constraints and release dates. Our algorithm handles general job-dependent resource cost functions. We also analyze the practical performance of our algorithms, showing that it is significantly superior to the theoretical bounds and in fact it is very close to optimal. The analysis is done using simulations and real instances, which are left publicly available for future benchmarks. We also present additional heuristic improvements and we study their performance in other settings.

AB - We are interested in the scheduling problem where there are several different resources that determine the speed at which a job runs and we pay depending on the amount of each resource that we use. This work is an extension of the resource dependent job processing time problem and the energy aware scheduling problems. We develop a new constant factor approximation algorithm for resource cost aware scheduling problems: the objective is to minimize the sum of the total cost of resources and the total weighted completion time in the one machine non-preemptive setting, allowing for arbitrary precedence constraints and release dates. Our algorithm handles general job-dependent resource cost functions. We also analyze the practical performance of our algorithms, showing that it is significantly superior to the theoretical bounds and in fact it is very close to optimal. The analysis is done using simulations and real instances, which are left publicly available for future benchmarks. We also present additional heuristic improvements and we study their performance in other settings.

KW - Approximation algorithms

KW - Resource aware scheduling

KW - Scheduling

KW - Speed-scaling

UR - http://www.scopus.com/inward/record.url?scp=85044289572&partnerID=8YFLogxK

U2 - 10.1016/j.ejor.2018.02.059

DO - 10.1016/j.ejor.2018.02.059

M3 - Article

AN - SCOPUS:85044289572

VL - 269

SP - 621

EP - 632

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 2

ER -