Unrelated parallel-machine scheduling with rate-modifying activities to minimize the total completion time

摘要

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(n~(2m+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(n~(2m+2)) time, respectively.