Algorithms for special cases of the single machine total tardiness problem and an application to the even–odd partition problem

The scheduling problem of minimizing total tardiness on a single machine is known to be NPNP-hard in the ordinary sense. In this paper, we consider the special case of the problem when the processing times pjpj and the due dates djdj of the jobs j,j∈N={1,2,…,n}, are oppositely ordered: p1≥p2≥⋯≥pnp1≥p2≥⋯≥pn and d1≤d2≤⋯≤dnd1≤d2≤⋯≤dn. It is shown that already this special case is NPNP-hard in the ordinary sense, too. The set of jobs NN is partitioned into k,1≤k≤nk,1≤k≤n, subsets M1,M2,…,MkM1,M2,…,Mk, Mν⋂Mμ=0̸Mν⋂Mμ=0̸ for ν≠μ,N=M1⋃M2⋃⋯⋃Mkν≠μ,N=M1⋃M2⋃⋯⋃Mk, such that maxi,j∈Mν|di−dj|≤minj∈Mνpjmaxi,j∈Mν|di−dj|≤minj∈Mνpj for each ν=1,2,…,kν=1,2,…,k. We propose algorithms which solve the problem: in O(kn∑pj)O(kn∑pj) time if 1≤k