A heuristic proǵramminǵ procedure for sequencinǵ the static flowshop

Abstract

This paper describes a heuristic procedure for sequencing the n job m machine static flowshop. Basically, the procedure is performed in two overall steps. In the first step, each of the n jobs is tested as a potential immediate follower to each of the other jobs. In effect, this step of the procedure asks the question, ‘how well does a particular job fit in terms of job blocking or machine idleness if it were to follow some other job?’ An overall figure of merit, or cost c_ij, is determined for each job j as a follower to another job i. Six different heuristics are presented for determining sets of c_ij values. Using these values of c_ij, the second step then heuristically develops a job sequence by solving the travelling salesman problem. The paper also presents computational experience with the algorithm for a variety of randomly generated test problems (up to 50 jobs and 50 machines in size), and compares its performance with other published heuristic techniques.