Notes on scheduling non-simultaneously released jobs with restricted processing times on uniform machines

We consider a basic optimization problem where non-simultaneously released jobs are to be scheduled on m uniform machines. The objective is to minimize the maximum job completion time. For the special case of the problem with equal-length jobs, in Dessouky et al . [ Statistica Neerlandica 44 (1990) 115–123] a classical idea from Lageweg et al . [Computer Aided complexity classification of deterministic scheduling problems (1982)] was developed in an O ( n log n ) time algorithm. The algorithm was briefly described without presenting a proof that it works correctly. The description does not fully define how the claimed optimal schedule is obtained. Here we complete the description of the algorithm and prove that it is optimal. We also describe an O ( n log n ) time algorithm for the case where two job processing requirement p and 2 p are allowed, settling the complexity status of this before open setting.