Algorithms for some maximization scheduling problems on a single machine

In this paper, we consider two scheduling problems on a single machine, where a specific objective function has to be maximized in contrast to usual minimization problems. We propose exact algorithms for the single machine problem of maximizing total tardiness $1\|\max\sum T_j$ and for the problem of maximizing the number of tardy jobs $1\|\max\sum U_j$. In both cases, it is assumed that the processing of the first job starts at time zero and there is no idle time between the jobs. We show that problem $1\|\max\sum U_j$ is polynomially solvable. For several special cases of problem $1\|\max\sum T_j$, we present exact polynomial algorithms. Moreover, we give an exact pseudo-polynomial algorithm for the general case of the latter problem and an alternative exact algorithm.

Presented by the member of Editorial Board: P. Yu. Chebotarev