A polynomial algorithm for the two machine job-shop scheduling problem with a fixed number of jobs (Q1326784)

The nonpreemptive job shop scheduling problem where \(n\) jobs are to processed on two machines so as to minimize the makespan (maximum completion time) is considered. Job \(i\) consists of \(n_ i\) operations and the sequence of operation processing is given in advance for each job. It is known that the problem is NP-hard for three machines and \(n=3\) and it is polynomially solvable for \(n=2\) and non fixed number of machines. It is known also an \(O(r^ 4)\) algorithm for the problem with two machines and \(n=3\), where \(r\) denotes the maximal number of operations per job. The author proposes an \(O(r^{3k})\) algorithm for the problem with two machines and \(n= k\) (\(k\) is a fixed number). The algorithm can be easily transformed into \(O(r^ 4)\) algorithm for \(n= 3\).