TY - JOUR

T1 - The local–global conjecture for scheduling with non-linear cost

AU - Bansal, N.

AU - Dürr, C.

AU - Thang, N.K.K.

AU - Vásquez, Ó.C.

PY - 2017/6/1

Y1 - 2017/6/1

N2 - We consider the classical scheduling problem on a single machine, on which we need to schedule sequentially n given jobs. Every job j has a processing time pj and a priority weight wj, and for a given schedule a completion time Cj. In this paper, we consider the problem of minimizing the objective value ∑jwjCjβ for some fixed constant β> 0. This non-linearity is motivated for example by the learning effect of a machine improving its efficiency over time, or by the speed scaling model. For β= 1 , the well-known Smith’s rule that orders job in the non-increasing order of wj/ pj gives the optimum schedule. However, for β≠ 1 , the complexity status of this problem is open. Among other things, a key issue here is that the ordering between a pair of jobs is not well defined, and might depend on where the jobs lie in the schedule and also on the jobs between them. We investigate this question systematically and substantially generalize the previously known results in this direction. These results lead to interesting new dominance properties among schedules which lead to huge speed up in exact algorithms for the problem. An experimental study evaluates the impact of these properties on the exact algorithm A*.

AB - We consider the classical scheduling problem on a single machine, on which we need to schedule sequentially n given jobs. Every job j has a processing time pj and a priority weight wj, and for a given schedule a completion time Cj. In this paper, we consider the problem of minimizing the objective value ∑jwjCjβ for some fixed constant β> 0. This non-linearity is motivated for example by the learning effect of a machine improving its efficiency over time, or by the speed scaling model. For β= 1 , the well-known Smith’s rule that orders job in the non-increasing order of wj/ pj gives the optimum schedule. However, for β≠ 1 , the complexity status of this problem is open. Among other things, a key issue here is that the ordering between a pair of jobs is not well defined, and might depend on where the jobs lie in the schedule and also on the jobs between them. We investigate this question systematically and substantially generalize the previously known results in this direction. These results lead to interesting new dominance properties among schedules which lead to huge speed up in exact algorithms for the problem. An experimental study evaluates the impact of these properties on the exact algorithm A*.

KW - Algorithm A

KW - Non-linear cost function

KW - Pruning rules

KW - Scheduling

KW - Single machine

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

U2 - 10.1007/s10951-015-0466-5

DO - 10.1007/s10951-015-0466-5

M3 - Article

AN - SCOPUS:84954437561

SN - 1094-6136

VL - 20

SP - 239

EP - 254

JO - Journal of Scheduling

JF - Journal of Scheduling

IS - 3

ER -