An Efficient Optimal Algorithm for the Two-Machines Unit-Time Jobshop Schedule-Length Problem

The problem of scheduling a two-machine unit-operation-time jobshop to complete all jobs as rapidly as possible is shown to be solved by the following rule. Select for service from available jobs at each stage one with longest remaining processing time. The running time and storage space of the rule are both linear functions of the total number of operations, thereby establishing that the problem belongs to P.