بررسی فعل و انفعالات پارامتری سیستم مورچه با استفاده از طراحی آزمایش برای مشکلات زمان بندی تولید کارگاهی

In recent years, one of the most important and promising research fields has been metaheuristics to find optimal or near-optimal solutions for NP-hard combinatorial optimization problems. Improving the quality of the solution or the solution time is basic research area on metaheuristics. Modifications of the existing ones or creation of hybrid approaches are the focus of these efforts. Another area of improving the solution quality of metaheuristics is finding the optimal combination of algorithm control parameters. This is usually done by design of experiments or one-at-a-time approach in genetic algorithms, simulated annealing and similar metaheuristics. We observe that, in studies which use Ant Colonies Optimization (ACO) as an optimization technique; the levels of control parameters are determined by some non-systematic initial experiments and the interactions of the parameters are not studied yet. In this study, the parameters of Ant System have been investigated on different sized and randomly generated job-shop scheduling problems by using design of experiments. The effects and interactions of the parameters have been interpreted with the outputs of the experiments. Referring to the statistical analysis it is observed that none of the interactions between the Ant System parameters has a significant effect on makespan value. A specific fractional experimental design is suggested instead of the full factorial design. Depending on the findings from the benchmark problems it will be a reliable approach to use the suggested design for saving time and effort in experiments without sacrificing the solution quality.

It is well known that many combinatorial optimization problems, especially the complex real life problems arising in computer science, engineering mathematics, management and many other fields cannot be solved exactly within reasonable time limits. In recent years, one of the most important and promising research fields has been generic heuristic methods, which is also called general local search methods or metaheuristics. These algorithms borrow some metaphors from physics, biology or social sciences to find optimal or near-optimal solutions for NP-hard combinatorial optimization problems. We can reckon genetic algorithms, neural networks and artificial immune systems from biology; particle swarm optimization and simulated annealing from physics; taboo search from social sciences, and ant algorithms from ethology among the most successful techniques. Their self-adaptation capability to use feedback information for modifying the internal models and their parameters, and the ability to operate with multiple agents may help to find high quality solutions for hard problems in reasonable time. Of course the rapid development of computer systems and the simplicity of both design and computational requirements of the metaheuristics comparing with the mathematical optimization techniques have crucial role on the very fast, exploding growth of this research field. Ant Colonies Optimization is a class of constructive multi-agent metaheuristic algorithms that are analogous with the behavior of real ants that can be used for the solution of combinatorial optimization problems. Ant System (AS) is the original and most simplistic ACO algorithm. As such, it has been extremely influential in the development of more advanced ACO algorithms. AS are inspired by the foraging behavior of ant-colonies. This system tries to capture the basic mechanisms that allow ants to find the shortest path from their colony to a food source. This mechanism works with a substance called pheromone (Colorni, Dorigo, Maniezzo, & Trubian, 1994). AS is a general-purpose heuristic algorithm, which can be used to solve various combinatorial optimization problems including but not limited to the traveling salesman problem, quadratic assignment problem, vehicle routing, data analysis, scheduling, sequencing, frequency assignment, graph partitioning and reliability optimization. Following the AS algorithm, several extensions and improvements of the original AS algorithm were introduced over the years such as Elitist AS (EAS), Rank-Based AS, Max–Min AS, Ant Colony System (ACS) and Hyper-Cube Framework (HCF). The details of the successful ACO variants can be seen in Blum’s (2005a) study. A brief survey of the ACO variants used in the literature and the fields in which they are applied is provided in the Appendix A. In this study job-shop scheduling problems with the objective of minimization of makespan (Cmax) are selected as the application area. Job-shop scheduling is one of the best known problems in the area of scheduling. A job-shop scheduling problem considers n jobs processed on m machines. Each job consists of a set of operations Oij (i = 1, 2, … , n; j = 1, 2, … , m). Various approaches for solving this problem have been proposed in the literature including heuristics and metaheuristics.

As the number of factors (k) in a 2k factorial design increases, the number of runs required for a complete replicate of the design rapidly outgrows the completion time of experiments of most experimenters. For example, a complete replicate of the 25 design requires 32 runs as in our case. In this design only 5 of the 31 degrees of freedom correspond to main effects, and the remaining 26 degrees of freedom are associated with two-factor and higher interactions. If the experimenter can reasonably assume that some certain interactions are negligible, information on the main effects and the existing interactions may be obtained by running only a fraction of the complete factorial experiment. The main effects and many of the interactions are significant as expected on the makespan in the first group of experiments in which the parameter levels are chosen at extreme points. For the main effects in the second group of experiments using the random parameter sets, similar results are obtained; it is also observed that interactions are less significant than the single effects of factors. Especially, multiple interactions between three, four and five factors are negligible. The similarity between the results of the experiments for all groups using the random parameter sets implies that the operation times (generated randomly in the range of 1–99 min) have no significant influence on the factor and interaction effects on Cmax. Another finding which can be derived from the same experiments is that the problem size of the job-shop scheduling problem is not influential on the factor and interaction effects on Cmax. Referring to Table 9, both the sum of normalized F values and the total number of the rejected null hypotheses B(β) is the most influential factor on response variable. Factor C(ρ) follows it with a great degree of importance. Factor E(t), D(m) and A(α), follow these factors, respectively. In addition, AC and BC interactions can also be evaluated as notable, with respect to their sum of normalized F values although the numbers of rejected null hypotheses of these interactions are not as high as the main effects’.