Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
436580 | Theoretical Computer Science | 2008 | 7 Pages |
Abstract
In the literature, most of the parallel-machine scheduling problems, in which the processing time of a job is a linear function of its starting time, are proved to be NP-hard. In this paper, we study a parallel-machine scheduling problem in which the processing time of a job is a linear function of its starting time. The objectives are to minimize the total completion of all jobs and the total load on all machines respectively. We consider two linear functions of job starting time and show that the problems are polynomially solvable.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics