Single machine scheduling problem with controllable processing times and resource dependent release times

We consider two single machine scheduling problems with resource dependent release times and processing times, in which the release times and processing times are linearly decreasing functions of the amount of resources consumed. The objective is to minimize the total cost of makespan and resource consumption function that is composed of release time reduction and processing time reduction. In the first problem, the cost of reducing a unit release time for each job is common. We show that the problem can be solved in polynomial time. The second problem assumes different reduction costs of job release times. We show that the problem can be reduced polynomially from the partition problem and thus, is NP-complete. (c) 2006 Elsevier B.V. All rights reserved.