The scheduling problem for flexible manufacturing systems (FMSs) has been attempted in this paper using the ant colony optimization (ACO) technique. Since the operation of a job in FMSs can be performed on more than one machine, the scheduling of the FMS is considered as a computationally hard problem. Ant algorithms are based on the foraging behaviour of real ants. The article deals with the ant algorithm with certain modifications that make it suitable for application to the required problem. The proposed solution procedure applies a graph-based representation technique with nodes and arcs representing operation and transfer from one stage of processing to the other. Individual ants move from the initial node to the final node through all nodes desired to be visited. The solution of the algorithm is a collective outcome of the solution found by all the ants. The pheromone trail is updated after all the ants have found out their respective solutions. Various features like stagnation avoidance and prevention from quick convergence have been incorporated in the proposed algorithm so that the near-optimal solution is obtained for the FMS scheduling problem, which is considered as a non-polynomial (NP)-hard problem. The algorithm stabilizes to the solution in considerably lesser computational effort. Extensive computational experiments have been carried out to study the influence of various parameters on the system performance.
LiD. C.SheI. S.Using unsupervised learning technologies to induce scheduling knowledge for FMSs. Int. J. Prod. Res., 1994, 32(9), 2187–2199.
2.
ShinichN.TaketoshiY.Dynamic scheduling system utilizing machine learning as a knowledge acquisition tool. Int. J. Prod. Res., 1992, 30, 411–413.
3.
HaddockJ.O'KeefeR. M.Using artificial intelligence to facilitate manufacturing systems simulation. Computers and Ind. Engng, 1990, 18(3), 275–283.
4.
SteckeK. E.Design, scheduling and control problems of flexible manufacturing systems. Ann. Op. Res., 1995, 3, 3–12.
5.
AndreattaG.DesertiI.GiraldoL. N.Scheduling algorithm for a two machine flexible manufacturing system. Int. J. Flexible Mfg Systems, 1995, 7, 207–227.
6.
SaruncuogluL.KarabukS.A beam search-based algorithm and evaluation of scheduling approaches for flexible manufacturing systems. IIE Trans., 1999, 30, 179–191.
7.
JeongK. C.KimY. D.A real time scheduling mechanism for a flexible manufacturing system: Using simulation and dispatch rules. Int. J. Prod. Res., 1998, 36(9), 2609–2626.
8.
YihY.ThesenA.Semi-Markov decision models for real-time scheduling. Int. J. Prod. Res., 1991, 29, 2331–2346.
9.
ThesenA.LeiL.An expert scheduling system for material handling hoists. J. Mfg Systems, 1990, 9, 247–252.
10.
ShawM. J.A pattern-directed approach to flexible manufacturing: A framework for intelligent scheduling, learning, and control. Int. J. Flexible Mfg Systems, 1989, 2, 121–144.
11.
LiangT. P.MoskowitzH.YihY.Intelligent neural networks and semi-Markov process for automated knowledge acquisition: A real time scheduling. Decision Sci., 1992, 23, 1297–1341.
12.
ChryssolourisG.LeeM.DomroeseM.The use of neural networks in determining operational policies for manufacturing systems. J. Mfg Systems, 1991, 10, 166–175.
13.
TalvageJ. J.ShodhanR.Automated development of design and control strategy for FMS. Int. J. Computer Integrated Mfg, 1992, 5, 335–348.
14.
BenguG.A simulation-based scheduler for flexible flow lines. Int. J. Prod. Res., 1994, 32, 321–344.
15.
KimM. H.KimY. D.Simulation based real time scheduling mechanism in a flexible manufacturing system. J. Mfg Systems, 1994, 13, 85–93.
16.
DuffieN. A.PrabhuV. V.Real time distributed scheduling of heterarchical manufacturing systems. J. Mfg Systems, 1994, 13, 94–107.
17.
IshiiN.MurakiM.An extended dispatching rule approach in an online scheduling framework for the batch process management. Int. J. Prod. Res., 1996, 34, 329–348.
18.
MarieP. J.A class of Petri nets for manufacturing system integration. IEEE Trans. Robotics and Automn, 1997, 13, 317–326.
19.
NaiqiW.Necessary and sufficient conditions for deadlock free operation in flexible manufacturing systems using a colored Petri net model. IEEE Trans. Systems, Man and Cybernetics—Part C: Applications and Reviews, 1999, 29(2), 192–204.
20.
KimY. W.InabaA.SuzukiT.OkumaS.FMS scheduling based on timed Petri net model and RTA algorithm. In Proceedings of the 2001 IEEE International Conference on Robotics and Automation, Seoul, Korea, 21–26 May 2001, pp. 848–853.
21.
DorigoM.ManiezzoV.ColorniA.Positive feedback as a search strategy. Technical Report 91-016, Dipartimento di Elettronica, Politechnico di Milano, Italy, 1991.
22.
DorigoM.ManiezzoV.ColorniA.The ant systems: Optimization by a colony of cooperative agents. IEEE Trans. Man, Machine and Cybernetics—Part B, 1996, 26(1), 29–41.
23.
GambardellaL. M.DorigoM.Ant-Q: A reinforcement learning approach to the travelling salesman problem. In Proceedings of the Twelfth International Conference on Machine Learning, ML-95, 1995, pp. 252–260.
24.
DorigoM.GambardellaL. M.Ant colonies for the travelling salesman problem. Bio Systems, 1997, 43, 73–81.
25.
DorigoM.GambardellaL. M.Ant colony systems: A co-operative learning approach to the travelling salesman problem. IEEE Trans. Evolutionary Computation, 1997, 1(1), 53–66.
26.
GambardellaL. M.DorigoM.Solving symmetric and asymmetric TSPs by ant colonies. In Proceedings of the IEEE Conference on The Evolutionary Computation, ICE96, 1996, pp. 622–627.
27.
StutzleT.HoosH.The MAX-MIN ant systems and local search for the travelling salesman problem. In Proceedings of IEEE-ICEC-EPS, IEEE International Conference on Evolutionary Computation and Evolutionary Programming, 1997, pp. 309–314.
28.
StutzleT.HoosH.Improvements on the ant system: Introducing MAX-MIN ant system. In Proceedings of the International Conference on Artificial Neural Networks and Genetic Algorithms, 1997, pp. 245–249.
29.
BullnheimerB.HartlR. F.StraussC.A new rank-based version of the ant system: A computational study. Technical Report POM-03/97, Institute of Management Science, University of Vienna. In Central European Journal for Operation Research and Economics, 1997.
30.
GambardellaL. M.TaillardE. D.DorigoM.Ant colonies for the QAP. J. Opl Res. Soc., 50, 167–176.
31.
StutzleT.HoosH.MAX-MIN ant systems and local search for the combinatorial optimization problems. In Advances and Trends in the Local Search Paradigms for the Optimization (Eds OsamaI. H.MartelloS.RoucariolC.), 1998, 137–154.
32.
ManiezzoV.ColorniA.The ant systems applied to the quadratic assignment problem. IEEE Trans. Knowledge and Data Engng, 1999, 11(50), 769–778.
33.
ManiezzoV.ColorniA.DorigoM.The ant systems applied to the quadratic assignment problem. Technical Report IRIDIA, University Libre de Bruxelles, Belgium, 1994, pp. 28–94.
34.
ColorniA.DorigoM.ManiezzoV.TrubianM.Ant system for job-shop scheduling. Belgian J. Op. Res., Statistics and Computer Sci., 1994, 34, 39–53.
35.
BullnheimerB.HartlR. F.StraussC.Applying the ant systems to the vehicle routing problem. In Advances and Trends in the Local Search Paradigms for Optimization (Eds OsamaI. H.MartelloS.RoucariolC.), 1998, pp. 109–120.
36.
LeeD. Y.DicesareF.FMS scheduling using Petri nets and heuristic search. IEEE Trans. Robotics and Automn, 1994, 10(2), 123–132.
37.
YimS. J.LeeD. Y.Scheduling method with the consideration of machine setup in flexible manufacturing systems. In Proceedings of IEEE International Conference on Robotics and Automation, Albuquerque, New Mexico, April 1997, pp. 2735–2740.
