# 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:10.1007/978-3-540-87744-8_63)

## 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.

### Actions (login required)

View Item |