Document Type : Original Article

Authors

Damghan University, Damghan, Iran.

Abstract

Precedence constrained sequencing problem (PCSP) is related to locate the optimal sequence with the shortest traveling time among all feasible sequences. In PCSP, precedence relations determine sequence of traveling between any two nodes. Various methods and algorithms for effectively solving the PCSP have been suggested. In this paper we propose a cuckoo search algorithm (CSA) for effectively solving PCSP. CSA is inspired by the life of a bird named cuckoo. As basic CSA at first was introduced to solve continuous optimization problem, in this paper to find the optimal sequence of the PCSP, some schemes are proposed with modifications in operators of the basic CSA to solve discrete precedence constrained sequencing problem. To evaluate the performance of proposed algorithm, several instances with different sizes from the literature are tested in this paper. Computational results show the good performance of the proposed algorithm in comparison with the best results of the literature.

Keywords

Altiparmak, F., Gen, M., Lin, L. and Paksov T., (2006), “A genetic algorithm approach for multi-objective optimization of supply chain networks”, Computers and Industrial Engineering, Vol. 51, No. 1, pp. 196-215. 
Altiparmak, F., Gen, M., Lin, L., and Karaoglan, I., (2007). “A steady-state genetic algorithm for multi-product supply chain network design”, Computers and Industrial Engineering, Vol. 56, No. 2, pp. 521–537.
Chen, C. (1990). “AND/OR precedence constraint traveling salesman problem and its application to assembly schedule generation”. IEEE international conference on Systems, Man and Cybernetics. Proceedings. 560–562. 
Chan, F. T. S., and Chung, S. H., (2004). “A multi-criterion genetic algorithm for order distribution in a demand driven supply chain”, International Journal of Computer Integrated Manufacturing, Vol. 17, No. 4, pp. 339–351.
Dasqupta, P., and Das, S., (2015). “A Discrete Inter-Species Cuckoo Search for flow shop scheduling problems”, Computers and Operations Research, Vol. 60, No. 3, pp. 111-120.
Dhivya1, M., and Sundarambal, M., (2011). “Cuckoo search for data gathering in wireless sensor networks”, International Journal of Mobile Communications, Vol. 9, No. 6, pp. 642-656.
Dhivya1, M., Sundarambal, M. and Anand L.N., (2011). “Energy efficient computation of data fusion in wireless sensor networks using cuckoo based particle approach (CBPA)”, International Journal of Communications, Network and System Sciences, Vol. 4, pp. 249-255.
Duman, E., Or, I., (2004). “Precedence constrained TSP arising printed circuit board assembly”, International Journal of Production Research, Vol. 42, No. 1, pp. 67–78.
Gandomi, A. H., Yang Xin-She and Alavi A. H., (2013). “Cuckoo search algorithm: a meta-heuristic approach to solve structural optimization problems”, Engineering with Computers, Vol. 21, No. 1, pp. 17-35 
Gen, M., Cheng, R., and Lin, L., (2008). Network models and optimization: multi objective genetic algorithm approach, Springer. England.
Gen, M., Lin, L., and Zhang, H., (2009). “Evolutionary techniques for optimization problems in integrated manufacturing system: State-of-the-art-survey”, Computers and Industrial Engineering, Vol. 56, No. 3, pp. 779–808.
He, W., Kusiak, A., (1992). “Scheduling manufacturing systems”, Computers in Industry, Vol. 20, pp. 163–175.
Lambert, A. J. D., (2006). “Exact methods in optimum disassembly sequence search for problems subject to sequence dependent costs”, Omega, Vol. 34, pp. 538–549.
Li,W. D., Ong, S. K. and Nee, A. Y. C., (2002). “Hybrid genetic algorithm and simulated annealing approach for the optimization of process plans for prismatic parts”, International Journal of Production Research, Vol. 40, No. 8, pp. 1899-1922.
Moon, C., Kim, J., Choi, G., and Seo, Y., (2002). “An efficient genetic algorithm for the traveling salesman problem with precedence constraints”, European Journal of Operational Research, Vol. 140, No. 3, pp. 606–617.
Moravej, Z., Akhlaghi, A., (2013). “A novel approach based on cuckoo search for DG allocation in distribution network”, Electrical Power and Energy Systems, Vol. 44, pp. 672-679.
Pedersen, C. R., Rasmussen, R. V. and Andersen, K. A., (2007). “Solving a large-scale precedence constrained scheduling problem with elastic jobs using Tabu search”, Computers and Operations Research, Vol. 34, No. 7, pp. 2025-2042. 
Renaud, J., Boctor, F. F., and Ouenniche, J., (2000). “A heuristic for the pickup and delivery traveling salesman problem”, Computers and Operations Research, Vol. 27, pp. 905–916.
Savelsbergh, M., and Sol, M., (1995). “The general pickup and delivery problem”, Transportation Science, Vol. 29, pp. 17–29. 
Su, Q., (2007). “Applying case-based reasoning in assembly sequence planning”, International Journal of Production Research, Vol. 45, No. 1, pp. 29–47.
Valian, E., Tavakoli, S., Mohanna, S., and Haghi, A., (2013). “Improved cuckoo search for reliability optimization problems”, Computer and Industrial Engineering, Vol. 64, pp. 459-468.
Yang, X. S., Deb, S., (2009). “Cuckoo search via le´vy flights. In: Nature & biologically inspired computing”, NaBIC 2009. World congress on, IEEE, Proceedings. 210–214.
Yang, X. S., and Deb, S., (2014). “Cuckoo search: recent advances and applications”, Neural Computing and Applications, Vol. 24, No. 1, pp. 169-174.
Yun, Y. S., and Moon, C., (2011). “Genetic algorithm approach for precedence constrained sequencing problems”, Journal of Intelligent Manufacturing, Vol. 22, No. 3, pp. 379–388. 
Yun, Y. S., Chung, H., and Moon, C., (2013). “Hybrid genetic algorithm approach for precedence-constrained sequencing problem”, Computers and Industrial Engineering, Vol. 65, pp.137-147.