A block approach for single-machine scheduling with release dates and due dates (Q1083026)

The problem of scheduling deterministic tasks on one machine in order to minimize maximum lateness is considered. Tasks are nonpreemptable. They are characterized by arbitrary processing times, arrival times and deadlines. This problem is known to be NP-hard, thus, unlikely to admit a non-enumerative approach. Hence, in the paper a new method of the branch- and-bound type is proposed. The paper lacks, however, a comparison of the proposed algorithm to other existing methods.