An Ant Colony System for Solving Fuzzy Flow Shop Scheduling Problem
[1]
Ghorbanali Mohammadi, Industrial Engineering Department, College of Engineering, Qom University of Technology, Qom, Iran.
[2]
Darius Mohammadi, Electrical and Computer Engineering Department, College of Engineering, Iowa State University, Ames, IA, USA.
In the recent years, many articles have studied and many researchers have worked on Flow Shop Scheduling problems. Flow Shop includes n works performed on m machines in a same sequence. It is very difficult in the real world to determine 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.
Flow Shop Scheduling Problem, Ranking Fuzzy Number, Ant Colony Optimization
[1]
Balasubramanian J. Grossmann, I.E (2003) Scheduling multistage flowshops with parallel units – an alternative approach to optimization under uncertainty. Computer Aided Chemical Engineering 15: 154-159.
[2]
Bilchev G., parmee, I.C (1995) The Ant colony Metaphor for Searching continuous Design Spaces. Proceedings of the AISB Workshop on Evolutionary Computation, University of Sheffield, UK, pp.3-4.
[3]
Bullnheimer B., Hartl, R.F., Strauss, C (1999) A new rank based version of the Ant system: A computational study. Central European Journal for Operations Research and Economics 7(1); 25-38.
[4]
Cheng B., Li, K., Chen, B (2010) 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); 29-34.
[5]
Cordon O., ferandez de Viana, I., Herrera, F., Moreno, L (2000) A new Ant colony model integrating evolutionary computation concepts: the best–worst Ant system. In M. Dorigo, M. Middendorf, and T. Stutzle, editors, Abstract proceedings of ANTS 2000- from Ant colonies to artificial Ants: A series of International workshops on Ant Algorithms, p.p.22-29, IRIDZA, universitolibre de Bruxelles, Belgium, 2000.
[6]
Dannenbring D.G (1977) An evaluation of flowshop sequencing heuristics. Management Science 23(11); 1174-1182.
[7]
Deng, Y., Zhenfu, Z. Qi, L., 2006. Ranking fuzzy numbers with an area method using radius of gyration. Computers and Mathematics with Applications 51(6-7); 1127-1136.
[8]
Dorigo M (1992) Optimization, learning and natural algorithm. Ph.D. Thesis, DEI, politecnico di Milano, Italy.
[9]
Dorigo M., Gambardella, L.M (1997) Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE transactions on Evolutionary computation 1(1); 53-66.
[10]
Gambardella L.M., Dorigo, M (1995) Ant–Q: A reinforcement learning approach to the traveling salesman problem. In Aprieditis & S. Russell (Eds). Proceedings of the twelfth international conference on machine learning (ML-95) (pp.252-260). PaloAlto: morgankaufman.
[11]
Goldberg D.E (1989) Genetic algorithms in search, optimization and machine learning. Reading, MA: Addison- Wesley.
[12]
Gupta J.N.D., Stafford, E.F (2006) Flowshop scheduling research after five decade. European Journal of Operational Research 169(3); 699-711.
[13]
Gupta J.N.D (1971) An improved combinatorial algorithm for the flowshop scheduling problem. Operations Research 19(7); 1753-1758.
[14]
Hong T.P., Wang, T.T (2000) Fuzzy flexible flowshops at two machine centers for continuous fuzzy domains. Information Sciences 129(1-4); 227-237.
[15]
Hundal T.S., Rajgopal, J (1988) An extension of palmer's heuristic for the flow-shop scheduling problem. International Journal of production Research 26; 1119-1124.
[16]
Ignall E., Schrage, L.E (1965) Application of the branch and bound technique to some flow shop scheduling problems. Operations Research 13(3); 400-412.
[17]
Javadi B., Saidi-Mehrabad, M., Haji, A., Mahdavi, I (2008) No-wait flowshop scheduling using fuzzy multi-objective linear programming. Journal of the Franklin Institute 345; 452-467.
[18]
Johnson S.M. (195).Optimal two and three–stage production schedules with setup times included. Naval Research logistics Quarterly 1(1); 61-68.
[19]
Khademi Zare, H., Fakhrzad, M.B (2011) Solving flexible flow-shop problem with a hybrid genetic algorithm and data mining: A fuzzy approach. Expert Systems with Applications 38(6); 7609-7615.
[20]
Khalouli S., Ghedjati, F., Hamzaoui, A. (2010) A meta-heuristic approach to solve a JIT scheduling problem in hybrid flowshop. Engineering Applications of Artificial Intelligence 23(5); 765-771.
[21]
Lai P.J., Wu, H.C (2011) Evaluate the fuzzy completion times in the fuzzy flowshop scheduling problems using the Virus-Evolutionary genetic algorithms. Applied Soft Computing 11(8); 4540-4550.
[22]
Li S.G., Rong, Y.L (2009) The reliable design of one-piece flow production system using fuzzy ant colony optimization. Computers and Operations Research 36(5); 1656-1663.
[23]
McCahon C.S., Stanley, L.E (2003) Fuzzy job sequencing for a flowshop. European Journal of Operational Research 62(3); 294-301.
[24]
McMahon G.B., Burton, P.G (1967) Flowshop scheduling with the branch and bound method. Operations Research 15,473-481.
[25]
Nawaz M.E., Enscore, E., Ham, I (1983) A heuristic algorithm for the m-machine, n-job flowshop sequencing problem. Omega 11(1); 91-95.
[26]
Nowicki E., Smutnicki, C (1996) A fast tabu search algorithm for the permutation flow shop problem. European Journal of Operational Research 91(1); 160-175.
[27]
OgbuF. A., Smith, D. K (1991) Simulated annealing for the permutation flow shop problem. Omega 19(1); 64-67.
[28]
Osman I.H., Potts, C.N (1989) Simulated annealing for permutation Flow-shop scheduling. Omega 17(6); 551-557.
[29]
Palmer D.S (1965) 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); 101-107.
[30]
Pinedo M. (1995) scheduling: theory, algorithms, and systems. Prentice Hall, Englewood Cliffs, NJ.
[31]
Reeves C (1995) A genetic algorithm for flow shop sequencing. Computers and Operations Research 22(1),5-13.
[32]
Sadinezhad S., Ghaleh Assadi, R (2008) Preference ratio-based maximum operator approximation and its application in fuzzy flowshop scheduling. Applied Soft Computing 8 (1); 759-766.
[33]
Smith M.L., Dudek, R.A (1967) A general algorithm for solution of the n-job, m-machine sequencing problem of the flowshop. Operations Research 15; 71-82.
[34]
Stanfield P.M., King, R.E., Joines, J.A (1996) Scheduling arrivals to a production system in a fuzzy environment. European Journal of Operational Research 93(1); 75-87.
[35]
Stutzle T., Dorigo, M (2003) The ant colony optimization metaheuristic: Algorithms, applications, and advances. In F. Glover and G. kochenberger (EDS).Handbook of metaheuristics (pp.251-285). Norwel l, MA: kluwer Academic publishers.
[36]
Stutzle, T., Hoos, H., 1996. Improvements on the Ant-system: Introducing max–min ant system. Computer and Information Science 1-23.
[37]
Stutzle T., Hoos, H (1997) The max–min ant system and local Search for the traveling salesman problem. In T. back, Z. michalewicz, and X. Yao (Eds). Proceedings of the 1997 IEEE international conference on evolutionary computation (ICEC'97) (pp.309-314). Piscataway: IEEE press.
[38]
Taillard E (1993) Benchmarks for basic scheduling problems. European Journal of Operational Research 64(2); 278-285.
[39]
Tsujimura, Y., Park, S.H., Chang, I.S., Gen, M., 2003. An effective method for solving flowshop scheduling problems with fuzzy processing times. Computers and Industrial Engineering 25(1-4), 239-242.
[40]
Van Laarhoven P.J.M., Aarts, E.H.L (1987) Simulated annealing: theory and applications. Dordrecht: D. Reidelpubl. Co.
[41]
Widmer, M., Hertz, A., 1989. A new heuristic method for the flow-shop sequencing problem. European Journal of Operational Research 42(2); 186-193.
[42]
Yagmahan B., Yenisey, M.M (2008) Ant colony optimization for multi-objective flow shop scheduling problem. Computers and Industrial Engineering 54; 411-420.
[43]
Ying K.C., Liao, C.J (2004) An ant colony system for permutation flow-shop sequencing. Computers and Operations Research 31(5); 791-801.
