Precedence graph-oriented approach to optimise single-product flow-line configurations of reconfigurable manufacturing system

Abstract

To facilitate the configuration selection of reconfigurable manufacturing systems, it needs to generate K (predefined number) best configurations as candidates for a given demand period. This paper presents a systematic approach for the problem of generating single-product flow-line (SPFL) configurations. The problem is to determine the SPFL configuration's parameters including number of workstations, number of paralleling machines and machine type as well as assigned operations for each workstation. Given an operation precedence graph (PG) and machine options for each operation, the objective is to minimise the capital costs of SPFL configurations subject to space limitation, investment limitation, and capacity constraint as well as precedence constraints among operations. For linear PG with one feasible operation sequence (FOS), a constrained K-shortest paths (CKSP) formulation is developed and a CKSP algorithm is introduced to generate K-best configurations including the optimal and near-optimal ones. For simple PG (a small number of FOSs), the K-best configurations are found by repeatedly solving the CKSP problem associated with every FOS. For general PG (numerous FOSs), a GA based approach is proposed to identify K-best configurations through searching within the optimal configurations associated with all FOSs. Case studies illustrate the effectiveness and efficiency of our approach.

Keywords:

• reconfigurable manufacturing system
• configuration generation
• flow-line
• precedence graph
• constrained K-shortest paths
• genetic algorithm

Acknowledgements

The work is supported by National Basic Research Program of China (973 Program) under Grant No. 2002CB312204. The authors would like to acknowledge anonymous referees whose comments have helped us to improve this paper.