基于文化基因算法的开放车间调度问题研究

An Open Shop Scheduling Problem Based on Memetic Algorithm

针对开放车间调度问题,运用了文化基因算法进行优化求解。在文化基因算法的框架中,既有种群中的全局搜索,又包含针对问题自身特点的局部搜索,为解决开放车间调度问题提供了一种新的算法。按照文化基因算法的思想和特点,将爬山法作为局部搜索策略加入到全局搜索策略所用到的遗传算法中,通过对开放车间调度问题的邻域结构进行研究,加入爬山搜索法进行优化求解。基于40个标准算例,通过与下界值的比较,验证了所提算法在解决具有较大搜索空间的调度问题时,其拥有更出色的算法性能。

Aiming at the Open Shop Scheduling Problem (OSSP),a Memetic Algorithm (MA) is proposed to solve the problem.In the framework of the cultural Genetic Algorithm (GA),both global search and local search for the problem's own characteristics are provided.It provides a new algorithm for solving the open job shop scheduling problem.According to the thought and cultural characteristics of genetic algorithm,the method of climbing as a local search strategy into the genetic algorithm global search strategy is used,and a research of neighborhood structure is conducted on open shop scheduling problem,adding hill-climbing search method to solve the optimal.Based on the comparison of 40 standard examples,it is proved that the proposed algorithm has better performance in solving the scheduling problem with larger search space by comparing with lower bound values.