Batch Scheduling with Deadlines on Parallel Machines: An NP-Hard Case.
Mikhail Y. KovalyovYakov M. ShafranskyPublished in: Inf. Process. Lett. (1997)
Keyphrases
- parallel machines
- scheduling problem
- np hard
- total tardiness
- sequence dependent setup times
- optimal solution
- unrelated parallel machines
- remains np hard
- massively parallel
- approximation algorithms
- precedence constraints
- single machine
- response time
- special case
- linear programming
- minimize total
- setup times
- markov random field
- objective function
- weighted tardiness
- polynomially solvable
- single server
- upper bound
- worst case
- search space
- parallel computing
- processing times
- lower bound
- information systems