混合离散蛙跳算法求解柔性装配系统调度问题

Hybrid discrete shuffled frog leaping algorithm for the scheduling problem of flexible assembly systems

中文关键词  柔性装配系统  死锁  Petri网  调度  混合离散蛙跳算法

英文关键词  flexible assembly systems  deadlock  Petri nets  scheduling  hybrid discrete shuffled frog leaping algorithm

中文摘要

      本文主要研究不含中间缓冲区的柔性装配系统(FAS)的优化调度问题,其中当工件竞争使用有限的生产资 源时,不合理的资源分配会导致系统死锁(deadlock).针对易死锁(deadlock-prone)FAS的优化调度问题,本文采用 Petri网建模, 提出了一种混合离散蛙跳算法(HDSFLA)以最小化最大完工时间(makespan). 首先,提出了一种新的编 码解码方法,其中一个个体编码为一个包含全部工件加工信息的变迁序列,可解码为一个工件–工序序列;其次,为 了保证种群中个体的可行性,提出了一个个体修正算法和基于最早引发时间的改进个体修正算法,从而将不可行个 体修复为可行个体;然后,结合编码特征设计了用于生成新个体的交叉操作;最后,为了平衡算法的全局搜索和局 部开发能力,设计了一个基于交换和插入算子的局部搜索策略.通过不同规模算例上的仿真实验和算法对比分析, 验证了HDSFLA的有效性.

英文摘要

      This paper addresses the scheduling problem in flexible assembly systems (FAS) without intermediate buffer s. In such systems, deadlock may occur when multiple jobs compete for limited shared resources under inappropriate allocation. To solve the scheduling problem of deadlock-prone FAS, Petri nets are used to model it, and a hybrid discrete shuffled frog leaping algorithm (HDSFLA) is proposed to minimize the maximum completion time, i.e., makespan. Firstly, a novel encoding and decoding method is proposed, in which an individual is encoded as a complete transition sequence and can be decoded into a sequence of jobs and operations. Then, in order to guarantee the feasibility of each individual, an individual modification method and an improved individual modification method based on the-earliest-firing-time are de veloped, through which an unfeasible solution can be repaired into a feasible one. Furthermore, based on the characteristics of the encoding method, a crossover operation is designed to generate new individuals for the next generation. In addition, to balance the global exploration and local exploitation capabilities of the proposed algorithm, a local search method based on swap and insert operators is developed and imbedded into the algorithm. Experimental tests on different instances and comparisons with other algorithms are conducted to demonstrate the effectiveness of HDSFLA.