基于混合多智能体遗传算法的作业车间调度问题研究

针对作业车间调度问题(JSP)的非确定性多项式特性与解空间分布的大山谷属性,本文提出一种多智能体遗传算法(MAGA)与自适应模拟退火算法(ASA)的混合优化算法,用于寻找最大完工时间最短的调度。首先,将每个染色体视作独立的智能体并采用工序编码方式随机初始化每个智能体,结合多智能体协作与竞争理论设计了实现智能体之间交互作用的邻居交互算子,进而利用一定数量智能体进行全局搜索,找到多个适应度较高的可行解。其次,为避免算法陷入局部最优,采用ASA对每个智能体开展局部寻优。最后,通过基准测试库中典型实例的计算结果验证了该算法的有效性。

Hybrid multiagent genetic algorithm for job shop scheduling problem

For the NP-hard characteristic of job shop scheduling problem (JSP) and big valley property of its solution space, this paper proposes a hybrid algorithm based multiagent genetic algorithm (MAGA) and adaptive simulated annealing algorithm (ASA) to obtain the minimal makespan schedule. First, each chromosome is regarded as independent agent which is randomly initialized under condition of operation-based encoding method. Combined with multiagent cooperation and competition theory, a neighborhood interaction operator is designed to realize the interaction between agents, and then a certain number of agents are utilized to do global searching to find several individuals with high fitness. Second, in order to prevent the algorithm from falling into local optimum, ASA is adopted to carry out local optimization for each agent. Finally, the effectiveness of the proposed hybrid algorithm is verified by the computational results of typical problems from benchmark library.