An efficient algorithm for a job shop problem

The authors study the problem of minimizing makespan in a two-machine job shop with unit processing time operations. An efficient algorithm with respect to a succinct encoding of the problem instances is proposed. The algorithm is an improvement of earlier algorithms proposed for the problem by Brucker, Hefetz and Adiri and Timkovskiy. The idea behind the algorithm has the potential of extension to job shops with parallel machines.