具有特殊约束的流水车间成组调度问题研究

雩风三日

具有特殊约束的流水车间成组调度问题研究

    流水车间成组调度问题广泛存在于具有批组加工特征的流程工业中。在特定的生产环境下，流水车间成组调度问题往往伴随着源于生产工艺的特殊约束，这些约束的存在使得问题性质发生了变化，从而需要更具针对性的解决方法。论文从钢铁企业无缝钢管生产管理的实际需求出发，提炼出具有工件相关性阻塞、双向运输时间、序列相关准备时间等特殊但关键约束的流水车间成组调度问题，以最小化最大完工时间(Makespan)为优化目标，对其基本性质、数学模型和求解算法展开研究。主要研究内容和创新点如下:
- D7 F6 W# P. a    (1)以无缝钢管产品在管加工车间的生产实际为背景，研究了一类具有工件相关性阻塞约束的两阶段流水车间成组调度问题。构建了问题的混合整数线性规划模型，通过三划分问题的多项式归结证明了该问题具有强NP难特性，将问题划分为工件组间调度和各工件组内工件间调度两个子问题，提出一种协同进化的分布估计算法。基于实际生产数据设计多种问题规模的实验，验证了模型和算法的有效性。
2 S+ R9 I0 C$ V' j1 V* B" ~    (2)结合无缝钢管在管加工车间的生产管理需求，进一步考虑了阶段间运输工具的双向运输时间约束，对具有双向运输时间和工件相关性阻塞约束的两阶段流水车间成组调度问题展开研究。针对此调度问题，建立混合整数线性规划模型，结合问题特征提出一种协同进化遗传算法。算法通过协同进化框架对工件组间调度和各工件组内工件间调度两个子问题进行联合优化，提出一种基于区块挖掘的人工解构造策略来提升算法收敛速度。数值实验表明，所提模型和算法对于求解的问题具有良好的效果。
5 p- u& N: S  ~: @) G- o    (3)将钢铁行业普遍存在的双向运输时间约束引入经典的流水车间成组调度问题，同时加入序列相关准备时间，研究了具有序列相关准备时间和双向运输时间约束的多阶段流水车间成组调度问题。构建了问题的混合整数线性规划模型，提出一种改进的迭代贪婪算法，算法通过启发式规则构造问题的初始解，并设计了改进的迭代贪婪规则和接受准则来提升算法的求解质量和效率。基于理论分析给出了问题最优解的两个下界。通过不同规模的数值实验和对比算法的比较分析，验证了所提算法的有效性和鲁棒性。
, O" E: s2 z. W9 n0 D    (4)将问题范围进一步扩展至混合流水车间，研究了具有序列相关准备时间和无关并行机的混合流水车间成组调度问题。针对此问题，建立数学模型，提出一种改进的候鸟优化算法。算法通过新的编码和解码策略来表征各工件组在各阶段上并行机的选择，各并行机上工件组间的加工顺序，以及各工件组内工件间的加工顺序三个子问题，基于编码策略设计了邻域结构和邻域解构造策略，并提出一种重置机制来平衡算法的全局和局部搜索能力。仿真实验表明该算法可以在短时间内获得较好的调度结果，且具有良好的稳定性。
9 d, g$ M. f# ~2 S2 J' I
关键词:流水车间成组调度；工件相关性阻塞；双向运输时间；序列相关准备时间；元启发式