Skip navigation

Fast divide-and-conquer algorithms for preemptive scheduling problems with controllable processing times - a polymatroid optimization approach

Fast divide-and-conquer algorithms for preemptive scheduling problems with controllable processing times - a polymatroid optimization approach

Shakhlevich, Natalia V., Shioura, Akiyoshi and Strusevich, Vitaly A. (2008) Fast divide-and-conquer algorithms for preemptive scheduling problems with controllable processing times - a polymatroid optimization approach. In: Algorithms – ESA 2008 : 16th Annual European Symposium, Karlsruhe, Germany, September 15-17, 2008. Proceedings. Lecture Notes in Computer Science (5193). Springer Verlag, Berlin/Heidelberg, Germany, pp. 756-767. ISBN 978-3-540-87743-1 (doi:https://doi.org/10.1007/978-3-540-87744-8_63)

Full text not available from this repository.

Abstract

We consider a variety of preemptive scheduling problems with controllable processing times on a single machine and on identical/uniform parallel machines, where the objective is to minimize the total compression cost. In this paper, we propose fast divide-and-conquer algorithms for these scheduling problems. Our approach is based on the observation that each scheduling problem we discuss can be formulated as a polymatroid optimization problem. We develop a novel divide-and-conquer technique for the polymatroid optimization problem and then apply it to each scheduling problem. We show that each scheduling problem can be solved in $ \O({\rm T}_{\rm feas}(n) \times\log n)$ time by using our divide-and-conquer technique, where n is the number of jobs and Tfeas(n) denotes the time complexity of the corresponding feasible scheduling problem with n jobs. This approach yields faster algorithms for most of the scheduling problems discussed in this paper.

Item Type: Conference Proceedings
Title of Proceedings: Algorithms – ESA 2008 : 16th Annual European Symposium, Karlsruhe, Germany, September 15-17, 2008. Proceedings
Additional Information: [1] This paper was first presented at the 16th Annual European Symposium on Algorithms (ESA 2008), held from 15-17 September 2008 in Karlsruhe, Germany.
Uncontrolled Keywords: polymatroid optimization, divide-and-conquer algorithm, scheduling
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
URI: http://gala.gre.ac.uk/id/eprint/1214

Actions (login required)

View Item View Item