A Best Possible Deterministic On-Line Algorithm for Minimizing Maximum Delivery Time on a Single Machine.
Han HoogeveenArjen P. A. VestjensPublished in: SIAM J. Discret. Math. (2000)
Keyphrases
- single machine
- dynamic programming
- learning algorithm
- competitive ratio
- computational complexity
- search space
- scheduling problem
- processing times
- single machine scheduling problem
- optimal solution
- np hard
- total weighted tardiness
- combinatorial optimization
- weighted number of tardy jobs
- weighted tardiness
- search procedure
- benchmark problems
- np complete
- worst case
- objective function