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

Dimitrios Letsios*, Jeremy T. Bradley, G. Suraj, Ruth Misener, Natasha Page

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)237-258
Number of pages22
Issue number2
Publication statusPublished - Apr 2021


  • Approximation algorithms
  • Bounded job start scheduling
  • Mail deliveries
  • Robust scheduling


Dive into the research topics of 'Approximate and robust bounded job start scheduling for Royal Mail delivery offices'. Together they form a unique fingerprint.

Cite this