SUMMARY This paper investigates the classical n-job, M-machine flow-shop scheduling problem under the assumption that jobs are processed on all machines in the same order. Baaed on the heuristic job-pairing technique and the decomposition strategy, a heuristic decomposition algorithm is developed which will generate at least a near-optimal schedule for the flow-shop scheduling problem. The proposed algorithm is compared to the existing decomposition approach and is found to be superior to Ashour's decomposition algorithm, both in increased solution quality and decreased computational time required to solve the problem.