Abstract: For the Distributed Two-Stage Hybrid Flow Shop Scheduling Problem (DTHFSP) with Sequence-Dependent Setup Times (SDST),a Double Variable Neighborhood Search (DVNS) algorithm was proposed to minimize the total tardiness and makespan simultaneously.The factory assignment and the machine assignment of the first stage were combined together to reduce the number of subproblems.DVNS consisted of two cooperative variable neighborhood structures and each of which had global search operator.Some useful strategies included the cooperation between neighborhood search and global search,the reasonable configuration of neighborhood structures and the periodic update of current solution were applied.Extensive experiments were conducted to test the performance of DVNS and the computational results showed that DVNS had promising advantages on DTHFSP.

Key words: double variable neighborhood search, distributed scheduling, two-stage hybrid flow shop scheduling, setup time

摘要： 针对准备时间依赖于顺序的分布式两阶段混合流水车间调度问题(DTHFSP),提出一种双变邻域搜索(DVNS)算法以同时最小化总延迟时间和最大完成时间。由于该问题子问题较多,将工厂分配和第一阶段的机器分配合并以减少子问题的数量。DVNS包含两个相互协作的变邻域结构,每个变邻域结构都加入全局搜索算子,并应用了邻域搜索和全局搜索协调、邻域结构的合理配置以及当前解的周期性更新等策略。通过大量实例的对比实验表明,DVNS在求解DTHFSP方面具有较强的优势。

关键词: 双变邻域搜索, 分布式调度, 两阶段混合流水车间调度, 准备时间