Skip navigation

Preemptive scheduling on uniform parallel machines with controllable job processing times

Preemptive scheduling on uniform parallel machines with controllable job processing times

Shakhlevich, Natalia V. and Strusevich, Vitaly A. (2007) Preemptive scheduling on uniform parallel machines with controllable job processing times. Algorithmica, 51 (4). pp. 451-473. ISSN 0178-4617 (Print), 1432-0541 (Online) (doi:https://doi.org/10.1007/s00453-007-9091-9)

Full text not available from this repository.

Abstract

In this paper, we provide a unified approach to solving preemptive scheduling problems with uniform parallel machines and controllable processing times. We demonstrate that a single criterion problem of minimizing total compression cost subject to the constraint that all due dates should be met can be formulated in terms of maximizing a linear function over a generalized polymatroid. This justifies applicability of the greedy approach and allows us to develop fast algorithms for solving the problem with arbitrary release and due dates as well as its special case with zero release dates and a common due date. For the bicriteria counterpart of the latter problem we develop an efficient algorithm that constructs the trade-off curve for minimizing the compression cost and the makespan.

Item Type: Article
Additional Information: [1] Published online: 18 October 2007
Uncontrolled Keywords: uniform parallel machine scheduling, controllable processing times, generalized polymatroid, maximum flow
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Pre-2014 Departments: School of Computing & Mathematical Sciences
School of Computing & Mathematical Sciences > Department of Mathematical Sciences
School of Computing & Mathematical Sciences > Statistics & Operational Research Group
Related URLs:
Last Modified: 14 Oct 2016 09:03
Selected for GREAT 2016: None
Selected for GREAT 2017: None
Selected for GREAT 2018: None
URI: http://gala.gre.ac.uk/id/eprint/1325

Actions (login required)

View Item View Item