بررسی ادبیات در مورد بهینه سازی کلونی مورچه برای مشکلات برنامه ریزی: راهنمایی برای پیاده سازی و جهت تحقیقات آینده

Ant Colony Optimization is a swarm intelligence approach that has proved to be useful in solving several classes of discrete and continuous optimization problems. One set, called scheduling problems, is extremely important both to academics and to practitioners. This paper describes how the current literature uses the ACO approach to solve scheduling problems. An analysis of the literature allows one to conclude that ACO is a hugely viable approach to solve scheduling problems. On the basis of the literature review, we were not only able to derive certain guidelines for the implementation of ACO algorithms but also to determine possible directions for future research.

Ant Colony Optimization (ACO) is a meta-heuristic approach proposed by Colorni et al. (1991) and improved in later research (e.g., see Dorigo et al., 1996 for the Ant Colony System and Stützle and Hoos, 2000 for the Max–Min Ant System). The behavior common to all approaches involving ant-based algorithms lies in the mimicry of the behavior used by “real” ants to find the optimal path between their nest and a food source. The earlier application of ACO was to solve the well-known NP-Hard Traveling Salesman Problem (Colorni et al., 1991, Dorigo et al., 1996 and Dorigo and Gambardella, 1997). In this problem, there is a graph in which each node corresponds to a city, and the arcs correspond to the distances between cities. The problem consists of obtaining a minimal tour (sequence of cities) length that contains all the nodes. Several studies have applied ACO to solve different discrete and continuous optimization problems, such as vehicle routing, quadratic assignment problems and graph coloring. Dorigo and Stützle (2004) reported more than 30 problems where ACO-based algorithms have been used successfully. One of these applications involves scheduling problems. With the significance of these problems recognized because of their impact on real environments and their academic relevance (e.g., Pinedo, 2009), “scheduling problems” are a huge set of problems, and are mostly NP-Hard, that try to deal with a simple question: given a set of jobs, a set of resources, a set of constraints, and an objective function, how should the jobs be allocated to the resources? Answering this question, however, usually requires complex and/or time-costly procedures. The great advantage in using a meta-heuristic such as ACO to obtain near-optimal solutions is that the time required to solve the problem is usually acceptable even though the 100% optimal solution may not be achieved. This paper aims at reviewing and classifying published studies that use ACO to solve scheduling problems, and it focuses on the four classical manufacturing environments (single machine, parallel machine, flowshop and jobshop). Different scheduling problems, such as service scheduling (e.g., see Gutjahr and Rauner, 2007 for an ACO approach to the nurse-scheduling problem) are not included in the revision. In addition, this paper concentrates only on uses of the ACO meta-heuristic on its own: any “hybrid approach” is disregarded. This paper contribution is twofold. In the first instance, it aims to help researchers apply this technique in production scheduling, demonstrating how research is being carried out in the literature. Therefore, some guidelines relating to the characteristics of the ACO algorithm applied to scheduling problems are derived. In the second instance, certain directions for future research in the field are highlighted. To present the results, this paper is divided into six sections: Section 2 deals with the basics of scheduling problems; Section 3 is concerned with the ACO; Section 4 has to do with the classification method proposed and the papers reviewed; Section 5 presents an overview of the ACO application to scheduling problems; Section 6 shows a quantitative analysis of the literature; and Section 7 presents the final remarks.

This paper presents a literature review concerning the use of the ACO metaheuristic in scheduling problems. The scope of this survey covers four manufacturing environments: single machine, parallel machine, flowshop, and job shop. Through the analysis, it was possible to verify that ant-based algorithms (ACO, ACS, and MMAS) are valid strategies for solving scheduling problems. Although the ACO algorithm is straightforward, the possibility to easily incorporate scheduling-specific heuristics and other metaheuristics increases the complexity and the research opportunities involving the use of this metaheuristic for this category of problems. The analysis presented in this paper indicates that this field of research is a relatively new one, and only the initial results have been published. One can easily note that the first studies had to do with single-machine scheduling problems. Only later were flowshop, parallel-machine, and job shop environments addressed. The evolution of knowledge in this research area can also be observed in terms of the new features added to address certain problems (e.g., dominance criteria involving single-machine and flowshop scheduling problems). From the quantitative analysis performed, we can derive certain guidelines for the application of ACO algorithms to scheduling problems. The first concerns the job-position scheme. Our research shows that the job-to-job position scheme is used more often than the job-to-position. This may indicate that the job-to-job scheme is usually a straightforward strategy to begin new applications of ACO to scheduling problems. As regards the job-to-position scheme, an interesting strategy is a hybrid approach, which uses both job-to-job and job-to-position, indicating that, when necessary, it is possible to combine both strategies. Another conclusion to be drawn from this paper is that the definition of visibility as a function of the partial solution being built by a single ant is a promising strategy for scheduling applications, since it was used in almost 20 papers in our review. In addition, our literature review highlights the benefits of incorporating scheduling-specific information into ACO implementations. This can be observed from: (i) The adoption of dominance criteria in some papers; (ii) The use of problem-specific pheromone initialization methods, aimed at speeding up the algorithm. Potential topics for future research also emerged. We observed that a single-criterion objective function was used in the four manufacturing environments studied in this paper. This was not the case for multi-criteria objective functions. Therefore, one can conclude that using ACO for scheduling problems aimed at optimizing multi-criteria objective functions is a relatively new research field (no paper with this characteristic was found for single and parallel environments, and only one paper with regard to job shop), and can be addressed. In addition, our review indicates that the general evolution of ACO applications relating to scheduling problems basically followed an expected path: single machine, parallel machine, flowshop, and job shop. Other promising areas for future research involve: •Setup-dependent times. Although some of the approached problems address setup-dependent times, we note that there is no application of ACO to solve job shop problems with this constraint. A similar remark can be made regarding the possibility of generating production batches, which is still not considered in job shop problems. • Makespan. Still observing the job shop problems addressed, it is possible to note that makespan is the most frequent criterion, showing that a research opportunity exists to use other objective functions in job shop scheduling. The other three studied environments present a wider range of objective functions. •Time-window constraint. Of all the papers examined, only one deals with scheduling with a time-window constraint (Huang and Yang, 2008). This constraint is common in real scheduling problems, and can therefore represent an opportunity for research regarding application of the ACO metaheuristic.