Minimizing total completion time and maximum cost simultaneously is solvable in polynomial time
January 1995
Article
pp 205-208.
This publication is part of collection
| Related Files |
|---|
View PDF Version
(MinimumTotalCompletion-1995.pdf, 0.3MB) |
We prove that the bicriteria single-machine scheduling problem of minimizing total completion time and maximum cost simultaneously is solvable in polynomial time. Our result settles a long-standing open problem.
Keywords
Automatically Extracted Terms
- schedule
- problem
- algorithm
- pareto
- completion time
- completion
- scheduling
- point
- polynomial time
- job jj
- interchange
- deadline
- performance measures
- kth position
- jobs ji
- polynomial
- number
- van wassenhove
- proof
- position
