دانلود رایگان مقاله انگلیسی یک الگوریتم کلونی مورچه هیبریدی جدید برای برنامه ریزی فلوشاپ بدون انتظار - اشپرینگر 2018

Abstract

In this paper, the no-wait flow shop scheduling problem under makespan and flowtime criteria is addressed. The no-wait flowshop is a variant of the wellknown flowshop scheduling problem where all processes follow the previous one without any interruption for operations of a job. Owing to the problem is known to be NP-hard for more than two machines, a hybrid meta-heuristic algorithm based on ant colony optimization (ACO) and simulated annealing (SA) algorithm is improved. First, at each step, due to the characteristic of ACO algorithm that include solution construction and pheromone trail updating, some different areas of search space are checked and best solution is selected. Then, to enhance the quality and diversity of the solution and finding best neighbor of this solution, a novel SA is presented. Moreover, a new principle is applied for global pheromone update based on the probability function like SA algorithm. The proposed approach solution is compared with several the state-of-the-art algorithms in the literature. The reported results show that the proposed algorithms are effective and the new approach for local search in ACO algorithm is efficient for solving the no-wait flow shop problem. Then, we employed another hybrid ACO algorithm based on hybridization of ACO with variable neighborhood search (VNS) and compare the results given by two proposed algorithms. These results show that our new hybrid provides better results than ACO-VNS algorithm.

6 Conclusion and future work

In the current research, a no-wait flow-shop scheduling problem (NWFSP) for minimizing the makespan was discussed. This problem is known to be strongly NPhard. In this paper, ant colony algorithm with the simulated annealing as a local search method are proposed to solve this problem. Unlike most of other reported population-based algorithms in the literature, the proposed ACO–SA algorithm is simple and easy to implement and replicate. The evaluation of the proposed methods was carried out against the 8 best performing methods from the literature.

Statistical analyses and extensive experimental demonstrate the efficiency of the proposed ACO–SA algorithm owing to an average PRD of -4.85. In order to prove the efficiency of our algorithms, we use another method based on VNS for local search phase. The computational results are indicated that hybridization ACO with SA is viable and reliable method and really competitive and provides promising computational results. As the future work, other neighborhood’s structures can be applied in SA algorithm. In addition, the proposed algorithm can be used to solve the NWFSP with set-up times, maintenance of machines and transportation times. Furthermore, combining ACO with other local search-based algorithms such as Iterated local search or tabu search algorithm is possible research method.