Minimizing the Weighted Makespan with Restarts on a Single Machine
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909835536105472 |
|---|---|
| author | Amouzandeh, Aflatoun Jansen, Klaus Pirotton, Lis van Stee, Rob Wambsganz, Corinna |
| author_facet | Amouzandeh, Aflatoun Jansen, Klaus Pirotton, Lis van Stee, Rob Wambsganz, Corinna |
| contents | We consider the problem of minimizing the weighted makespan on a single machine with restarts. Restarts are similar to preemptions but weaker: a job can be interrupted, but then it has to be run again from the start instead of resuming at the point of interruption later. The objective is to minimize the weighted makespan, defined as the maximum weighted completion time of jobs.
We establish a lower bound of 1.4656 on the competitive ratio achievable by deterministic online algorithms. For the case where all jobs have identical processing times, we design and analyze a deterministic online algorithm that improves the competitive ratio to better than 1.3098. Finally, we prove a lower bound of 1.2344 for this case. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_09589 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Minimizing the Weighted Makespan with Restarts on a Single Machine Amouzandeh, Aflatoun Jansen, Klaus Pirotton, Lis van Stee, Rob Wambsganz, Corinna Data Structures and Algorithms F.2.2 We consider the problem of minimizing the weighted makespan on a single machine with restarts. Restarts are similar to preemptions but weaker: a job can be interrupted, but then it has to be run again from the start instead of resuming at the point of interruption later. The objective is to minimize the weighted makespan, defined as the maximum weighted completion time of jobs. We establish a lower bound of 1.4656 on the competitive ratio achievable by deterministic online algorithms. For the case where all jobs have identical processing times, we design and analyze a deterministic online algorithm that improves the competitive ratio to better than 1.3098. Finally, we prove a lower bound of 1.2344 for this case. |
| title | Minimizing the Weighted Makespan with Restarts on a Single Machine |
| topic | Data Structures and Algorithms F.2.2 |
| url | https://arxiv.org/abs/2510.09589 |