1. ¹Department of Computer and Information Science, National Chiao Tung University, Hsinchu 300, Taiwan
2. ²Department of Information and Finance Management, National Chiao Tung University, Hsinchu 300, Taiwan

Correspondence: BMT Lin, Department of Information and Finance Management, National Chiao Tung University, Hsinchu 300, Taiwan. E-mail: bmtlin@mail.nctu.edu.tw

Received January 2005; Accepted January 2006; Published online 26 April 2006.

Abstract

We consider a parallel-machine scheduling problem of minimizing the total completion time. The processing time of a job is a linear function of its starting time and deterioration rate. This problem is known to be NP-hard, even for the case with two machines. In this note, we generalize an existing lower bound for the two-machine case to the general case with an arbitrary number of machines. Despite the generalization concerning machine number, our bound has one extra term that makes our bound tighter than the existing one.