The proportionate two-machine no-wait job shop scheduling problem

We consider the two-machine no-wait job shop minimum makespan scheduling problem. We show that when each job has exactly two equal length operations (also called a proportionate job shop), the problem is solvable in O(nlog n) time. We also show that the proportionate problem becomes strongly NP-hard when some jobs are allowed to visit only one machine. Finally, we show that the proportionate problem with missing operations becomes solvable in O(nlog n) time when all missing operations are on the same machine.