One-operator, two-machine open shop and flowshop scheduling with setup times for machines and maximum lateness objective

This paper considers a scheduling problem in which a single operator completes a set of n jobs requiring operations on two machines. The operator can perform only one operation at a time, so when one machine is in use the other is idle. After developing general properties of optimal schedules, the paper develops efficient algorithms for minimizing maximum lateness. The algorithm has time complexity O(n) (after due data sorting) for both the open and flowshop cases.