Ant colony optimization with a new exploratory heuristic information approach for open shop scheduling problem

摘要

This work proposes a new metaheuristic algorithm (ACONEH) for open shop scheduling problem (OSSP) with makespan minimization. The aim is to improve the exploration capability of ant colony optimization (ACO) and also solve OSSP more effectively. This is achieved by introducing a new heuristic information approach that utilizes three exploratory characteristics. The first is randomness: the heuristic information should be generated randomly. The second is diversity: each ant acquires different information. The third is improvability: each ant improves its information periodically. ACONEH is tested on three well-known benchmark problem sets that include 175 instances. The proposed heuristic approach is compared with a traditional one. The results show that the proposed approach produces considerable improvements. These improvements are 91% in the average relative deviation of the best solution and 63% in the average relative deviation of the average solution. ACONEH is compared with other six recent and best-so-far metaheuristic algorithms. The results show that it produces better solutions than all of them in a reasonable computational time. Moreover, the improvements in the average relative deviation of the best solution achieved on the best-so-far ACO and the best-so-far metaheuristic algorithm are 75% and 46%, respectively. Therefore, ACONEH can be considered as the best-so-far metaheuristic algorithm for OSSP.