An online joint replenishment problem combined with single machine scheduling
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916230915424256 |
|---|---|
| author | Györgyi, Péter Kis, Tamás Tamási, Tímea |
| author_facet | Györgyi, Péter Kis, Tamás Tamási, Tímea |
| contents | This paper considers a combination of the joint replenishment problem with single machine scheduling. There is a single resource, which is required by all the jobs, and a job can be started at time point $t$ on the machine if and only the machine does not process another job at $t$, and the resource is replenished between its release date and $t$. Each replenishment has a cost, which is independent of the amount replenished. The objective is to minimize the total replenishment cost plus the maximum flow time of the jobs.
We consider the online variant of the problem, where the jobs are released over time, and once a job is inserted into the schedule, its starting time cannot be changed. We propose a deterministic 2-competitive online algorithm for the general input. Moreover, we show that for a certain class of inputs (so-called $p$-bounded input), the competitive ratio of the algorithm tends to $\sqrt{2}$ as the number of jobs tends to infinity. We also derive several lower bounds for the best competitive ratio of any deterministic online algorithm under various assumptions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2208_02748 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | An online joint replenishment problem combined with single machine scheduling Györgyi, Péter Kis, Tamás Tamási, Tímea Data Structures and Algorithms Optimization and Control 90B35 This paper considers a combination of the joint replenishment problem with single machine scheduling. There is a single resource, which is required by all the jobs, and a job can be started at time point $t$ on the machine if and only the machine does not process another job at $t$, and the resource is replenished between its release date and $t$. Each replenishment has a cost, which is independent of the amount replenished. The objective is to minimize the total replenishment cost plus the maximum flow time of the jobs. We consider the online variant of the problem, where the jobs are released over time, and once a job is inserted into the schedule, its starting time cannot be changed. We propose a deterministic 2-competitive online algorithm for the general input. Moreover, we show that for a certain class of inputs (so-called $p$-bounded input), the competitive ratio of the algorithm tends to $\sqrt{2}$ as the number of jobs tends to infinity. We also derive several lower bounds for the best competitive ratio of any deterministic online algorithm under various assumptions. |
| title | An online joint replenishment problem combined with single machine scheduling |
| topic | Data Structures and Algorithms Optimization and Control 90B35 |
| url | https://arxiv.org/abs/2208.02748 |