Makespan minimization of multi-slot just-in-time scheduling on single and parallel machines (Q600836)

In this paper multi-slot just-in-time scheduling problems are considered. Given is a set of jobs \(j=1,\ldots,n\) where each job \(j\) has a processing time \(p_j\) and a due date \(d_j\). The objective is to schedule all jobs on a given number of parallel machines in time slots of length \(L\) such that job \(j\) is completed exactly at its due date in one time slot (i.e. at time \(iL+d_j\) for some integer \(i \geq 0\)) and the makespan is minimized. In this paper an \(O(n \log ^2 n)\)-time algorithm is presented for the single machine case and an \(O(n \log n)\)-time algorithm for an arbitrary number \(m>1\) of parallel machines where \(p_j \leq d_j\) for all jobs \(j\) holds. Finally, for the general case on \(m>1\) parallel machines a polynomial-time approximation algorithm with constant worst-case performance ratio is proposed.