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

Centro de Investigación en Ciencias, UAEMor, Cuernavaca, Morelos, Mexico

^* Corresponding author: nodari@uaem.mx

Received: 8 November 2024
Accepted: 5 June 2025

Abstract

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 2p are allowed, settling the complexity status of this before open setting.