A GA maintained by binary heap and transitive reduction for addressing PSP

Author

Qiao, K. ; Tao, F. ; Zhang, L. ; Li, Z.

Author_Institution

Sch. of Autom. Sci. & Electr. Eng., Beihang Univ., Beijing, China

fYear

2010

fDate

22-24 Oct. 2010

Firstpage

12

Lastpage

15

Abstract

A genetic algorithm (GA) maintained by binary heap and transitive reduction for addressing partner selection problem (PSP) in virtual enterprise is proposed. Compared with the traditional GA for addressing PSP, there are three creative contributions in the proposed algorithm. They are: (a) In order to reduce the time complexity of PSP, an algorithm for generating the directed acrylic graph that represents the precedence relationship among subprojects in PSP is designed firstly; (b) An algorithm for simplifying the graph is proposed; and (c) An algorithm using the turntable maintained by the binary heap to select the better solutions generated during the evolution is proposed. The simulation and experiment results demonstrated that the proposed algorithm has good effectiveness and performance for addressing PSP.

Keywords

directed graphs; genetic algorithms; virtual enterprises; GA; binary heap; directed acrylic graph; genetic algorithm; partner selection problem; time complexity; transitive reduction; virtual enterprise; Gallium; binary heap; genetic algorithm (GA); partner selection problem (PSP); transitive reduction;

fLanguage

English

Publisher

ieee

Conference_Titel

Intelligent Computing and Integrated Systems (ICISS), 2010 International Conference on

Conference_Location

Guilin

Print_ISBN

978-1-4244-6834-8

Type

conf

DOI

10.1109/ICISS.2010.5654994

Filename

5654994