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

Nikhil Bansal (), Christoph Dürr (), Nguyen Kim Thang () and Óscar C. Vásquez ()
Additional contact information
Nikhil Bansal: Eindhoven University of Technology
Christoph Dürr: Sorbonne Universités, UPMC Univ Paris 06, LIP6, CNRS, UMR 7606
Nguyen Kim Thang: University Evry Val d’Essonne
Óscar C. Vásquez: Universidad de Santiago

Journal of Scheduling, 2017, vol. 20, issue 3, No 2, 239-254

Abstract: Abstract 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 $$p_j$$ p j and a priority weight $$w_j$$ w j , and for a given schedule a completion time $$C_j$$ C j . In this paper, we consider the problem of minimizing the objective value $$\sum _j w_j C_j^\beta $$ ∑ j w j C j β for some fixed constant $$\beta >0$$ β > 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 $$\beta =1$$ β = 1 , the well-known Smith’s rule that orders job in the non-increasing order of $$w_j/p_j$$ w j / p j gives the optimum schedule. However, for $$\beta \ne 1$$ β ≠ 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*.

Keywords: Scheduling; Single machine; Non-linear cost function; Pruning rules; Algorithm A* (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10951-015-0466-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:20:y:2017:i:3:d:10.1007_s10951-015-0466-5

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-015-0466-5

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().