A Program to Determine the Exact Competitive Ratio of List s-Batching with Unit Jobs
Wolfgang W. BeinLeah EpsteinLawrence L. LarmoreJohn NogaPublished in: CoRR (2009)
Keyphrases
- competitive ratio
- single machine
- processing times
- identical parallel machines
- scheduling jobs
- release dates
- scheduling problem
- setup times
- flowshop
- single machine scheduling problem
- lower bound
- completion times
- average case
- precedence constraints
- online algorithms
- optimal strategy
- parallel machines
- multi agent
- fixed number
- weighted sum
- batch processing
- tabu search
- markov chain