Shioura, Akiyoshi, Shakhlevich, Natalia V. and Strusevich, Vitaly A. (2013) A submodular optimization approach to bicriteria scheduling problems with controllable processing times on parallel machines. SIAM Journal on Discrete Mathematics, 27 (1). pp. 186-204. ISSN 0895-4801 (Print), 1095-7146 (Online) (doi:10.1137/110843836)

Full text not available from this repository.

Abstract

In this paper, we present a general methodology for designing polynomial-time algorithms for bicriteria scheduling problems on parallel machines with controllable processing times. For each considered problem, the two criteria are the makespan and the total compression cost, and the solution is delivered in the form of the break points of the efficient frontier. We reformulate the scheduling problems in terms of optimization over submodular polyhedra and give efficient procedures for computing the corresponding rank functions. As a result, for two of the considered problems we obtain the first polynomial-time algorithms, while for the third problem we considerably improve the known running time.

Item Type:	Article
Additional Information:	CMS Ref: 13/22
Uncontrolled Keywords:	submodular optimization, parallel machine scheduling, controllable processing times, bicriteria problems
Subjects:	Q Science > QA Mathematics
Pre-2014 Departments:	School of Computing & Mathematical Sciences
Related URLs:	Publisher Organisation Organisation
Last Modified:	14 Oct 2016 09:24
URI:	http://gala.gre.ac.uk/id/eprint/10123

Actions (login required)

View Item