1. Approximation algorithms for batch scheduling with processing set restrictions.
- Author
-
Chai, Xing, Li, Wenhua, Ng, C. T., and Cheng, T. C. E.
- Subjects
BATCH processing ,APPROXIMATION algorithms ,PRODUCTION scheduling ,ECONOMIC lot size - Abstract
We consider batch scheduling on m machines to minimize the makespan. Each job has a given set of machines to be assigned. Each machine can process several jobs simultaneously as a batch, and the machines may have different batch capacities. We study two models: (i) scheduling on equal-speed batch machines under a nested processing set restriction, where the machines have the same processing speed, and (ii) scheduling on uniform batch machines under a tree-hierarchical processing set restriction, where the machines have different processing speeds. For both models we design polynomial-time approximation algorithms to solve them. The algorithms have a worst-case ratio of 2 for non-identical batch capacities and a worst-case ratio of 2 - 1 / m for identical batch capacities. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF