Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
393592 | Information Sciences | 2011 | 5 Pages |
Abstract
Zhao et al. (2009) [24] study the m identical parallel-machine scheduling problem with rate-modifying activities to minimize the total completion time. They show that the problem can be solved in O(n2m+3) time. In this study we extend the scheduling environment to the unrelated parallel-machine setting and present a more efficient algorithm to solve the extended problem. For the cases where the rate-modifying rate is (i) larger than 0 and not larger than 1, and (ii) larger than 0, we show that the problem can be solved in O(nm+3) and O(n2m+2) time, respectively.
Related Topics
Physical Sciences and Engineering
Computer Science
Artificial Intelligence
Authors
Chou-Jung Hsu, T.C.E. Cheng, Dar-Li Yang,