Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
479110 | European Journal of Operational Research | 2007 | 9 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Byung-Cheon Choi, Suk-Hun Yoon, Sung-Jin Chung,