A 2-machine sequencing problem with machine repetition and overlapping processing times

This paper is concerned with a two-machine sequencing problem with overlapping processing times and machine repetition. Though its structure appears comparatively simple the problem under consideration belongs to the class of NP-complete problems. Based on the (well-known) concept of dominating processing times/dominated machines conditions are identified which permit the construction of solutions minimising the maximum flow-time within polynomial time. Besides providing a solution to the investigated problem this paper also extends some famous results by Johnson to more complex production environments.