基于关键链的需求视窗技术在柔性车间调度中的应用

代大齐

摘 要：针对柔性车间调度问题，运用需求视窗来表征其加工环境的模糊性及市场需求，并建立满意度函数，作为车间调度模型的目标函数。为了应对调度过程的复杂性，运用多色集合建立基本信息约束围道矩阵来改进遗传算法，结合关键链，提出基于关键链的需求视窗技术。通过仿真实例验证了给出的调度方法的可行性和有效性。

关键词：柔性车间调度;关键链;需求视窗;遗传算法

中图分类号：TH165文献标识码：A文章编号：1003-5168（2020）04-0033-03

Abstract： Aiming at the flexible job-shop scheduling problem， fuzzy working environment and market demand about flexible job-shop were described by demand time window， and the satisfaction function was established as the objective function of the shop scheduling model. In order to solve the complexity of scheduling， Polychromatic Sets were used to build constraint contour matrix so that the genetic algorithm was improved. Combined with critical chain， a method of demand time window based on critical chain was proposed. The effectiveness and feasibility of this scheduling method were validated by simulation experiments.

Keywords： flexible job-shop;scheduling critical chain;demand time window;genetic algorithm

生產车间调度问题是公认的强NP-hard[1]问题，具有重要的实际意义和理论价值。柔性作业车间调度问题（Flexible Job-Shop Scheduling Problem，FJSP）的研究扩展了经典作业调度，是当前车间调度问题研究的热点之一[2]。通过相关算法及改进算法解决调度问题是较为常用的一种手段[3-5]。赵诗奎提出一种融合改进邻域结构的混合算法[6]，石小秋等提出遗传杂草算法[7]等用于柔性车间调度。目前，在对FJSP的研究上，单一调度的针对性应用研究较多，而对于FJSP的复杂性，大多没有进行有效的分类、简化处理，且优化出的调度方案通用性、实用性不强。

本文在分析柔性调度技术、方法的基础上，结合实际情况，运用关键链简化复杂的FJSP系统，以控制视窗建立针对模糊环境的满意度函数，将关键链和需求视窗技术相结合，并运用多色集合（Polychromatic Sets，PS）[8-9]建立基本信息围道矩阵改进遗传算法来解决柔性车间的调度问题。

1 调度关键链的确立

在调度中存在众多加工瓶颈，瓶颈因素[10]就组成了关键链条[11-12]。……