An ant colony system for solving fuzzy flow shop scheduling problem

  • Authors

    • Nasser Shahsavari Pour Islamic Azad University, Iran
    • Mohammad hossein Abolhasani Ashkezari
    • Hamed Mohammadi Andargoli
    https://doi.org/10.14419/ijet.v1i2.23

    Received date: April 11, 2012

    Accepted date: April 18, 2012

    Published date: April 28, 2012

  • Abstract

    During the past years, the flow shop has been regarded by many researchers and some extensive investigations have been done on this respect. Flow Shop includes n works performed on m machines in a same sequence. It is very difficult in the real world to determine the exact process time of an operation on a machine. Therefore, we consider in this article the process time as trapezoidal fuzzy numbers. Our purpose is that we obtain a sequence of works using such fuzzy numbers in order to minimize maximum fuzzy time of completion entire jobs or fuzzy makespan. We offered an optimization algorithm of Ant Colony System (ACS) to solve this problem. Finally, we present computational results for explanation and comparison with other articles in future.

  • References

    1. S.M. Johnson, Optimal two and three–stage production schedules with setup times included, Naval Research logistics Quarterly 1 (1) (1954) 61-68.
    2. M. Widmer, A. Hertz, A new heuristic method for the flow shop sequencing problem, European Journal of Operational Research 42 (2) (1989) 186-193.
    3. J.N.D. Gupta, E.F. Stafford, Flow shop scheduling research after five decade, European Journal of Operational Research 169 (3) (2006) 699-711.
    4. D.S. Palmer, Sequencing jobs through a multi stage process in the minimum total time : A quick method of obtaining a near optimum, Operation Research Quarterly 16 (1) (1965) 101-107.
    5. M.L. Smith, R.A. Dudek, A general algorithm for solution of the n-job, m-machine sequencing problem of the flow shop, Operations Research 15 (1967) 71-82.
    6. J.N.D. Gupta, An improved combinatorial algorithm for the flow shop scheduling problem, Operations Research 19 (7) (1971) 1753-1758.
    7. D.G. Dannenbring, An evaluation of flow shop sequencing heuristics, Management Science 23 (11) (1977) 1174-1182.
    8. M.E. Nawaz, E. Enscore, I. Ham, A heuristic algorithm for the m-machine, n-job flow shop sequencing problem, Omega 11 (1) (1983) 91-95.
    9. T.S. Hundal, J. Rajgopal, An extension of palmer's heuristic for the flow-shop scheduling problem, International Journal of production Research 26 (1988) 1119-1124.
    10. M. Pinedo, Scheduling: theory, algorithms, and systems, Prentice Hall, Englewood Cliffs, NJ, 1995.
    11. E. Ignall, L.E. Schrage, Application of the branch and bound technique to some flow shop scheduling problems, Operations Research 13 (3) (1965) 400-412.
    12. G.B. McMahon, P.G. Burton, Flow shop scheduling with the branch and bound method, Operations Research 15 (1967) 473-481.
    13. P.J.M. Van Laarhoven, E.H.L. Aarts, Simulated annealing: theory and applications, Dordrecht: D.Reidel publ.Co, 1987.
    14. I.H. Osman, C.N. potts, Simulated annealing for permutation Flow-shop scheduling, Omega 17 (6) (1989) 551-557.
    15. F.A. Ogbu, D.K. Smith, Simulated annealing for the permutation flow shop problem, Omega 19 (1) (1991) 64-67.
    16. D.E. Goldberg, Genetic algorithms in search, optimization and machine learning, Reading, MA: Addison- Wesley, 1989.
    17. C. Reeves, A genetic algorithm for flow shop sequencing, Computers and Operations Research 22 (1) (1995) 5-13.
    18. E. Nowicki, C. Smutnicki, A fast tabu search algorithm for the permutation flow shop problem, European Journal of Operational Research 91 (1) (1996) 160-175.
    19. K.C. Ying, C.J. Liao, An ant colony system for permutation flow shop sequencing, Computers and Operations Research 31 (5) (2004) 791-801.
    20. B. Yagmahan, M.M. Yenisey, Ant colony optimization for multi-objective flow shop scheduling problem, Computers and Industrial Engineering 54 (2008) 411-420.
    21. S. Khalouli, F. Ghedjati, A. Hamzaoui, A meta-heuristic approach to solve a JIT scheduling problem in hybrid flowshop, Engineering Applications of Artificial Intelligence 23 (5) (2010) 765-771.
    22. T. Stutzle, M. Dorigo, The ant colony optimization metaheuristic: Algorithms, applications, and advances, Handbook of metaheuristics, Norwell,MA: kluwer Academic publishers, 2003, pp.251-285.
    23. M. Dorigo, Optimization, learning and natural algorithm, Ph.D. thesis, DEI, Politecnico Di Milano, Italy, 1992.
    24. M. Dorigo, L.M. Gambardella, Ant colony system: a cooperative learning approach to the traveling salesman problem, IEEE transactions on Evolutionary computation 1 (1) (1997) 53-66.
    25. T. Stutzle, H. Hoos, Improvements on the Ant-system: Introducing max–min ant system, Computer and Information Science (1996) 1-23.
    26. T. Stutzle, H. Hoos, The max–min ant system and local Search for the traveling salesman problem, Proceedings of 1997 IEEE International Conference on Evolutionary Computation, IEEE press, 1997, pp.309-314.
    27. B. Bullnheimer, R.F. Hartl, C. Strauss, A new rank based version of the Ant system: A computational study, Central European Journal for Operations Research and Economics 7 (1) (1999) 25-38.
    28. O. Cordon, I. ferandez de Viana, F. Herrera, L. Moreno, A new aco model integrating evolutionary computation concepts: the best–worst Ant system, universito libre de Bruxelles, Belgium, 2000, pp. 22-29.
    29. L.M. Gambardella, M. Dorigo, Ant–Q: A reinforcement learning approach to the traveling salesman problem, Proceedings of the twelfth international conference on machine learning, morgan kaufman, 1995, pp.252-260.
    30. P.M. Stanfield, R.E. King, J.A. Joines, Scheduling arrivals to a production system in a fuzzy environment, European Journal of Operational Research 93 (1) (1996) 75-87.
    31. T.P. Hong, T.T. Wang, Fuzzy flexible flow shops at two machine centers for continuous fuzzy domains, Information Sciences 129 (1-4) (2000) 227-237.
    32. J. Balasubramanian, I.E. Grossmann, Scheduling multi-stage flow shops with parallel units: an alternative approach to optimization under uncertainty, Computer Aided Chemical Engineering 15 (2003) 154-159.
    33. Y. Tsujimura, S.H. Park, I.S. Chang, M. Gen, An effective method for solving flow shop scheduling problems with fuzzy processing times, Computers and Industrial Engineering 25 (1-4) (2003) 239-242.
    34. C.S. Mccahon, L.E. Stanley, Fuzzy job sequencing for a flow shop, European Journal of Operational Research 62 (3) (2003) 294-301.
    35. B. Javadi, M. Saidi-Mehrabad, A. Haji, I. Mahdavi, No-wait flow shop scheduling using fuzzy multi-objective linear programming, Journal of the Franklin Institute 345 (2008) 452-467.
    36. S. Sadi nezhad, R. Ghaleh Assadi, Preference ratio-based maximum operator approximation and its application in fuzzy flowshop scheduling, Applied Soft Computing 8 (1) (2008) 759-766.
    37. H. Khademi Zare, M.B. Fakhrzad, Solving flexible flow-shop problem with a hybrid genetic algorithm and data mining: A fuzzy approach, Expert Systems with Applications 38 (6) (2011) 7609-7615.
    38. P.J. Lai, H.C. Wu, Evaluate the fuzzy completion times in the fuzzy flow shop scheduling problems using the Virus-Evolutionary genetic algorithms, Applied Soft Computing 11 (8) (2011) 4540-4550.
    39. S.G. Li, Y.L. Rong, The reliable design of one-piece flow production system using fuzzy ant colony optimization, Computers and Operations Research 36 (5) (2009) 1656-1663.
    40. B. Cheng, K. Li, B. Chen, Scheduling a single batch-processing machine with non-identical job sizes in fuzzy environment using an improved ant colony optimization, Journal of Manufacturing Systems 29 (1) (2010) 29-34.
    41. Y. Deng, Z. Zhenfu, L. Qi, Ranking fuzzy numbers with an area method using radius of gyration, Computers and Mathematics with Applications 51 (6-7) (2006) 1127-1136.
    42. E. Taillard, Benchmarks for basic scheduling problems, European Journal of Operational Research 64 (2) (1993) 278-285.

  • Downloads

  • How to Cite

    Pour, N. S., Ashkezari, M. hossein A., & Andargoli, H. M. (2012). An ant colony system for solving fuzzy flow shop scheduling problem. International Journal of Engineering and Technology, 1(2), 44-57. https://doi.org/10.14419/ijet.v1i2.23