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

Dimitrios Letsios (), Jeremy T. Bradley (), Suraj G (), Ruth Misener () and Natasha Page ()
Additional contact information
Dimitrios Letsios: King’s College London
Jeremy T. Bradley: GBI/Data Science Group, Royal Mail
Suraj G: Imperial College London
Ruth Misener: Imperial College London
Natasha Page: Imperial College London

Journal of Scheduling, 2021, vol. 24, issue 2, No 7, 237-258

Abstract: Abstract Motivated by mail delivery scheduling problems arising in Royal Mail, we study a generalization of the fundamental makespan scheduling $$P||C_{\max }$$ P | | C max problem which we call the bounded job start scheduling problem. Given a set of jobs, each specified by an integer processing time $$p_j$$ 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\le m$$ 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 $${\mathcal {N}}{\mathcal {P}}$$ N P -hard even when $$g=1$$ 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\ge m$$ p j ≥ m and $$p_j

Keywords: Bounded job start scheduling; Approximation algorithms; Robust scheduling; Mail deliveries (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-021-00678-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:24:y:2021:i:2:d:10.1007_s10951-021-00678-7

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-021-00678-7

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().