Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2503.23273 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915218717671424 |
|---|---|
| author | Li, Shuguang Wen, Zhenxin Wei, Jing |
| author_facet | Li, Shuguang Wen, Zhenxin Wei, Jing |
| contents | This paper studies the bicriteria problem of scheduling $n$ jobs on a serial-batch machine to minimize makespan and maximum cost simultaneously. A serial-batch machine can process up to $b$ jobs as a batch, where $b$ is known as the batch capacity. When a new batch starts, a constant setup time is required for the machine. Within each batch, the jobs are processed sequentially, and thus the processing time of a batch equals the sum of the processing times of its jobs. All the jobs in a batch have the same completion time, namely, the completion time of the batch. The main result is an $O(n^3)$-time algorithm which can generate all Pareto optimal points for the bounded model ($b<n$) without precedence relation. The algorithm can be modified to solve the unbounded model ($b\ge n$) with strict precedence relation in $O(n^3)$ time as well. The results improve the previously best known running time of $O(n^4)$ for both the bounded and unbounded models. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_23273 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Improved algorithms for single machine serial-batch scheduling to minimize makespan and maximum cost Li, Shuguang Wen, Zhenxin Wei, Jing Data Structures and Algorithms This paper studies the bicriteria problem of scheduling $n$ jobs on a serial-batch machine to minimize makespan and maximum cost simultaneously. A serial-batch machine can process up to $b$ jobs as a batch, where $b$ is known as the batch capacity. When a new batch starts, a constant setup time is required for the machine. Within each batch, the jobs are processed sequentially, and thus the processing time of a batch equals the sum of the processing times of its jobs. All the jobs in a batch have the same completion time, namely, the completion time of the batch. The main result is an $O(n^3)$-time algorithm which can generate all Pareto optimal points for the bounded model ($b<n$) without precedence relation. The algorithm can be modified to solve the unbounded model ($b\ge n$) with strict precedence relation in $O(n^3)$ time as well. The results improve the previously best known running time of $O(n^4)$ for both the bounded and unbounded models. |
| title | Improved algorithms for single machine serial-batch scheduling to minimize makespan and maximum cost |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2503.23273 |