Modified Cuckoo Optimization Algorithm (MCOA) to solve Precedence Constrained Sequencing Problem (PCSP)

摘要

In recent years, new meta-heuristic algorithms have been developed to solve optimization problems. Recently-introduced Cuckoo Optimization Algorithm (COA) has proven its excellent performance to solve different optimization problems. Precedence Constrained Sequencing Problem (PCSP) is related to locating the optimal sequence with the shortest traveling time among all feasible sequences. The problem is motivated by applications in networks, scheduling, project management, logistics, assembly flow and routing. Regarding numerous practical applications of PCSP, it can be asserted that PCSP is a useful tool for a variety of industrial planning and scheduling problems. However it can also be seen that the most approaches may not solve various types of PCSPs and in related papers considering definite conditions, a model is determined and solved. In this paper a new approach is presented for solving various types of PCSPs based on COA. Since COA at first was introduced to solve continuous optimization problems, in order to demonstrate the application of COA to find the optimal sequence of the PCSP, some proposed schemes have been applied in this paper with modifications in operators of the basic COA. In fact due to the discrete nature and characteristics of the PCSP, the basic COA should be modified to solve PSCPs. To evaluate the performance of the proposed algorithm, at first, an applied single machine scheduling problem from the literature that can be formulated as a PCSP and has optimal solution is described and solved. Then, several PCSP instances with different sizes from the literature that do not have optimal solutions are solved and results are compared to the algorithms of the literature. Computational results show that the proposed algorithm has better performance compared to presented well-known meta-heuristic algorithms presented to solve various types of PCSPs so far.