Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2509.11383 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915494742720512 |
|---|---|
| author | Feng, Lin Franklin Hu, Yue Kuang, Xu |
| author_facet | Feng, Lin Franklin Hu, Yue Kuang, Xu |
| contents | We study optimal scheduling in multi-class queueing systems with reentrance, where jobs may return for additional service after completion. Such reentrance creates feedback loops that fundamentally alter congestion dynamics and challenge classical scheduling results. We model two distinct dimensions of the reentrance behavior, the probability of return and the speed of return, and show that their product, the effective return rate, is the key statistic that governs optimal priorities. Our main result establishes a dichotomy: when the effective return rate of the smaller job class (the class with lower expected total workload) is lower, a fixed priority rule is optimal; when it is higher, fixed rules are suboptimal and the optimal policy must be state dependent. This characterization clarifies how reentrance changes the externalities that jobs impose on one another and provides structural guidance for designing scheduling policies. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_11383 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Prioritizing Recurrent Services Feng, Lin Franklin Hu, Yue Kuang, Xu Optimization and Control Systems and Control We study optimal scheduling in multi-class queueing systems with reentrance, where jobs may return for additional service after completion. Such reentrance creates feedback loops that fundamentally alter congestion dynamics and challenge classical scheduling results. We model two distinct dimensions of the reentrance behavior, the probability of return and the speed of return, and show that their product, the effective return rate, is the key statistic that governs optimal priorities. Our main result establishes a dichotomy: when the effective return rate of the smaller job class (the class with lower expected total workload) is lower, a fixed priority rule is optimal; when it is higher, fixed rules are suboptimal and the optimal policy must be state dependent. This characterization clarifies how reentrance changes the externalities that jobs impose on one another and provides structural guidance for designing scheduling policies. |
| title | Prioritizing Recurrent Services |
| topic | Optimization and Control Systems and Control |
| url | https://arxiv.org/abs/2509.11383 |