الگوریتم کلونی زنبور عسل مصنوعی بر اساس مشکل خواص داده ها برای برنامه ریزی فروشگاه های شغلی

To solve the job shop scheduling problem with the objective of minimizing total weighted tardiness, an artificial bee colony algorithm based on problem data analysis is proposed. First, characteristic values are defined to describe the criticality of each job in the process of scheduling and optimization. Then, a fuzzy inference system is employed to evaluate the characteristic values according to practical scheduling knowledge. Finally, a local search mechanism is designed based on the idea that critical jobs should be processed with higher priority. Numerical computations are conducted with an artificial bee colony algorithm which integrates the local search module. The computational results for problems of different sizes show that the proposed algorithm is both effective and efficient.

The job shop scheduling problem (JSSP) has been known as a notoriously hard combinatorial optimization problem since the 1950s. In terms of computational complexity, JSSP is NP-hard in the strong sense. Therefore, even for very small JSSP instances, it is by no means easy to guarantee the optimal solution. In recent years, the metaheuristics — such as genetic algorithm (GA) [1], tabu search (TS) [2], particle swarm optimization (PSO) [3], and ant colony optimization (ACO) [4] — have clearly become the research focus in practical optimization methods for solving JSSPs. However, when the problem size grows, meta-heuristic algorithms usually take excessive time to converge. To enhance the efficiency of these algorithms, two types of approaches may be roughly identified in the literature: (1) Focusing on the optimization algorithm: the conventional operations (or parameters) in the standard version of these algorithms have been modified or redesigned to promote their performance in the neighborhood search. (2) Focusing on the features of the pending problem: problem-specific or instance-specific information is extracted and utilized in the searching process to accelerate the convergence speed of these algorithms. The former approach is independent of problem classes. But according to the no free lunch theorem [5], such improvements on the optimization algorithm alone cannot guarantee good performance for all problems. In terms of the latter approach, embedded local search can utilize the characteristic information to improve the solutions inthe optimization process. However, how to effectively extract and describe the characteristic information remains a challenging but rewarding research topic. In this paper, we devise a fuzzy inference system based on intuitive knowledge to evaluate the criticality value of each job. Then, this information is used in a local search mechanism to promote the optimization efficiency of the artificial bee colony (ABC) algorithm. The paper is organized as follows. The discussed job shop scheduling problem is formulated in Section 2. Sections 3 and 4 presents the detailed algorithms. The computational results and a briefanalysis are provided in Section 5. Finally, the conclusions are given in Section 6.

In this paper, an artificial bee colony algorithm based on criticality information for solving job shop scheduling problems is proposed. The defined criticality values reflect the properties of both the objective function and the most crucial jobs at different stages of the optimization process. The criticality information is extracted and used as a local search optimizer to increase the convergence speed of the optimization process. Computational results show that the proposed algorithm is effective