Order Scheduling Models: Hardness and Algorithms

Garg, Naveen ; Kumar, Amit ; Pandit, Vinayaka (2007) Order Scheduling Models: Hardness and Algorithms Lecture Notes in Computer Science, 4855 . pp. 96-107. ISSN 0302-9743

Full text not available from this repository.

Official URL: http://doi.org/10.1007/978-3-540-77050-3_8

Related URL: http://dx.doi.org/10.1007/978-3-540-77050-3_8


We consider scheduling problems in which a job consists of components of different types to be processed on m machines. Each machine is capable of processing components of a single type. Different components of a job are independent and can be processed in parallel on different machines. A job is considered as completed only when all its components have been completed. We study both completion time and flowtime aspects of such problems. We show both lowerbounds and upperbounds for the completion time problem. We first show that even the unweighted completion time with single release date is MAX-SNP hard. We give an approximation algorithm based on linear programming which has an approximation ratio of 3 for weighted completion time with multiple release dates. We give online algorithms for the weighted completion time which are constant factor competitive. For the flowtime, we give only lowerbounds in both the offline and online settings. We show that it is NP-hard to approximate flowtime within Ω(logm) in the offline setting. We show that no online algorithm for the flowtime can have a competitive ratio better than Open image in new window

Item Type:Article
Source:Copyright of this article belongs to Springer-Verlag.
ID Code:123540
Deposited On:30 Sep 2021 09:51
Last Modified:30 Sep 2021 09:51

Repository Staff Only: item control page