Approximate and robust bounded job start scheduling for Royal Mail delivery offices

TY - JOUR

T1 - Approximate and robust bounded job start scheduling for Royal Mail delivery offices

AU - Letsios, Dimitrios

AU - Bradley, Jeremy T.

AU - Suraj, G.

AU - Misener, Ruth

AU - Page, Natasha

N1 - Funding Information: This work was funded by Engineering & Physical Sciences Research Council (EPSRC) grant EP/M028240/1 and an EPSRC Research Fellowship to RM (grant number EP/P016871/1). Publisher Copyright: © 2021, The Author(s). Copyright: Copyright 2021 Elsevier B.V., All rights reserved.

PY - 2021/4

Y1 - 2021/4

N2 - 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 pj, 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 pj≥ m and pj< m, 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 tightly satisfied packing and bounded job start constraints. For a broad family of instances excluding degenerate instances with many very long jobs, we derive a 1.985-approximation ratio. For general instances, we require machine augmentation to obtain better than 2-approximate schedules. In the presence of uncertain job processing times, we exploit machine augmentation and lexicographic optimization, which is useful for P| | Cmax under uncertainty, to propose a two-stage robust optimization approach for bounded job start scheduling under uncertainty aiming in a low number of used machines. Given a collection of schedules of makespan ≤ D, this approach allows distinguishing which are the more robust. We substantiate both the heuristics and our recovery approach numerically using Royal Mail data. We show that for the Royal Mail application, machine augmentation, i.e., short-term van rental, is especially relevant.

AB - 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 pj, 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 pj≥ m and pj< m, 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 tightly satisfied packing and bounded job start constraints. For a broad family of instances excluding degenerate instances with many very long jobs, we derive a 1.985-approximation ratio. For general instances, we require machine augmentation to obtain better than 2-approximate schedules. In the presence of uncertain job processing times, we exploit machine augmentation and lexicographic optimization, which is useful for P| | Cmax under uncertainty, to propose a two-stage robust optimization approach for bounded job start scheduling under uncertainty aiming in a low number of used machines. Given a collection of schedules of makespan ≤ D, this approach allows distinguishing which are the more robust. We substantiate both the heuristics and our recovery approach numerically using Royal Mail data. We show that for the Royal Mail application, machine augmentation, i.e., short-term van rental, is especially relevant.

KW - Approximation algorithms

KW - Bounded job start scheduling

KW - Mail deliveries

KW - Robust scheduling

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

U2 - 10.1007/s10951-021-00678-7

DO - 10.1007/s10951-021-00678-7

M3 - Article

AN - SCOPUS:85103207044

SN - 1094-6136

VL - 24

SP - 237

EP - 258

JO - JOURNAL OF SCHEDULING

JF - JOURNAL OF SCHEDULING

IS - 2

ER -