رویکرد ترکیبی الگوریتم ژنتیک برای اولویت محدودیت مسئله توالی

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.

The objective of precedence-constrained sequencing problem (PCSP) is to locate the optimal sequence with the shortest traveling time through all nodes, visiting each node only once. One of the important problems in the PCSP is to consider the precedence relation between nodes i and j. The precedence relation determines the sequence of travel between the given pair of nodes, i and j; i.e., i must be visited before j. Therefore, this problem can be formulated as a traveling salesman problem (TSP) with precedence constraints. Locating an optimal sequence for the PCSP may cause a great effect, since some inefficient sequences that may be generated in the PCSP highly affect all downstream stages such as manufacturing, logistics, and networking. Nevertheless, the PCSP has been successfully applied to a number of optimization problems regarding networks, scheduling, project management, logistics, assembly flow, and routing. We can classify the studies related with the PCSP into two types. First type is to use various heuristics and second type applies artificial intelligent algorithms such as genetic algorithm (GA) in order to solve the various types of the PCSP. For first type, He and Kusiak (1992) proposed a heuristic algorithm to solve the PCSP with sequence-dependent changeover cost and precedence constraints. Savelsbergh and Sol (1995) suggested a heuristic algorithm to solve the Dial-A-Ride problem that a vehicle should transport a number of passengers, and each passenger should be transported from a given location to a specific destination point. The Dial-A-Ride problem can be displayed by a PCSP. Renaud, Boctor, and Ouenniche (2000) suggested a heuristic model that solves the pickup and delivery traveling salesman problem (TSP) which can be represented by a PCSP. Duman and Or (2004) developed a heuristic approach to solve a PCSP in a printed circuit board assembly problem. This approach initially ignores precedence relations and solves the problem as a pure TSP, and then it is applied to eliminate component damage in the resulting TSP tour. For second type, Moon, Kim, Choi, and Seo (2002) presented a GA approach with a priority-based representation procedure to solve the PCSP based on supply chain planning model. Chan and Chung (2004) proposed a multi-objective GA procedure for the order distribution problem in a demand driven logistics which can be represented by a PCSP. Altiparmak et al., 2006 and Altiparmak et al., 2007 developed multi-objective GA approach for a single-source, single and multi-product, multi-stage supply chain network design problem. This problem has various precedence constraints and is thus presented as a PCSP. Gen, Cheng, and Lin (2008) showed various types of network models with precedence constraints and the models were presented as a priority-based representation procedure in GA implementation. Gen, Lin, and Zhang (2009) suggested a network model with various pickup and delivery points. This model was displayed as a PCSP and solved by GA approach. Recently, Yun and Moon (2011) proposed a GA approach to solve various types of the PCSP. The proposed GA approach used topological sort (TS)-based representation procedure to effectively represent the PCSP. The conventional approaches mentioned above show that the PCSP is a useful tool for representing various types of industrial optimization problems with precedence constraints (Chen, 1990, Duman and Or, 2004, Gen et al., 2008, Gen et al., 2009, He and Kusiak, 1992 and Moon et al., 2002). However, there are some difficulties in modeling the PCSP. First, most of the conventional approaches may not solve the PCSPs efficiently because of its computational complexities and complicated precedence constraints. Secondly, computation time for locating the optimal solution of the PCSP highly increases with the increase of the number of nodes. Therefore, a new approach is required to overcome these difficulties. The new approach can easily handle complicated precedence constraints and effectively finds an optimal solution or sequence in the PCSP regardless of the increase of the number of nodes. This paper aims at formulating a mathematical model as well as developing a new hybrid GA (HGA) approach for effectively solving various types of the PCSP. The proposed mathematical model is formulated by modifying the standard integer programming for TSP in order to avoid computational difficulties and ambiguity. In the HGA approach, the TS-based representation procedure is used to generate a set of feasible sequences, which is used for producing the individuals of the population in the proposed HGA approach. An adaptive local search scheme is used for adaptively regulating the use of local search in the proposed HGA approach.

The objective of the PCSP is to locate the optimal sequence with the shortest traveling time among all feasible sequences. A number of industrial models for the PCSP have been constructed and many researchers have developed various approaches to effectively treat and solve the PCSP. In this paper we have proposed a new hybrid approach using GA and adaptive local search scheme, called the HGA. The proposed HGA approach has both the global search ability by GA and the local search ability by iterative hill climbing method. For implementing the proposed HGA approach, the representation scheme by TS-based representation procedure has been suggested and the iterative hill climbing method for local search has been adaptively adapted to GA loop by means of the adaptive local search scheme. Several types of the PCSP have been 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.