Abstract
We consider the problem of scheduling a set of jobs on a single-machine where the release time of a job is related to the amount of resource consumed. The release time resource consumption function is common to all jobs, while different jobs may have different resource consumption rates. The objective is to minimize the total weighted job completion time, subject to a constraint on the resource consumed by the jobs. We show that the problem is strongly NP-hard in general and discuss the special case when the weight of a job is equal to its resource consumption rate. This special case can be solved efficiently when the resource consumption function is linear.
Original language | English |
---|---|
Pages (from-to) | 53-58 |
Number of pages | 6 |
Journal | Mathematical and Computer Modelling |
Volume | 20 |
Issue number | 2 |
DOIs | |
Publication status | Published - 1 Jan 1994 |
Externally published | Yes |
Keywords
- Release dates
- Resource allocation
- Resource consumption
- Single machine
ASJC Scopus subject areas
- Modelling and Simulation
- Computer Science Applications