GA-BHTR: an improved genetic algorithm for partner selection in virtual manufacturing

Abstract

An evolutionary genetic algorithm maintained using the binary heap and transitive reduction (GA-BHTR) method for addressing the partner selection problem (PSP) in a virtual enterprise is proposed. In order to reduce the time complexity of PSP, an algorithm for simplifying the directed acyclic graph that represents the precedence relationship among the subprojects in PSP is first designed. Different from the traditional regular GA, in order to avoid solutions from converging to a constant value early during evolution, multiple communities are used instead of a single community in GA-BHTR. The method and algorithms to distribute the individuals to the multiple communities while maximising the differences among the different communities are proposed. The concept of the catastrophe is introduced in the proposed GA-BHTR in order to avoid the solutions from converging to a local best solution too early after several generations of evolution. In order to maintain the capacity of the community (i.e. the number of individuals existing in a community) at a constant value while enhancing the diversity of the proposed GA-BHTR, an algorithm using the binary heap to maintain the data is designed. Simulation and experiments are conducted to test the effectiveness and performance of the proposed GA-BHTR for addressing PSP.

Keywords:

• partner selection problem (PSP)
• virtual manufacturing
• genetic algorithm (GA)
• transitive reduction
• mutiple communities
• catastrophe
• binary heap

Acknowledgements

This paper is partly supported by the NSFC (National Science Foundation of China) Project (No. 51005012 and No. 61074144) and the Fundamental Research Funds for the Central Universities in China. We would also like to express our great appreciation to the valuable comments made by the anonymous reviewers and the editor of the International Journal of Produciton Research.