Approximating Bounded Job Start Scheduling with Application in Royal Mail Deliveries Under Uncertainty

TY - JOUR

T1 - Approximating Bounded Job Start Scheduling with Application in Royal Mail Deliveries Under Uncertainty

AU - Bradley, Jeremy T.

AU - Letsios, Dimitrios

AU - Misener, Ruth

AU - Page, Natasha

PY - 2019/12/14

Y1 - 2019/12/14

N2 - Motivated by mail delivery scheduling problems arising in Royal Mail, we study a generalization of the fundamental makespan scheduling problem which we call the Bounded Job Start Scheduling Problem. Given a set of jobs, each one specified by an integer processing time, 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 on the number of jobs that may simultaneously begin per unit of time. We show that Longest Processing Time First (LPT) algorithm is tightly 2-approximate. After proving that the problem is strongly -hard even when, we elaborate on improving the 2-approximation ratio for this case. We distinguish the classes of long and short instances satisfying and, respectively, for each job j. We show that LPT is 5/3-approximate for the former and optimal for the latter. Then, we explore the idea of scheduling long jobs in parallel with short jobs to obtain solutions with tightly satisfied packing and bounded job start constraints. For a broad family of instances excluding degenerate instances with many very long jobs and instances with few machines, we derive a 1.985-approximation ratio. For general instances, we require machine augmentation to obtain better than 2-approximate schedules. Finally, we exploit machine augmentation and a state-of-the-art lexicographic optimization method for under uncertainty to propose a two-stage robust optimization approach for bounded job start scheduling under uncertainty attaining good trade-offs in terms of makespan and number of used machines. We substantiate this approach numerically using Royal Mail data.

AB - Motivated by mail delivery scheduling problems arising in Royal Mail, we study a generalization of the fundamental makespan scheduling problem which we call the Bounded Job Start Scheduling Problem. Given a set of jobs, each one specified by an integer processing time, 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 on the number of jobs that may simultaneously begin per unit of time. We show that Longest Processing Time First (LPT) algorithm is tightly 2-approximate. After proving that the problem is strongly -hard even when, we elaborate on improving the 2-approximation ratio for this case. We distinguish the classes of long and short instances satisfying and, respectively, for each job j. We show that LPT is 5/3-approximate for the former and optimal for the latter. Then, we explore the idea of scheduling long jobs in parallel with short jobs to obtain solutions with tightly satisfied packing and bounded job start constraints. For a broad family of instances excluding degenerate instances with many very long jobs and instances with few machines, we derive a 1.985-approximation ratio. For general instances, we require machine augmentation to obtain better than 2-approximate schedules. Finally, we exploit machine augmentation and a state-of-the-art lexicographic optimization method for under uncertainty to propose a two-stage robust optimization approach for bounded job start scheduling under uncertainty attaining good trade-offs in terms of makespan and number of used machines. We substantiate this approach numerically using Royal Mail data.

KW - Approximation algorithms

KW - Bounded job start scheduling

KW - Mail deliveries

KW - Robust scheduling

UR - http://www.scopus.com/inward/record.url?scp=85078545846&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-36412-0_6

DO - 10.1007/978-3-030-36412-0_6

M3 - Conference paper

AN - SCOPUS:85078545846

SN - 0302-9743

VL - 11949

SP - 69

EP - 81

JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

T2 - 13th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2019

Y2 - 13 December 2019 through 15 December 2019

ER -