Parallel machine scheduling with time dependent processing times

We consider a parallel machine scheduling problem in which the processing time of a job is a simple linear function of its starting time. The objective is to minimize total completion times. We show that the problem is NP-hard in the strong sense even with a fixed number of machines. When the number of machines is arbitrary, we show that there is no polynomial time heuristic with a constant worst-case bound unless P = NP. Under the two-machine case, we derive a data dependent worst-case bound for a simple polynomial time heuristic whose performance can be arbitrarily bad. However, for the case of a fixed number of machines, the question whether there exists a polynomial time heuristic with a constant worst-case bound remains open.