Bicriterion parallel-machine scheduling of equal-length jobs to minimize total tardiness and number of tardy jobs

We consider bicriterion scheduling of equal-length jobs on uniform parallel machines to minimize total tardiness and number of tardy jobs. The Pareto-scheduling problem is studied in this paper, which includes the hierarchical-scheduling problem as a subversion. By using the single-machine scheduling with generated completion times model introduced by Zhao and Yuan (J Comb Optim 39:637–661, 2020), we present an -time algorithm to solve the Pareto-scheduling problem, and two -time algorithms to solve two hierarchical-scheduling problems, respectively. Our -time algorithms improve the -time algorithms given by Sarin and Prakash (J Comb Optim 8:227–240, 2004) to solve two hierarchical-scheduling problems on identical parallel machines.