求解流水车间批量流集成调度的离散入侵杂草优化算法

A discrete invasive weed optimization algorithm for the integrated lot-streaming flow shop scheduling problem

中文关键词  流水车间  批量流  入侵杂草优化  邻域搜索

英文关键词  flow shop  lot-streaming  invasive weed optimization  neighborhood search

中文摘要

      提出一种离散入侵杂草优化算法, 用来解决最大完工时间目标的流水车间批量流集成调度问题. 该调度问 题包含两个紧密耦合的子问题: 批次分割问题和考虑启动时间的批次调度问题. 设计了两段字符串编码, 用来表示 两个子问题. 与基本入侵杂草优化算法不同, 所提算法基于适应度和年龄确定杂草种子数量, 基于正切函数和连续 邻域操作产生种子. 8种邻域算子的混合应用与局部搜索增强了算法的求解能力. 仿真实验表明了所提算法的有效 性.

英文摘要

      An effective discrete invasive weed optimization (DIWO) algorithm is presented to minimize the maximum completion time for an integrated lot-streaming flow shop scheduling problem, which can be modeled as two closely coupled sub-problems. One sub-problem is a lot-splitting problem, and the other is a batch scheduling problem with separable setup times. A two-stage string encoding is designed to represent the two sub-problems. Unlike the basic invasive weed optimization algorithm, the presented DIWO determines the number of seeds for each individual not only based on its fitness but also based on its age. In addition, the DIWO generates a seed based on the tangent function and the continuous neighborhood operation. Eight neighborhood operators and a local search procedure are developed. The mixed application of the eight neighborhood operators and the local search procedure significantly enhance the performance of the DIWO. The computational results based on extensive experiment demonstrate the effectiveness of the presented DIWO algorithm.