On-line approximation algorithms for scheduling tasks on identical machines withextendable working time.
Maria Grazia SperanzaZsolt TuzaPublished in: Ann. Oper. Res. (1999)
Keyphrases
- approximation algorithms
- identical machines
- precedence constraints
- polynomial time approximation
- np hard
- scheduling problem
- vertex cover
- job scheduling
- worst case
- special case
- minimum cost
- single machine
- primal dual
- processing times
- approximation ratio
- single machine scheduling problem
- setup times
- branch and bound algorithm
- error bounds
- linear programming
- open shop
- combinatorial auctions
- constant factor approximation