Single Machine Scheduling Problems With Resource Dependent Release Times And Penalty Factor

In this paper, we mainly consider two single machine scheduling problems with resource dependent release times and penalty factor, in which the release times and penalty factor can be controlled by a non-increasing convex resource consumption function.In the first problem,we study a single scheduling problem, in which the objec-tive is to minimize the total resource consumption with the constraint on the sum of job completion times. At the same time we use the method of polynomial-time reductions show that Permutation integer problem can reduce to the decision pro blem of this problem in polynomial-time, further show that the decision problem of this problem is NP-complete and give a approximate algorithm.In the second problem, we consider a single scheduling problem, in which the objective is to minimize the weighted total resource consumption and the sum of job completion times with the constraint that initial release time subtracts penalty factor greater than the sum of job processing times. Like the first problem we use the method of polynomial-time reductions, and show that this problem can reduce to the Assignment problem in polynomial-time, further more we show that this problem is polynomially solvable and its algorithms complexity is O(nlogn).We provide some optimality conditions as well.