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

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