Shioura, Akiyoshi, Shakhlevich, Natalia V. and Strusevich, Vitaly (2016) Application of submodular optimization to single machine scheduling with controllable processing times subject to release dates and deadlines. INFORMS Journal on Computing, 28 (1). pp. 148-161. ISSN 1091-9856 (Print), 1526-5528 (Online) (doi:https://doi.org/10.1287/ijoc.2015.0660)

Preview

PDF (Publisher PDF) 15193_Strusevich_Application of submodular optimization (pub PDF OA) 2016.pdf - Published Version Available under License Creative Commons Attribution. Download (317kB) | Preview

Abstract

In this paper, we study a scheduling problem on a single machine, provided that the jobs have individual release dates and deadlines, and the processing times are controllable. The objective is to find a feasible schedule that minimizes the total cost of reducing the processing times. We reformulate the problem in terms of maximizing a linear function over a submodular polyhedron intersected with a box. For the latter problem of submodular optimization, we develop a recursive decomposition algorithm and apply it to solving the single machine scheduling problem to achieve the best possible running time.

Item Type:	Article
Additional Information:	'This work is licensed under a Creative Commons Attribution 4.0 International License. You are free to copy, distribute, transmit and adapt this work, but you must attribute this work as “INFORMS Journal on Computing. Copyright 2016 INFORMS. http://dx.doi.org/10.1287/ijoc.2015.0660, used under a Creative Commons Attribution License: http://creativecommons.org/licenses/by/4.0/.”'
Uncontrolled Keywords:	programming: linear; production scheduling: deterministic, single machine; analysis of algorithms: computational complexity
Faculty / School / Research Centre / Research Group:	Faculty of Liberal Arts & Sciences
Last Modified:	21 Apr 2017 10:48
URI:	http://gala.gre.ac.uk/id/eprint/15193

Actions (login required)

View Item

Downloads