Exact algorithms for the feedback length minimisation problem

Abstract

Planning the sequence of interrelated activities of production and manufacturing systems has become a challenging issue due to the existence of cyclic information flows. This study develops efficient exact algorithms for finding an activity sequence with minimum total feedback length in a design structure matrix. First, we present two new properties of the problem. Second, based on the properties, we develop an efficient Parallel Branch-and-Prune algorithm (PBP). Finally, the proposed PBP is further improved by adopting hash functions representing activity sequences, which is referred as hash function-based PBP. Experimental results indicate that the proposed hash function-based PBP can find optimal solutions for problems up to 25 interrelated activities within 1 h, and outperforms existing methods.

Keywords:

• design structure matrix
• production and manufacturing system
• iterative process
• Branch-and-Prune Algorithm
• hash function

Additional information

Funding

This work was supported in part by the National Natural Science Foundation of China [grant number 71101115], National Social Science Foundation of China [grant number 16BGL017], Fundamental Research Funds for the Central Universities [grant number 3102017jc19004].