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

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 |

School / Department / Research Groups: | 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: | 23 Oct 2012 14:39 |

URI: | http://gala.gre.ac.uk/id/eprint/1214 |

### Actions (login required)

View Item |