AN EVALUATION OF THE CDS HEURISTIC IN FLOW SHOPS WITH MULTIPLE PROCESSORS

ABSTRACT

Scheduling in flow shops with multiple processors (FSMP) involves the sequencing of n jobs through m stages where there can be one or more identical processors at each stage. The heuristic developed by Campbell et al., also known as the CDS method, is one of the important contributions to the pure flow shop scheduling. In this paper, the CDS method was adopted for use in the FSMP environment. This study compares the CDS heuristic with the (m—1)Random scheduling method in order to investigate the effectiveness of the CDS method when used in the FSMP environment. The results indicate that the CDS method is superior to the (m—1)Random scheduling method when there are small numbers of stages and numbers of processors at each stage for both the small and large sized FSMP problems.

Keywords:

• scheduling
• flow shop
• makespan
• heuristic