Hybrid genetic algorithm approach for precedence-constrained sequencing problem

The objective of precedence-constrained sequencing problem (PCSP) is to locate the optimal sequence with the shortest traveling time among all feasible sequences. Various methods for effectively solving the PCSP have been suggested. This paper proposes a new concept of hybrid genetic algorithm (HGA) with adaptive local search scheme in order that the PCSP should be effectively solved. By the use of the adaptive local search scheme, the local search is automatically adapted into the loop of genetic algorithm. Two types of the PCSP are presented and analyzed to compare the efficiency among the proposed HGA approach and other competing conventional approaches. Finally, it is proved that the proposed HGA approach outperforms the other competing conventional approaches.

► Precedence-constrained sequencing problem (PCSP) is to locate the optimal sequence with the shortest traveling time.
► This paper proposes a new hybrid genetic algorithm (HGA) with adaptive local search scheme.
► The proposed HGA approach has the global and local search abilities by GA and iterative hill climbing method.
► Several types of the PCSP have been presented and analyzed to compare the efficiency of the proposed HGA approach.