All Title Author
Keywords Abstract


Ant Colony Optimisation for Backward Production Scheduling

DOI: 10.1155/2012/312132

Full-Text   Cite this paper   Add to My Lib

Abstract:

The main objective of a production scheduling system is to assign tasks (orders or jobs) to resources and sequence them as efficiently and economically (optimised) as possible. Achieving this goal is a difficult task in complex environment where capacity is usually limited. In these scenarios, finding an optimal solution—if possible—demands a large amount of computer time. For this reason, in many cases, a good solution that is quickly found is preferred. In such situations, the use of metaheuristics is an appropriate strategy. In these last two decades, some out-of-the-shelf systems have been developed using such techniques. This paper presents and analyses the development of a shop-floor scheduling system that uses ant colony optimisation (ACO) in a backward scheduling problem in a manufacturing scenario with single-stage processing, parallel resources, and flexible routings. This scenario was found in a large food industry where the corresponding author worked as consultant for more than a year. This work demonstrates the applicability of this artificial intelligence technique. In fact, ACO proved to be as efficient as branch-and-bound, however, executing much faster. 1. Production Scheduling Still a Differential for Competitiveness The globalised world economic scenario makes entrepreneurial competitiveness unavoidable and being competitive has become an indispensable prerequisite to organisations that strive for success. Within this context, manufacturing activities become especially important for they decisively influence performance, directly affecting (and being affected by) forecast, planning, and scheduling decisions. Shop-floor production scheduling, which within the hierarchical production planning covers disaggregate and detailed decisions in short time frame, consists in allocating activities (production orders or jobs) to resources, by obeying sequencing and setup restrictions, with focus on getting the best possible results from limited available resources, and, at the same time, aiming at reducing production costs and meeting service levels as fast and efficiently as possible. To make all this happen in cases where production and financial resources are limited and restrictions are many, adequate algorithms techniques and intelligence are necessary. Almost four decades ago, Garey et al. [1] classified production scheduling problems as being NP-hard, which in practical ways means that it is very difficult for one to obtain an optimal solution through exact algorithms and also demand unacceptable execution (computer or effort) time. The

References

[1]  Garey, MR, and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979.
[2]  C. J. Liao and C. C. Liao, “An ant colony optimisation algorithm for scheduling in agile manufacturing,” International Journal of Production Research, vol. 46, no. 7, pp. 1813–1824, 2008.
[3]  S. J. Shyu, B. M. T. Lin, and P. Y. Yin, “Application of ant colony optimization for no-wait flowshop scheduling problem to minimize the total completion time,” Computers and Industrial Engineering, vol. 47, no. 2-3, pp. 181–193, 2004.
[4]  C. Rajendran and H. Ziegler, “Two ant-colony algorithms for minimizing total flowtime in permutation flowshops,” Computers and Industrial Engineering, vol. 48, no. 4, pp. 789–797, 2005.
[5]  A. Bauer, B. Bullnheimer, R. F. Hartl, and C. Strauss, An Ant Colony Optimizations Approach for the Single Machine Total Tardiness Problem, Department of Management Science. Universidade de Vienna, Vienna, Austria, 1999.
[6]  B. M. T. Lin, C. Y. Lu, S. J. Shyu, and C. Y. Tsai, “Development of new features of ant colony optimization for flowshop scheduling,” International Journal of Production Economics, vol. 112, no. 2, pp. 742–755, 2008.
[7]  K. C. Ying and S. W. Lin, “Multiprocessor task scheduling in multistage hybrid flow-shops: an ant colony system approach,” International Journal of Production Research, vol. 44, no. 16, pp. 3161–3177, 2006.
[8]  M. Dorigo, V. Maniezzo, and A. Colorni, “Positive feedback as a search strategy,” Tech. Rep. 91-016, Dipartimento di Elettronica, Politecnico di Milano, Milano, Italy, 1991.
[9]  M. Dorigo, V. Maniezzo, and A. Colorni, “Ant system: optimization by a colony of cooperating agents,” IEEE Transactions on Systems, Man, and Cybernetics B, vol. 26, no. 1, pp. 29–41, 1996.
[10]  M. Ventresca and B. Ombuki, “Ant colony optimization for job-shop scheduling problem,” Tech. Rep., Department of Computer Science, St. Catharines, Canadá, 2004.
[11]  J. Mazzucco Jr., Uma abordagem híbrida do problema da Programa??o da produ??o através dos algoritmos simulated annealing e genético [tese de doutorado (Doutorado Engenharia de Produ??o, UFSC)], Florianópolis, 1999.
[12]  D. C. Montgomery and G. C. Runger, Estatística Aplicada à Engenharia, LTC, Rio de Janeiro, Brazil, 2004.

Full-Text

comments powered by Disqus