A novel search algorithm based on waterweeds reproduction principle for job shop scheduling problem | The International Journal of Advanced Manufacturing Technology Skip to main content
Springer Nature Link
Log in

A novel search algorithm based on waterweeds reproduction principle for job shop scheduling problem

  • ORIGINAL ARTICLE
  • Published:
The International Journal of Advanced Manufacturing Technology Aims and scope Submit manuscript

Abstract

Along with the mushroom development of new information technology, scheduling plays an increasing important role in manufacturing systems. A new search algorithm which imitates reproduction principle of waterweeds in searching for water sources is proposed for solving the job shop scheduling problems (JSSPs). Inspired by the swarm intelligence in waterweeds’ collaborative behavior and inheriting their strong survivability, the new waterweeds (WW) algorithm with few user-defined parameters and simple structure shows remarkable performance in solving continuous unconstrained optimization problems, which is proved by two experiments against five well-known benchmark functions. Furthermore, according to special needs of JSSPs solving, a series of modifications are introduced into original WW algorithm and the computational experiments on a set of problem instances indicate that the new discrete WW algorithm has competitive effectiveness and efficiency in comparison with other classical JSSPs solving methods in the literature. Successful application of WW algorithm in solving JSSPs illustrates its bright prospect in manufacturing field and other related optimization areas.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Adams J, Balas E, Zawack D (1988) The shifting bottleneck procedure for job shop scheduling. Manag Sci 34(3):391–401

    Article  MathSciNet  MATH  Google Scholar 

  2. Applegate D, Cook W (1991) A computational study of the job-shop scheduling problem. ORSA J Comput 3(2):149–156

    Article  MATH  Google Scholar 

  3. Bagheri A, Zandieh M, Mahdavi I, Yazdani M (2010) An artificial immune algorithm for the flexible job-shop scheduling problem. Futur Gener Comput Syst 26(4):533–541

    Article  Google Scholar 

  4. Balas E (1969) Machine sequencing via disjunctive graphs: an implicit enumeration algorithm. Oper Res 17(6):941–957

    Article  MathSciNet  MATH  Google Scholar 

  5. Balas E, Vazacopoulos A (1998) Guided local search with shifting bottleneck for job shop scheduling. Manag Sci 44(2): 262–275

    Article  MATH  Google Scholar 

  6. Bastos Filho CJ, de Lima Neto FB, Lins AJ, Nascimento AI, Lima MP (2009) Fish school search. In: Nature-inspired algorithms for optimisation. Springer, pp 261–277

  7. Brooks GH, White CR (1965) An algorithm for finding optimal or near optimal solutions to production scheduling problem. J Ind Eng 16(1):34

    Google Scholar 

  8. Brucker P, Jurisch B, Sievers B (1994) A branch and bound algorithm for the job-shop scheduling problem. Discret Appl Math 49(1):107–127

    Article  MathSciNet  MATH  Google Scholar 

  9. Carlier J, Pinson É (1989) An algorithm for solving the job-shop problem. Manag Sci 35(2):164–176

    Article  MathSciNet  MATH  Google Scholar 

  10. Coello CAC, Rivera DC, Cortes NC (2003) Use of an artificial immune system for job shop scheduling. In: Artificial Immune Systems. Springer, pp 1–10

  11. De Castro LN, Von Zuben FJ (1999) Artificial immune systems: Part i–basic theory and applications. Universidade Estadual de Campinas, Dezembro de, Tech Rep

  12. Dell’Amico M, Trubian M (1993) Applying tabu search to the job-shop scheduling problem. Ann Oper Res 41(3):231–252

    Article  MATH  Google Scholar 

  13. Dominic PD, Kaliyamoorthy S, Kumar MS (2004) Efficient dispatching rules for dynamic job shop scheduling. Int J Adv Manuf Technol 24(1-2):70–75

    Google Scholar 

  14. Dorigo M, Maniezzo V, Colorni A (1996) Ant system: optimization by a colony of cooperating agents. IEEE Trans Syst, Man, and Cybern Part B: Cybern 26(1):29–41

    Article  Google Scholar 

  15. Engelbrecht AP (2005) Fundamentals of computational swarm intelligence, vol 1. Wiley, Chichester

    Google Scholar 

  16. Falkenauer E, Bouffouix S (1991) A genetic algorithm for job shop. In: Proceedings of the IEEE international conference on robotics and automation, pp 824–82

  17. Fayad C, Petrovic S (2005) A fuzzy genetic algorithm for real-world job shop scheduling. In: Innovations in applied artificial intelligence, Springer, pp 524–533

  18. Fisher H, Thompson GL (1963) Probabilistic learning combinations of local job-shop scheduling rules. Industrial scheduling 3:225–251

    Google Scholar 

  19. Florian M, Trepant P, McMahon G (1971) An implicit enumeration algorithm for the machine sequencing problem. Manag Sci 17(12):B–782

    Article  MathSciNet  MATH  Google Scholar 

  20. French S (1982) Sequencing and scheduling: an introduction to the mathematics of the job-shop, vol 683. Ellis Horwood, Chichester

    MATH  Google Scholar 

  21. Gao L, Zhang G, Zhang L, Li X (2011) An efficient memetic algorithm for solving the job shop scheduling problem. Comput Ind Eng 60(4):699–705

    Article  Google Scholar 

  22. Garey MR, Johnson DS, Sethi R (1976) The complexity of flowshop and jobshop scheduling. Math Oper Res 1(2):117–129

    Article  MathSciNet  MATH  Google Scholar 

  23. Ge H, Du W, Qian F (2007) A hybrid algorithm based on particle swarm optimization and simulated annealing for job shop scheduling. In: 3rd international conference on natural computation, ICNC 2007. IEEE, vol 3, pp 715–719

  24. Giffler B, Thompson GL (1960) Algorithms for solving production-scheduling problems. Oper Res 8 (4):487–503

    Article  MathSciNet  MATH  Google Scholar 

  25. Gonċalves JF, de Magalhães Mendes JJ, Resende MG (2005) A hybrid genetic algorithm for the job shop scheduling problem. Eur J Oper Res 167(1):77–95

    Article  MathSciNet  MATH  Google Scholar 

  26. Greenberg HH (1968) A branch-bound solution to the general scheduling problem. Oper Res 16(2):353–361

    Article  MATH  Google Scholar 

  27. Huang RH (2010) Multi-objective job-shop scheduling with lot-splitting production. Int J Prod Econ 124(1):206–213

    Article  Google Scholar 

  28. Jawahar N, Aravindan P, Ponnambalam S (1998) A genetic algorithm for scheduling flexible manufacturing systems. Int J Adv Manuf Technol 14(8):588–607

    Article  Google Scholar 

  29. Karaboga D (2005) An idea based on honey bee swarm for numerical optimization. Tech. rep., Technical report-tr06, Erciyes university, engineering faculty, computer engineering department

  30. Karaboga D, Basturk B (2008) On the performance of artificial bee colony (abc) algorithm. Appl Soft Comput 8(1):687–697

    Article  Google Scholar 

  31. Kennedy J, Kennedy JF, Eberhart RC (2001) Swarm intelligence. Morgan Kaufmann

  32. Krink T, Filipic B, Fogel GB (2004) Noisy optimization problems—a particular challenge for differential evolution?. In: Congress on evolutionary computation, CEC2004. IEEE, vol 1, pp 332–339

  33. Krishnanand K, Ghose D (2006) Glowworm swarm based optimization algorithm for multimodal functions with collective robotics applications. Multiagent and Grid Systems 2(3):209–222

    MATH  Google Scholar 

  34. Lacomme P, Larabi M, Tchernev N (2013) Job-shop based framework for simultaneous scheduling of machines and automated guided vehicles. Int J Prod Econ 143(1):24–34

    Article  Google Scholar 

  35. Lageweg B, Lenstra J, Rinnooy Kan A (1977) Job-shop scheduling by implicit enumeration. Manag Sci 24(4):441–450

    Article  MathSciNet  MATH  Google Scholar 

  36. Li J, Tao F, Cheng Y, Zhao L (2015) Big data in product lifecycle management. Int J Adv Manuf Technol 81:667–684

    Article  Google Scholar 

  37. Li Jq, Yx Pan (2013) A hybrid discrete particle swarm optimization algorithm for solving fuzzy job shop scheduling problem. Int J Adv Manuf Technol 66(1–4):583–596

    Article  Google Scholar 

  38. Li JQ, Pan QK, Suganthan P, Chua T (2011) A hybrid tabu search algorithm with an efficient neighborhood structure for the flexible job shop scheduling problem. Int J Adv Manuf Technol 52(5-8):683–697

    Article  Google Scholar 

  39. Li T, Wang C, Wang W, Su W (2005) A global optimization bionics algorithm for solving integer programming-plant growth simulation algorithm. Syst Eng Theory Pract 25(1):76–85

    Google Scholar 

  40. de Lima Neto F, Lins A, Nascimento AI, Lima MP et al (2008) A novel search algorithm based on fish school behavior. In: IEEE international conference on systems, man and cybernetics, SMC 2008. IEEE, pp 2646–2651

  41. Martin PD (1996) A time-oriented approach to computing optimal schedules for the job-shop scheduling problem. Cornell University

  42. Moslehi G, Mahnam M (2011) A pareto approach to multi-objective flexible job-shop scheduling problem using particle swarm optimization and local search. Int J Prod Econ 129(1): 14–22

    Article  Google Scholar 

  43. Naderi B, Ghomi SF, Aminnayeri M, Zandieh M (2011) Scheduling open shops with parallel machines to minimize total completion time. J Comput Appl Math 235(5):1275–1287

    Article  MathSciNet  MATH  Google Scholar 

  44. Nowicki E, Smutnicki C (1996) A fast taboo search algorithm for the job shop problem. Manag Sci 4283: 137–160(6):797–813

    Article  MATH  Google Scholar 

  45. Passino KM (2002) Biomimicry of bacterial foraging for distributed optimization and control. IEEE Control Syst 22(3): 52–67

    Article  MathSciNet  Google Scholar 

  46. Perregaard M, Clausen J (1998) Parallel branch-and-bound methods for the job-shop scheduling problem. Ann Oper Res 83:137–160

    Article  MathSciNet  MATH  Google Scholar 

  47. Pezzella F, Merelli E (2000) A tabu search method guided by shifting bottleneck for the job shop scheduling problem. Eur J Oper Res 120(2):297–310

    Article  MathSciNet  MATH  Google Scholar 

  48. Pham D, Ghanbarzadeh A, Koc E, Otri S, Rahim S, Zaidi M (2005) The bees algorithm. technical note. Manufacturing Engineering Centre, Cardiff University, UK, pp 1–57

  49. Ponnambalam S, Aravindan P, Rajesh S (2000) A tabu search algorithm for job shop scheduling. Int J Adv Manuf Technol 16(10):765–771

    Article  Google Scholar 

  50. Sha D, Hsu CY (2006) A hybrid particle swarm optimization for job shop scheduling problem. Comput Ind Eng 51(4):791–808

    Article  Google Scholar 

  51. Subramaniam V, Ramesh T, Lee G, Wong Y, Hong G (2000) Job shop scheduling with dynamic fuzzy selection of dispatching rules. Int J Adv Manuf Technol 16(10):759–764

    Article  Google Scholar 

  52. Sun D, Batta R, Lin L (1995) Effective job shop scheduling through active chain manipulation. Comput Oper Res 22(2):159–172

    Article  MATH  Google Scholar 

  53. Tao F, Zhao D, Hu Y, Zhou Z (2008) Resource service composition and its optimal-selection based on particle swarm optimization in manufacturing grid system. IEEE Trans Ind Inf 4(4): 315–327

    Article  Google Scholar 

  54. Tao F, Zhang L, Zhang Z, Nee A (2010) A quantum multi-agent evolutionary algorithm for selection of partners in a virtual enterprise. CIRP Ann Manuf Technol 59(1):485–488

    Article  Google Scholar 

  55. Tao F, Zhao D, Yefa H, Zhou Z (2010) Correlation-aware resource service composition and optimal-selection in manufacturing grid. Eur J Oper Res 201(1):129–143

    Article  MATH  Google Scholar 

  56. Tao F, Zhang L, Venkatesh V, Luo Y, Cheng Y (2011) Cloud manufacturing: a computing and service-oriented manufacturing model. Proc IME B J Eng Manufact 225(10):1969–1976

    Article  Google Scholar 

  57. Tao F, LaiLi Y, Xu L, Zhang L (2013) Fc-paco-rm: a parallel method for service composition optimal-selection in cloud manufacturing system. IEEE Trans Ind Inf 9(4):2023–2033

    Article  Google Scholar 

  58. Tao F, Cheng Y, Da Xu L, Zhang L, Li BH (2014a) Cciot-cmfg: cloud computing and internet of things-based cloud manufacturing service system. IEEE Trans Ind Inf 10(2):1435–1442

    Article  Google Scholar 

  59. Tao F, Feng Y, Zhang L, Liao T (2014b) Clps-ga: a case library and pareto solution-based hybrid genetic algorithm for energy-aware cloud service scheduling. Appl Soft Comput 19: 264–279

    Article  Google Scholar 

  60. Tao F, Laili Y, Liu Y, Feng Y, Wang Q, Zhang L, Xu L (2014c) Concept, principle and application of dynamic configuration for intelligent algorithms. IEEE Syst J 8(1):28–42

  61. Tao F, Zuo Y, Da Xu L, Zhang L (2014) Iot-based intelligent perception and access of manufacturing resource toward cloud manufacturing. IEEE Trans Ind Inf 10(2):1547–1557

    Article  Google Scholar 

  62. Tao F, Cheng Y, Zhang L, Nee A (2015) Advanced manufacturing systems: socialization characteristics and trends. J Intell Manuf:1–16

  63. Tao F, Li C, Liao T, Laili Y (2015) Bgm-bla: a new algorithm for dynamic migration of virtual machines in cloud computing

  64. Tao F, Zhang L, Liu Y, Cheng Y, Wang L, Xu X (2015) Manufacturing service management in cloud manufacturing: overview and future research directions. Journal of Manufacturing Science and Engineering-Transaction of the ASME 137(4):040,912-1-040,912-11

  65. Topaloglu S, Kilincli G (2009) A modified shifting bottleneck heuristic for the reentrant job shop scheduling problem with makespan minimization. Int J Adv Manuf Technol 44(7–8):781–794

    Article  MATH  Google Scholar 

  66. Vilcot G, Billaut JC (2011) A tabu search algorithm for solving a multicriteria flexible job shop scheduling problem. Int J Prod Res 49(23):6963–6980

    Article  Google Scholar 

  67. Wang L, Zheng DZ (2001) An effective hybrid optimization strategy for job-shop scheduling problems. Comput Oper Res 28(6):585–596

    Article  MathSciNet  MATH  Google Scholar 

  68. Wang L, Zhou G, Xu Y, Wang S, Liu M (2012) An effective artificial bee colony algorithm for the flexible job-shop scheduling problem. Int J Adv Manuf Technol 60(1–4):303–315

    Article  Google Scholar 

  69. Wj Xia, Zm Wu (2006) A hybrid particle swarm optimization approach for the job-shop scheduling problem. Int J Adv Manuf Technol 29(3-4):360–366

    Article  Google Scholar 

  70. Xing LN, Chen YW, Wang P, Zhao QS, Xiong J (2010) A knowledge-based ant colony optimization for flexible job shop scheduling problems. Appl Soft Comput 10(3):888–896

    Article  Google Scholar 

  71. Yang XS (2010) Nature-inspired metaheuristic algorithms. Luniver press

  72. Yang XS (2012) Flower pollination algorithm for global optimization. In: Unconventional Computation and Natural Computation, Springer, pp 240–249

  73. Zhang C, Li P, Guan Z, Rao Y (2007) A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem. Comput Oper Res 34(11):3229–3242

    Article  MathSciNet  MATH  Google Scholar 

  74. Zhang R, Song S, Wu C (2013) A hybrid artificial bee colony algorithm for the job shop scheduling problem. Int J Prod Econ 141(1):167–178

    Article  MathSciNet  Google Scholar 

  75. Zou X, Tao F, Jiang P, Gu S, Qiao K, Zuo Y, Xu L (2015) A new approach for data processing in supply chain network based on fpga. Int J Adv Manuf Technol 1–12

Download references

Author information

Authors and Affiliations

  1. School of Automation Science and Electrical Engineering, Beihang University, Beijing, 100191, China

    Lin Cheng, Qingzhen Zhang, Fei Tao, Kun Ni & Yang Cheng

Authors
  1. Lin Cheng
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Qingzhen Zhang
    View author publications

    You can also search for this author inPubMed Google Scholar

  3. Fei Tao
    View author publications

    You can also search for this author inPubMed Google Scholar

  4. Kun Ni
    View author publications

    You can also search for this author inPubMed Google Scholar

  5. Yang Cheng
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to Fei Tao.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Cheng, L., Zhang, Q., Tao, F. et al. A novel search algorithm based on waterweeds reproduction principle for job shop scheduling problem. Int J Adv Manuf Technol 84, 405–424 (2016). https://doi.org/10.1007/s00170-015-8023-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00170-015-8023-0

Keywords