Analysis of a Combinatorial Approach to Flowshop Scheduling Problems

Abstract

This paper presents a simple theoretical development of the combinatorial approach to flowshop scheduling problems where each job is processed on each machine in the same sequence and passing of jobs is not allowed. The objective function considered is the weighted sum of completion times of all jobs on all machines. Subsequently, a probabilistic analysis shows that this approach is not suitable to solve problems containing more than nine jobs. A theoretical analysis of the poor performance of this approach is described and suggestions for future research are outlined.

View correction statement:

Erratum: Analysis of a Combinatorial Approach to Flowshop Scheduling Problems