Heuristic-Programming Solution of a Flowshop-Scheduling Problem.

This paper considers the static flowshop-scheduling problem with the objective of minimizing, as a cost function, the mean job-completion time. Within the more general framework of combinatorial optimization problems, it defines a heuristic search technique--an approach that has been successful in the past in obtaining near-optimal solutions for problems that could not be solved exactly, either for lack of theory or because of exorbitant computational requirements. The paper presents a two-phase algorithm: The first phase searches among schedules with identical processing orders on all machines; the second refines the schedule by allowing passing. Results of computer study are presented for a large ensemble of pseudorandom problems, and for two particular problems previously cited in the literature. The method is shown to provide solutions that are exceptionally low in cost, and superior to those provided by sampling techniques in the cases for which comparison is possible. Computation time is also discussed and is given in machine-independent terms. [ABSTRACT FROM AUTHOR]