1. ¹National Formosa University, Yun-Lin, Taiwan ROC
2. ²Nan-Kai Institute of Technology, Nan-Tou, Taiwan ROC

Correspondence: D-L Yang, Department of Information Management, National Formosa University, Yun-Lin, Taiwan 632, ROC. E-mail: dlyang@nfu.edu.tw

Received October 2006; Accepted December 2007; Published online 12 March 2008.

Abstract

In the literature, most of the parallel machine scheduling problems, in which the processing time of a job is a linear function of its starting time, are proved to be NP-hard. In this paper, we study an unrelated parallel machine scheduling problem in which the processing time of a job is a linear function of its starting time. The objective is to minimize the total completion time of all jobs. We consider two linear functions of job starting time in the problem and show that it is polynomially solvable.