Approximation algorithms for two-machine flow shop scheduling with batch setup times.
Bo ChenChris N. PottsVitaly A. StrusevichPublished in: Math. Program. (1998)
Keyphrases
- approximation algorithms
- setup times
- precedence constraints
- scheduling problem
- np hard
- special case
- lot sizing
- flowshop
- single machine
- multi item
- processing times
- single machine scheduling problem
- sequence dependent setup times
- strongly np hard
- worst case
- single server
- parallel machines
- approximation ratio
- constant factor approximation
- constant factor
- open shop
- lagrangian relaxation
- primal dual
- combinatorial auctions
- lower bound
- optimal solution
- linear programming
- multistage
- tabu search
- evolutionary algorithm