| Autor: |
Letsios, Dimitrios, Bradley, Jeremy T., G, Suraj, Misener, Ruth, Page, Natasha |
| Rok vydání: |
2019 |
| Předmět: |
|
| Druh dokumentu: |
Working Paper |
| Popis: |
Motivated by mail delivery scheduling problems arising in Royal Mail, we study a generalization of the fundamental makespan scheduling P||Cmax problem which we call the bounded job start scheduling problem. Given a set of jobs, each specified by an integer processing time p_j, that have to be executed non-preemptively by a set of m parallel identical machines, the objective is to compute a minimum makespan schedule subject to an upper bound g<=m on the number of jobs that may simultaneously begin per unit of time. With perfect input knowledge, we show that Longest Processing Time First (LPT) algorithm is tightly 2-approximate. After proving that the problem is strongly NP-hard even when g=1, we elaborate on improving the 2-approximation ratio for this case. We distinguish the classes of long and short instances satisfying p_j>=m and p_j
|
| Databáze: |
arXiv |
| Externí odkaz: |
|
