Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2401.00419 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910285158154240 |
|---|---|
| author | Bergé, Pierre Chaikovskaia, Mari Gayon, Jean-Philippe Quilliot, Alain |
| author_facet | Bergé, Pierre Chaikovskaia, Mari Gayon, Jean-Philippe Quilliot, Alain |
| contents | We consider here the MultiBot problem for the scheduling and the resource parametrization of jobs related to the production or the transportation of different products inside a given time horizon. Those jobs must meet known in advance demands. The time horizon is divided into several discrete identical periods representing each the time needed to proceed a job. The objective is to find a parametrization and a schedule for the jobs in such a way they require as less resources as possible. Though this problem derived from the applicative context of reconfigurable robots, we focus here on fundamental issues. We show that the resulting strongly NP-hard Multibot problem may be handled in a greedy way with an approximation ratio of $\frac{4}{3}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_00419 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Approximation algorithms for Job Scheduling with reconfigurable resources Bergé, Pierre Chaikovskaia, Mari Gayon, Jean-Philippe Quilliot, Alain Data Structures and Algorithms F.2.2 We consider here the MultiBot problem for the scheduling and the resource parametrization of jobs related to the production or the transportation of different products inside a given time horizon. Those jobs must meet known in advance demands. The time horizon is divided into several discrete identical periods representing each the time needed to proceed a job. The objective is to find a parametrization and a schedule for the jobs in such a way they require as less resources as possible. Though this problem derived from the applicative context of reconfigurable robots, we focus here on fundamental issues. We show that the resulting strongly NP-hard Multibot problem may be handled in a greedy way with an approximation ratio of $\frac{4}{3}$. |
| title | Approximation algorithms for Job Scheduling with reconfigurable resources |
| topic | Data Structures and Algorithms F.2.2 |
| url | https://arxiv.org/abs/2401.00419 |