Imperial College London
Portrait Picture

ProfessorRuthMisener

Faculty of Engineering, Department of Computing

Professor in Computational Optimisation
 
 
 
//

Contact

 

+44 (0)20 7594 8315r.misener Website CV

 
 
//

Location

 

379Huxley BuildingSouth Kensington Campus

//

Summary

 

Publications

Citation

BibTex format

@unpublished{Letsios:2019,
author = {Letsios, D and Bradley, JT and Suraj, G and Misener, R and Page, N},
publisher = {arXiv},
title = {Approximating bounded job start scheduling with application in Royal Mail deliveries under uncertainty},
url = {http://arxiv.org/abs/1912.06862v1},
year = {2019}
}
Download

RIS format (EndNote, RefMan)

TY  - UNPB
AB  - Motivated by mail delivery scheduling problems arising in Royal Mail, westudy a generalization of the fundamental makespan scheduling P||Cmax problemwhich 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 executednon-preemptively by a set of m parallel identical machines, the objective is tocompute a minimum makespan schedule subject to an upper bound g<=m on thenumber of jobs that may simultaneously begin per unit of time. We show thatLongest Processing Time First (LPT) algorithm is tightly 2-approximate. Afterproving that the problem is strongly NP-hard even when g=1, we elaborate onimproving the 2-approximation ratio for this case. We distinguish the classesof long and short instances satisfying p_j>=m and p_j<m, respectively, for eachjob j. We show that LPT is 5/3-approximate for the former and optimal for thelatter. Then, we explore the idea of scheduling long jobs in parallel withshort jobs to obtain tightly satisfied packing and bounded job startconstraints. For a broad family of instances excluding degenerate instanceswith many very long jobs, we derive a 1.985-approximation ratio. For generalinstances, we require machine augmentation to obtain better than 2-approximateschedules. Finally, we exploit machine augmentation and lexicographicoptimization, which is useful for P||Cmax under uncertainty, to propose atwo-stage robust optimization approach for bounded job start scheduling underuncertainty aiming in good trade-offs in terms of makespan and number of usedmachines. We substantiate this approach numerically using Royal Mail data.
AU  - Letsios,D
AU  - Bradley,JT
AU  - Suraj,G
AU  - Misener,R
AU  - Page,N
PB  - arXiv
PY  - 2019///
TI  - Approximating bounded job start scheduling with application in Royal Mail deliveries under uncertainty
UR  - http://arxiv.org/abs/1912.06862v1
UR  - http://hdl.handle.net/10044/1/75750
ER  -
Download