Shioura, Akiyoshi, Shakhlevich, Natalia V. and Strusevich, Vitaly A. (2015) Decomposition algorithms for submodular optimization with applications to parallel machine scheduling with controllable processing times. Mathematical Programming, 153 (2). pp. 495-534. ISSN 0025-5610 (Print), 1436-4646 (Online) (doi:10.1007/s10107-014-0814-9)

Preview

PDF (Publisher PDF) 15195_Strusevich_Decomposition algorithms for submodular optimization (pub PDF OA) 2015.pdf - Published Version Available under License Creative Commons Attribution. Download (533kB) | Preview

Abstract

In this paper we present a decomposition algorithm for maximizing a linear function over a submodular polyhedron intersected with a box. Apart from this contribution to submodular optimization, our results extend the toolkit available in deterministic machine scheduling with controllable processing times. We demonstrate how this method can be applied to developing fast algorithms for minimizing total compression cost for preemptive schedules on parallel machines with respect to given release dates and a common deadline. Obtained scheduling algorithms are faster and easier to justify than those previously known in the scheduling literature.

Item Type:	Article
Additional Information:	© The Author(s) 2014. This article is published with open access at Springerlink.com
Uncontrolled Keywords:	Submodular optimization, Parallel machine scheduling, Controllable processing times, Decomposition
Subjects:	Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Faculty / School / Research Centre / Research Group:	Faculty of Engineering & Science > School of Computing & Mathematical Sciences (CMS) Faculty of Engineering & Science
Last Modified:	04 Mar 2022 13:07
URI:	http://gala.gre.ac.uk/id/eprint/15195

Actions (login required)

View Item

Downloads