Note—Sequencing with Finite Intermediate Storage

Abstract

This note presents procedures for finding optimal solutions to the deterministic N -job two machine flow-shop sequencing problem when the buffer size z is nearly the same as the number of jobs. When m = N − z − 2 is small, a simple and fast procedure that uses Johnson's algorithm on the middle N − 2 m jobs is used. The procedure has a computational complexity of o( N 2 m +1 ) comparisons.