Research on optimization of the job shop scheduling problem (JSP) is one of the most significant and promising areas of optimization. Instead of the traditional optimization method, this paper presents an investigation into the use of an Ant Colony System (ACS) to optimize the JSP. The main characteristics of this system are positive feedback, distributed computation, robustness and the use of a constructive greedy heuristic. In this paper, an improvement of the performance of ACS will be discussed. The numerical experiments of ACS were implemented in a small JSP. The optimized results of the ACS are favourably compared with the traditional optimization methods.
Bames, J. W. and Chambers, J. B.1995: Solving the job-shop scheduling problem using tabu search. IIE Transactions27, 257-263.
2.
Beckers, R., Deneubourg, J. L. and Goss, S.1992: Trails and U-turns in the selection of the shortest path by the ant Lasius niger. Journal of Theoretical Biology397-415.
3.
Candido, M. A. B., Khator, S. K. and Barcia, R. M.1998: A genetic algorithm based procedure for more realistic job shop scheduling problem. International Journal of Production Research36, 3437-3457.
4.
Colorni, A., Dorigo, M. and Maniezzo, V. 1991: Distributed optimization by ant colonies. In Proceedings of ECAL91 - European Conference on Artificial Life. Elsevier, 134-142.
5.
Colorni, A., Dorigo, M., Maniezzo, V. and Trubian, M.1993: Ant system for Job-Shop scheduling. Belgian Journal of Operations Research, Statistics and Computer Science34, 39-54.
6.
Dell Amico, M. and Trubian, M.1993: Applying tabu search to the job shop scheduling problem. Annals of Operations Research41, 231-252.
7.
Della Croce, F., Tadei, R. and Volta, G.1995: A genetic algorithm for the job shop problem. Computers & Operations Research22, 15-24.
8.
Dorigo, M. 1992: Optimization, learning, and natural algorithms. PhD thesis, Politecnico di Milano.
9.
Dorigo, M. and Gambardella, L. M.1997: Ant Colony System: a cooperative learning approach to the Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation1, 53-66.
10.
Dorigo, M., Maniezzo, V. and Colorni, A.1996: Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics - Part B: Cybernetics26, 29-41.
11.
Garey, M. R., Johnson, D. S. and Sethi, R.1976: The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research1, 117-129.
12.
Hölldobler, B. and Wilson, E. O.1990: The ants. Springer-Verlag.
13.
Huang, D. S. and Ma, S. D.1999: Linear and nonlinear feedforward neural network classifiers: a comprehensive understanding. Journal of Intelligent Systems9, 1-38.
14.
Huang, D. S. and Wen-Bo Zhao, 2005: Determining the centers of radial basis probabilities neural networks by recursive orthogonal least square algorithms. Applied Mathematics and Computation162, 461-473.
15.
Huang, D. S., Ip, H. S., Law, K. C. K. and Zheru Chi. 2005: Zeroing polynomials using modified constrained neural network approach. IEEE Transanction on Neural Networks16, 721-732.
16.
Jain, A. and Meeran, S.1999: Deterministic job-shop scheduling: past, present and future. European Journal of Operational Research113, 390-434.
17.
Kim, G. H. and Lee, C. S. G. 1994: An evolutionary approach to the job-shop scheduling problem. Robotics and Automation. Proceedings 1994 IEEE International Conference, 8-13 May 1994, Volume 1, 501-506.
18.
Mati, Y., Rezg, N. and Xiaolan Xie. 2001: An integrated greedy heuristic for a flexible job shop scheduling problem. Systems, Man, and Cybernetics, 2001 IEEE International Conference7-10 October 2001, Volume 4, 2534-2539.
19.
Matsuo, H., Suth, C. J. and Sullivan, R. S.1988: A controlled search simulated annealing method for the general Job-Shop scheduling problem. Graduate School of Business, University of Texas.
20.
Rosenkrantz, D. J., Stearns, R. E. and Lewis, P. M.1977: An analysis of several heuristics for the traveling salesman problem. SIAM Journal of Computing6, 563-581.
21.
van Laarhoven, P. J. M., Aarts, E. H. L. and Lenstra, J. K.1992: Job shop scheduling by simulated annealing. Operations Research40, 113-125.
22.
Wan, G. and Wan, F. 2003: Job shop scheduling by taboo search with fuzzy reasoning. Systems, Man and Cybernetics, 2003. IEEE International Conference5-8 October 2003, Volume 2, 1566-1570.
23.
Wang Ling. 2003: Shop scheduling with genetic algorithm. TsingHua University Press, 59-67.
24.
Zhou Pin, Li Xiao-ping and Zhang Hong-fang. 2004: An ant colony algorithm for Job Shop scheduling problem. Proceedings of the 5th World Congress on Intelligent Control and Automation,15-19 June.
