No Access

An Enhanced Intelligent Water Drops Algorithm for Scheduling of an Agile Manufacturing System

Ehsan Teymourian

School of Mechanical, Industrial, and Manufacturing Engineering, Oregon State University, Corvallis, OR 97331-6001, USA

Search for more papers by this author

Vahid Kayvanfar

Department of Industrial Engineering, Amirkabir University of Technology, 424 Hafez Ave., 15875-4413 Tehran, Iran

E-mail Address: v.kayvanfar@aut.ac.ir

Search for more papers by this author

GH. M. Komaki

Department of Electrical Engineering and Computer Science, Case Western Reserve University, 10900 Euclid Ave., Cleveland, OH 44106, USA

Search for more papers by this author

, and

Majtaba Khodarahmi

Department of Industrial Engineering, Mazandaran University of Science and Technology, Babol, Iran

Search for more papers by this author

https://doi.org/10.1142/S0219622016500024Cited by:23 (Source: Crossref)

Abstract

This paper deals with an agile manufacturing system with two stages where the first stage is the machining stage including a single flexible machine while the second stage is assembly stage including parallel identical assembly machines. Products have an assembly structure where their parts should be processed at the first stage and then proceed to the assembly stage. The goal is to find the parts sequence which minimizes makespan. Since the studied problem is NP-hard, enhanced intelligent water drops (EIWD) algorithm as a new swarm-based nature inspired optimization algorithm is proposed. Also, artificial immune system (AIS) algorithm has been proposed to tackle the addressed problem. Computational results based on randomly generated instances show the effectiveness of the proposed technique.

Keywords:

References

1. D. He and A. Babayan, Scheduling manufacturing systems for delayed product differentiation in agile manufacturing, International Journal of Production Research 40 (11) (2002) 2461–2481. Web of Science, Google Scholar
2. L. K. Gaafar, S. A. Masoud and A. O. Nassef, A particle swarm-based genetic algorithm for scheduling in an agile environment, Computers and Industrial Engineering 55 (3) (2008) 707–720. Web of Science, Google Scholar
3. A. Kusiak, Aggregate scheduling of a flexible machining and assembly system, IEEE Transactions on Robotic and Automation 5 (1989) 451–459. Google Scholar
4. R. L. Graham, E. L. Lawler, J. K. Lenstra and A. H. G. RinnooyKan, Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics 5 (1977) 287–326. Google Scholar
5. D. He, A. Babayan and A. Kusiak, Scheduling manufacturing systems in an agile environment, Robotics and Computer-Integratical Manufacturing 17 (1) (2001) 87–97. Web of Science, Google Scholar
6. L. K. Gaafar and S. A. Masoud, Genetic algorithms and simulated annealing for scheduling in agile manufacturing, International Journal of Production Research 43 (14) (2005) 3069–3085. Web of Science, Google Scholar
7. C. J. Liao and C. C. Liao, An ant colony optimisation algorithm for scheduling in agile manufacturing, International Journal of Production Research 46 (7) (2008) 1813–1824. Web of Science, Google Scholar
8. C. Y. Lee, T. C. E. Cheng and B. M. T. Lin, Minimizing the makespan in the 3-machine assembly-type flowshop scheduling problem, Management Science 39 (5) (1993) 616–625. Web of Science, Google Scholar
9. C. N. Potts, S. V. Sevast’Janov, V. A. Strusevich, L. N. Van Wassenhove and C. M. Zwaneveld, The two-stage assembly scheduling problem: Complexity and approximation, Operational Research 43 (1995) 346–355. Web of Science, Google Scholar
10. A. M. A. Hariri and C. N. Potts, A branch and bound algorithm for the two-stage assembly scheduling problem, European Journal of Operation Research 103 (3) (1997) 547–556. Web of Science, Google Scholar
11. A. Tozkapan, Ö. Kırca and C. S. Chung, A branch and bound algorithm to minimize the total weighted flowtime for the two-stage assembly scheduling problem, Computation Operation Research 30 (2) (2003) 309–320. Web of Science, Google Scholar
12. F. S. Al-Anzi and A. Allahverdi, A hybrid tabu search heuristic for the two-stage assembly scheduling problem, International Journal of Operational Research 3 (2) (2006) 109–119. Google Scholar
13. S. Hatami, S. Ebrahimnejad, R. Tavakkoli-Moghaddam and Y. Maboudian, Two meta-heuristics for three-stage assembly flowshop scheduling with sequence-dependent setup times, International Journal of Advanced Manufacturing Technology 50 (2010) 1153–1164. Web of Science, Google Scholar
14. I. Mahdavi, G. M. Komaki and V. Kayvanfar, Aggregate hybrid flowshop scheduling with assembly operations, in 18th IEEE, Conference on Industrial Engineering & Engineering Management (IE&EM), (2011) pp. 663–667. Google Scholar
15. M. Yokoyama, Hybrid flow-shop scheduling with assembly operations, International Journal of Production Economics 73 (2) (2001) 103–116. Web of Science, Google Scholar
16. M. Yokoyama, Flow-shop scheduling with setup and assembly operations, European Journal of Operational Research 187 (3) (2008) 1184–1195. Web of Science, Google Scholar
17. P. Fattahi, S. M. H. Hosseini and F. Jolai, A mathematical model and extension algorithm for assembly flexible flow shop scheduling problem, International Journal of Advanced Manufacturing Technology 65 (2013) 787–802. Web of Science, Google Scholar
18. H. Shah-Hosseini, Problem solving by intelligent water drops, in IEEE Congr. on Evolutionary Computation (CEC) 2007, pp. 3226–3231. Google Scholar
19. H. Shah-Hosseini, Intelligent water drops algorithm: A new optimization method for solving the multiple knapsack problem, International Journal of Intelligence Computational Cybernetics 1 (2) (2008) 193–212. Google Scholar
20. H. Shah-Hosseini, The intelligent water drops algorithm: A nature-inspired swarm-based optimization algorithm, International Journal of Bio-Inspired Computing 1 (1) (2009) 71–79. Web of Science, Google Scholar
21. I. Kamkar, M. R. Akbarzadeh-T and M. Yaghoobi Intelligent water drops a new optimization algorithm for solving the vehicle routing problem, in IEEE Conference on Systems Man and Cybernetics (SMC), pp. 4142–4146. Google Scholar
22. S. H. Niu, S. K. Ong and A. Y. C. Nee, An improved intelligent water drops algorithm for achieving optimal job-shop scheduling solutions, Intranational Journal of Production Research 50 (15) (2012) 4192–4205. Web of Science, Google Scholar
23. Z. Booyavi, E. Teymourian, G. M. Komaki and S. Sheikh, An improved optimization method based on the intelligent water drops algorithm for the vehicle routing problem, IEEE Symp. Computational Intelligence in Production and Logistics Systems (CIPLS) (2014) 59–66. Google Scholar
24. V. Kayvanfar and E. Teymourian, Hybrid intelligent water drops algorithm to unrelated parallel machines scheduling problem: A just-in-time approach, International Journal of Production Research 52 (19) (2014) 5857–5879. Web of Science, Google Scholar
25. X. Dong, H. Huang and P. Chen, An iterated local search algorithm for the permutation flowshop problem with total flowtime criterion, Computers and Operations Research 36 (5) (2009) 1664–1669. Web of Science, Google Scholar
26. M. Zandieh, S. M. T. F. Ghomi and S. M. M. Husseini, An immune algorithm approach to hybrid flow shops scheduling with sequence-dependent setup times, Applied Mathematics and Computations 180 (1) (2006) 111–127. Web of Science, Google Scholar
27. P. Merz and I. Huhse, An iterated local search approach for finding provably good solutions for very large TSP instances, Parallel Problem Solving from Nature–PPSN X (Springer, Berlin, Heidelberg, 2008), pp. 929–939. Google Scholar
28. P. H. V. Penna, A. Subramanian and L. S. Ochi, An iterated local search heuristic for the heterogeneous fleet vehicle routing problem, Journal of Heuristics 19 (2) (2013) 201–232. Web of Science, Google Scholar
29. H. R. Lourenço, O. C. Martin and T. Stutzle, Iterated local search, arXiv: math/0102188, 2001. Google Scholar
30. X. S. Yang and S. Deb, Cuckoo search via Lévy flights, Proc. World Congress on Nature & Biologically Inspired Computing, 2009, NaBIC 2009 (IEEE, 2009), pp. 210–214. Google Scholar
31. A. R. Mehrabian and C. Lucas, A novel numerical optimization algorithm inspired from weed colonization, Ecological Informatics 1 (4) (2006) 355–366. Web of Science, Google Scholar
32. L. N. de Castro and J. Timmis, An artificial immune network for multimodal function optimization, in Proc. 2002 Congress on Evolutionary Computation, IEEE 2002, CEC’02, Vol. 1, pp. 699–704. Google Scholar
33. A. A. Freitas and J. Timmis, Revisiting the foundations of artificial immune systems for data mining, IEEE Transactions on Evolutionary Computation 11 (4) (2007) 521–540. Web of Science, Google Scholar
34. O. Engin and A. Döyen, A new approach to solve hybrid flow shop scheduling problems by artificial immune system, Future Generation Computer System 20 (6) (2004) 1083–1095. Web of Science, Google Scholar
35. M. Chandrasekaran, P. Asokan, S. Kumanan, T. Balamurugan and S. Nickolas, Solving job shop scheduling problems using artificial immune system, International Journal of Advanced Manufacturing Technology 31 (2006) 580–593. Web of Science, Google Scholar
36. G.-C. Luh and C.-H. Chueh, A multi-modal immune algorithm for the job-shop scheduling problem, Information Sciences 179 (2009) 1516–32. Web of Science, Google Scholar
37. F. Al-Anzi and A. Allahverdi, An artificial immune system heuristic for two-stage multi-machine assembly scheduling problem to minimize total completion time, Journal of Manufacturing Systems 32 (4) (2013) 825–830. Web of Science, Google Scholar
38. G. L. Ada and G. J. V. Nossal, The clonal selection theory, Science American 257 (1987) 50–57. Web of Science, Google Scholar
39. V. Kayvanfar, I. Mahdavi and G. H. M. Komaki, A drastic hybrid heuristic algorithm to approach to JIT policy considering controllable processing times, International Journal of Advanced Manufacturing Technology 69 (4) (2013) 257–267 1. Web of Science, Google Scholar
40. G. Kou, Y. Lu, Y. Peng and Y. Shi, Evaluation of classification algorithms using MCDM and rank correlation, International Journal of Information Technology Decision Making 11 (1) (2012) 197–225. Link, Web of Science, Google Scholar