Scheduling on Identical Machines with Setup Time and Unknown Execution Time
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908450582167552 |
|---|---|
| author | Kawase, Yasushi Makino, Kazuhisa Phan, Vinh Long Sumita, Hanna |
| author_facet | Kawase, Yasushi Makino, Kazuhisa Phan, Vinh Long Sumita, Hanna |
| contents | In this study, we investigate a scheduling problem on identical machines in which jobs require initial setup before execution. We assume that an algorithm can dynamically form a batch (i.e., a collection of jobs to be processed together) from the remaining jobs. The setup time is modeled as a known monotone function of the set of jobs within a batch, while the execution time of each job remains unknown until completion. This uncertainty poses significant challenges for minimizing the makespan. We address these challenges by considering two scenarios: each job batch must be assigned to a single machine, or a batch may be distributed across multiple machines. For both scenarios, we analyze settings with and without preemption. Across these four settings, we design online algorithms that achieve asymptotically optimal competitive ratios with respect to both the number of jobs and the number of machines. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_11311 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Scheduling on Identical Machines with Setup Time and Unknown Execution Time Kawase, Yasushi Makino, Kazuhisa Phan, Vinh Long Sumita, Hanna Data Structures and Algorithms In this study, we investigate a scheduling problem on identical machines in which jobs require initial setup before execution. We assume that an algorithm can dynamically form a batch (i.e., a collection of jobs to be processed together) from the remaining jobs. The setup time is modeled as a known monotone function of the set of jobs within a batch, while the execution time of each job remains unknown until completion. This uncertainty poses significant challenges for minimizing the makespan. We address these challenges by considering two scenarios: each job batch must be assigned to a single machine, or a batch may be distributed across multiple machines. For both scenarios, we analyze settings with and without preemption. Across these four settings, we design online algorithms that achieve asymptotically optimal competitive ratios with respect to both the number of jobs and the number of machines. |
| title | Scheduling on Identical Machines with Setup Time and Unknown Execution Time |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2507.11311 |