Unbounded parallel-batch scheduling to minimize the total weighted tardy span

Abstract

For the unbounded parallel-batch scheduling on a single machine, we consider a new criterion, the total weighted tardy span of jobs, where the tardy span of a job is its completion time if it is tardy and is 0 if it is early. From the literature, the general problem is NP-hard and can be solved in pseudo-polynomial time. When the jobs are released at time 0, we show that the problem is NP-hard and present three pseudo-polynomial-time algorithms and computational experiments that show the performances of the three algorithms. Moreover, for the two cases, (ⅰ) the jobs are released at different times and the number of different processing times is a constant and (ⅱ) the jobs are released at time 0 and have a common due date, we present polynomial-time algorithms.