时间约束混合流水车间调度问题综述

A survey on time constrained hybrid flow shop scheduling problems

中文关键词  混合流水车间调度  无等待约束  准备时间约束  模糊/随机加工时间约束  多时间约束  多目标优化

英文关键词  hybrid flow shop  no-wait constraint  setup time constraint  fuzzy or stochastic processing time constraint  multiple time-constrained  multi-objective optimization

中文摘要

      车间调度是智能制造领域中的核心问题之一, 在经典流水车间调度中, 所有工件按照相同的加工顺序在指 定机床上加工. 混合流水车间调度(HFS)作为流水车间调度的特例, 相比前者增加了机床选择的灵活性, 可以显著 优化系统目标, 但同时也增加了问题求解的难度. 由于时间约束HFS相比基本HFS问题更贴近实际生产过程, 近年 来, 综合考虑各类时间相关约束的HFS问题得到了深入研究. 因此, 本文围绕基本HFS、有限等待时间HFS、带准备 时间HFS、模糊/随机加工时间HFS、多时间约束HFS、时间约束相关多目标HFS等问题开展研究. 针对每一类时间 约束HFS问题, 按照问题规模对当前研究成果进行分类描述, 按照确定性算法、启发式方法、元启发式方法、算法混 合对相关成果进行算法分类, 按照实际工业应用对文献进行归类分析. 另一方面, 围绕交货期、能耗、成本等3类性 能指标, 分析了在各类时间约束HFS问题中的多目标优化相关成果. 最后详细分析了带时间约束HFS问题在问题层 面、算法层面和应用层面存在的挑战性问题和未来研究的方向.

英文摘要

      Scheduling is one of the key technology of intelligent manufacturing, in typical flow shop scheduling, all jobs should be processed according to the same sequence through all the given machines. As an extension of the classical flow shop, in hybrid flowshop scheduling(HFS), all jobs should select one suitable machine from a set of candidate machines, which increase the flexibility, and thus improve the performance significantly. Nevertheless, the complexity of the system is also increased and thus the problem is even more hard to be solved. Therefore, we give a survey on researches of several time-constrained HFS problems, including the canonical HFS, HFS with limited wait time constraints, HFS with setup time constraints, HFS with fuzzy or stochastic processing times, HFS with multiple time constraints, and time-constrained multi-objective HFS. For each type of time-constrained HFS, firstly, the literatures are classified according to their problem scales. Then, all the researches are categorized into four types according to exact algorithm, heuristics, meta-heuristics, and hybrid algorithms. Further, the realistic applications of the related time-constrained HFS are also analyzed. Meanwhile, the algorithms about the multiple objectives are also analyzed according to three aspects, i.e., considering the due dates, energy consumption, and costs. Lastly, from problem features, algorithm classification, and the application aspects, the time-constrained HFS are summarized both in challenging problems and future research focuses. The problem features, algorithms, and typical applications about these problems are reviewed. Finally, we also give a brief description about the future challenging issues of the HFS with special process constraints.