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:	Publisher Organisation
Last Modified:	14 Oct 2016 09:03
URI:	http://gala.gre.ac.uk/id/eprint/1214

Actions (login required)

View Item