Skip to main content
SpringerLink
Log in

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

  • Published:
Applied Intelligence Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10

Similar content being viewed by others

References

  1. Talbi E (2009) Metaheuristics from design to implementation. Wiley, Hoboken

    MATH  Google Scholar 

  2. Kasana HS, Kumar KD (2011) Introductory operations research: theory and applications. Springer, Berlin

    MATH  Google Scholar 

  3. Werner F (2011) Genetic algorithms for shop scheduling problems: a survey. Preprint, 11, 31

  4. Leung JY (ed) (2004) Handbook of scheduling: algorithms, models, and performance analysis. CRC Press

  5. Brucker P (2007) Scheduling algorithms. Springer, Berlin

    MATH  Google Scholar 

  6. Allahverdi A, Ng CT, Cheng TE, Kovalyov MY (2008) A survey of scheduling problems with setup times or costs. Eur J Oper Res 187(3):985–1032

    Article  MathSciNet  MATH  Google Scholar 

  7. Gendreau M, Hertz A, Laporte G (1996) The traveling salesman problem with backhauls. Comput Oper Res 23(5):501–508

    Article  MathSciNet  MATH  Google Scholar 

  8. Renaud J, Boctor FF, Ouenniche J (2000) A heuristic for the pickup and delivery traveling salesman problem. Comput Oper Res 27(9):905–916

    Article  MathSciNet  MATH  Google Scholar 

  9. Savelsbergh M, Sol M (1995) The general pickup and delivery problem. Transport Sci 29:17–29

    Article  MATH  Google Scholar 

  10. Carrabs F, Cordeau JF, Laporte G (2007) Variable neighborhood search for the pickup and delivery traveling salesman problem with LIFO loading. Informs J Comput 19(4):618–632

    Article  MathSciNet  MATH  Google Scholar 

  11. Anghinolfi D, Montemanni R, Paolucci M, Gambardella LM (2011) A hybrid particle swarm optimization approach for the sequential ordering problem. Comput Oper Res 38(7):1076–1085

    Article  MathSciNet  MATH  Google Scholar 

  12. Montemanni R, Smith DH, Gambardella LM (2007) Ant colony systems for large sequential ordering problems. In: Swarm intelligence symposium, 2007. SIS 2007. IEEE (pp 60–67). IEEE

    Google Scholar 

  13. Yun YS, Moon C (2011) Genetic algorithm approach for precedence constrained sequencing problems. J Intell Manuf 22(3):379–388

    Article  Google Scholar 

  14. Yun YS, Chung H, Moon C (2013) Hybrid genetic algorithm approach for precedence-constrained sequencing problem. Comput Ind Eng 65(1):137–147

    Article  Google Scholar 

  15. Moon C, Kim J, Choi G, Seo Y (2002) An efficient genetic algorithm for the traveling salesman problem with precedence constraints. Eur J Oper Res 140(3):606–617

    Article  MathSciNet  MATH  Google Scholar 

  16. Lenstra JK, Rinnooy Kan AHG (1978) Complexity of scheduling under precedence constraints. Oper Res 26(1):22–35

    Article  MathSciNet  MATH  Google Scholar 

  17. Lawler EL (1978) Sequencing jobs to minimize total weighted completion time subject to precedence constraints. Ann Discrete Math 2:75–90

    Article  MathSciNet  MATH  Google Scholar 

  18. Chen C (1990) AND/OR Precedence constraint traveling salesman problem and its application to assembly schedule generation. In: Proceedings of the IEEE international conference on systems, man and cybernetics, pp 560–562

    Google Scholar 

  19. He W, Kusiak A (1992) Scheduling manufacturing systems. Comput Ind 20(2):163–175

    Article  Google Scholar 

  20. Lambert AJD (2006) Exact methods in optimum disassembly sequence search for problems subject to sequence dependent costs. Omega Int J Manage S 34(6):538–549

    Article  Google Scholar 

  21. Duman E, Or I (2004) Precedence constrained TSP arising printed circuit board assembly. Int J Prod Res 42(1):67–78

    Article  MATH  Google Scholar 

  22. Chan FTS, Chung S (2004) A multi-criterion genetic algorithm for order distribution in a demand driven supply chain. Int J Comp Integ M 17(4):339–351

    Article  Google Scholar 

  23. Altiparmak F, Gen M, Lin L, Paksov T (2006) A genetic algorithm approach for multi-objective optimization of supply chain networks. Comput Ind Eng 51(1):196–215

    Article  Google Scholar 

  24. Altiparmak F, Gen M, Lin L, Karaoglan I (2007) A steady-state genetic algorithm for multi-product supply chain network design. Comput Ind Eng 56(2):521–537

    Article  Google Scholar 

  25. Gen M, Cheng R, Lin L (2008) Network models and optimization: multi objective genetic algorithm approach. Springer, London

    MATH  Google Scholar 

  26. Gen M, Lin L, Zhang H (2009) Evolutionary techniques for optimization problems in integrated manufacturing system: state-of-the-art-survey. Comput Ind Eng 56(3):779–808

    Article  Google Scholar 

  27. Rajabioun R (2011) Cuckoo optimization algorithm. Appl Soft Comput 11(8):5508–5518

    Article  Google Scholar 

  28. Mahmoudi S, Lotfi S (2015) Modified cuckoo optimization algorithm MCOA to solve graph coloring problem. Appl Soft Comput 33:48–64

    Article  Google Scholar 

  29. Shokri-Ghaleh H, Alfi A (2014) Optimal synchronization of teleoperation systems via cuckoo optimization algorithm. Nonlinear Dynam 78(4):2359–2376

    Article  MathSciNet  Google Scholar 

  30. Khajeh M, Golzary AR (2014) Synthesis of zinc oxide nanoparticles-chitosan for extraction of methyl orange from water samples: cuckoo optimization algorithm-artificial neural network. Spectrochim Acta A 15(131):189–194

    Article  Google Scholar 

  31. Stryczek R (2014) A meta-heuristic for fast machining error compensation. J Intell Manuf. doi:10.1007/s10845-014-0945-0

  32. Kumar AMK, Singh GK (2013) EEG/ERP adaptive noise canceller design with Controlled Search Space CSS approach in cuckoo and other optimization algorithms. IEEE ACM T Comput Bi 10(6):1491–1504

    Google Scholar 

  33. Abolpour B, Mohebbi A (2013) Estimation of the compressive strength of 28-day-old concrete by use of an adaptive cuckoo–fuzzy logic model. Res Chem Intermediat 39(9):4001–4009

    Article  Google Scholar 

  34. Teimouri R, Sohrabpoor H (2013) Application of adaptive neuro fuzzy inference system and cuckoo optimization algorithm for analyzing electro chemical machining process. Front Mech Eng 8(4):429–442

    Article  Google Scholar 

  35. Mellal MA, Williams EJ (2014). doi:10.1007/s10845-014-0925-4

  36. Ascheuer N, Junger M, Reinelt G (2000) Branch & cut algorithm for the asymmetric traveling salesman problem with precedence constraints. Comput Optim Appl 17(1):61–84

    Article  MathSciNet  MATH  Google Scholar 

  37. Mingozzi A, Bianco L, Ricciardelli S (1997) Dynamic programming strategies for the travelling salesman problem with time windows and precedence constraints. Oper Res 45(3):365–367

    Article  MathSciNet  MATH  Google Scholar 

  38. Pedersen CR, Rasmussen RV, Andersen KA (2007) Solving a large-scale precedence constrained scheduling problem with elastic jobs using tabu search. Comput Oper Res 34(7):2025–2042

    Article  MATH  Google Scholar 

  39. Li WD, Ong SK, Nee AYC (2002) Hybrid genetic algorithm and simulated annealing approach for the optimization of process plans for prismatic parts. Int J Prod Res 40(8):1899–1922

    Article  MATH  Google Scholar 

  40. Su Q (2007) Applying case-based reasoning in assembly sequence planning. Int J Prod Res 45(1):29–47

    Article  MATH  Google Scholar 

  41. Sung J, Jeong B (2014) An adaptive evolutionary algorithm for traveling salesman problem with precedence constraints. Sci World Jo. doi:10.1155/2014/313767

  42. Yang X, Deb S (2009) Cuckoo search via le’vy flights. In: Proceedings of the IEEE world congress on nature & biologically inspired computing, naBIC, pp 210–214

    Google Scholar 

  43. Ouaarab A, Ahiod B, Yang X (2014) Discrete cuckoo search algorithm for the travelling salesman problem. Neural Comput Appl 24(7):1659–1669

    Article  Google Scholar 

  44. Gen M, Altiparmak F, Lin L (2006) A genetic algorithm for two-stage transportation problem using priority-based encoding. OR Spectrum 28(3):337–354

    Article  MathSciNet  MATH  Google Scholar 

  45. Gen M, Cheng R (2000) Genetic algorithms and engineering optimization. Wiley, New Jersey

    Google Scholar 

  46. Moon C, Seo Y (2005) Advanced planning for minimizing makespan with load balancing in multi-plants chain. Int J Prod Res 43(20):4381–4396

    Article  Google Scholar 

  47. Phadke SM (1989) Quality engineering using robust design. Prentice Hall, New Jersey

    Google Scholar 

  48. Hsu C (2012) Improving the lighting performance of a 3535 packaged hi-power LED using genetic programming, quality loss functions and particle swarm optimization. Appl Soft Comput 12(9):2933–2947

    Article  Google Scholar 

  49. Tanga CY, Wub YL, Peng CC (2012) Fundamental matrix estimation by multi objective genetic algorithm with Taguchi’s method. Appl Soft Comput 12(1):553–558

    Article  Google Scholar 

  50. Maadi M, Javidnia M (2016) Forest optimization algorithm for resource-constrained project scheduling problem. In: 13th international management conference, Tehran

Download references

Author information

Authors and Affiliations

  1. School of Engineering, Damghan University, Damghan, Iran

    Mansoureh Maadi

  2. School of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran

    Mohammad Javidnia

  3. School of Mathematics and Computer Science, Damghan University, Damghan, Iran

    Rohollah Ramezani

Authors
  1. Mansoureh Maadi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mohammad Javidnia
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Rohollah Ramezani
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mansoureh Maadi.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Maadi, M., Javidnia, M. & Ramezani, R. Modified Cuckoo Optimization Algorithm (MCOA) to solve Precedence Constrained Sequencing Problem (PCSP). Appl Intell 48, 1407–1422 (2018). https://doi.org/10.1007/s10489-017-1022-0

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10489-017-1022-0

Keywords

Search

Navigation