Approximation algorithms for bicriteria scheduling problems on identical parallel machines for makespan and total completion time.
Xiaojuan JiangKangbok LeeMichael L. PinedoPublished in: Eur. J. Oper. Res. (2023)
Keyphrases
- bicriteria
- scheduling problem
- flowshop
- approximation algorithms
- identical parallel machines
- np hard
- strongly np hard
- completion times
- processing times
- single machine
- special case
- sequence dependent setup times
- setup times
- knapsack problem
- release dates
- minimizing makespan
- tabu search
- integer programming
- worst case
- parallel machines
- precedence constraints
- lower bound
- optimal solution
- linear programming
- computational complexity
- lagrangian relaxation
- competitive ratio
- job shop
- efficient solutions
- single machine scheduling problem
- linear program
- branch and bound algorithm