Skip navigation

Decomposition algorithms for submodular optimization with applications to parallel machine scheduling with controllable processing times

Decomposition algorithms for submodular optimization with applications to parallel machine scheduling with controllable processing times

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)

[img]
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 / Department / Research Group: Faculty of Architecture, Computing & Humanities
Faculty of Architecture, Computing & Humanities > Department of Mathematical Sciences
Last Modified: 21 Apr 2017 10:48
Selected for GREAT 2016: GREAT a
Selected for GREAT 2017: None
Selected for GREAT 2018: None
URI: http://gala.gre.ac.uk/id/eprint/15195

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics