《基于关键链的需求视窗技术在柔性车间调度中的应用》-工学论文，科技论文-论文范文参考-科学狗论文网

标题

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

范文

代大齐

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

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

中图分类号：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]。其中有两个重要约束：一是机械约束，即关键设备;二是时间约束，即关键时序。

2 需求视窗与满意度函数

需求视窗也叫需求时间窗，是就一个时间段进行控制，要求做到准时交货，是时间上的交货宽放域。若[ri和rj]分别表示需求期望上界和下界，那么需求视窗[Wt=ri-rj]，以[ti]表示完工时间，则期望函数[hi（ti）]（满意度函数）可以表示为：

有时调度关键链有多条，那么满意度函数为（2）式，也是目标函数。

3 仿真实例

某柔性车间，生产5种产品，其加工工序时间如表1所示。

表1中，括号外为实际加工时间，括号内为加工的上下界时间，也可看作是市场期望的正常的加工时间及期望的下界和上界，当然也可以看作是实际生产车间的模糊加工环境。

本例从机械设备和时间约束综合考虑确定调度关键为设备M3#和M2#，并组成关键链，即M3#→M2#，关键链组成为2台设备，条数只有一条。运用PS理论建立约束围道矩阵以有利于最优解的生成，PS建立的是基于基本信息的围道约束矩阵，由实际的柔性车间的基本信息生成。

在遗传算法的编码上采用工序编码，种群大小设为10，交叉率为0.3，变异率为0.08，最大进化代数设为200。运行后获得如图1和图2所示的结果。

图2为调度方案，1-1表示第一个工件的第一道工序，对应长度为加工时长，相同工件为同一个颜色，其他类推。

4 实例分析

采用的是5×5×5案例，即5种类型的工件，工序数最大的为5道工序，在5台设备上加工。与普通车间调度的区别是，该调度车间为柔性车间，设备都具备多工序加工能力，属于多功能机床，如机床M3#具备11道工序的加工能力。实例中柔性加工车间调度问题具有代表性，解决方案的最终运行结果也是有效、可行的。

实例中的不足是多功能机床局限于独占性约束，即每台设备同一时间只具备一道工序的加工能力，不具备同时多道工序的加工能力。在柔性加工车间中，如果有同时性工序加工能力的加工中心类机床存在时，即假设在实例中M3#具备某2道工序的同时加工能力，问题的解决办法是：在围道矩阵中添加一台具备该工序加工能力的虚拟设备，变成6台设备的形式来解决问题，即5×5×6。

在关键链技术的运用上，本例仅选择了综合优先级高的M2#、M3#机床组成关键链，这是由于实例中加工机床、工序数目较少，无须挑选更多关键设备或工序组建关键链。当遇见较为复杂的柔性车间时，关键链可以更长、更多。在运用时，人的因素尤为重要，人需要结合实际情况在关键链长短、条件上进行适当判别。

实例主要基于M3#、M2#这两台关键机床的市场需求（同时也可以看成是模糊性加工环境或人为意愿要求）进行优化，其关注点侧重于解决确立出来的关键机床。从运行结果来看，在经过近80代的迭代后，这两台机床的平均满意度达到了66%的最高值，满足了市场对关键机床的期望。

5 结论

通过仿真实例说明了采用基于关键链技术的需求视窗在柔性车间调度中应用的可行性。同时还应看到的是，以结合需求视窗满意度为目标函数的调度，调度结果是根据市场需求或模糊加工环境得出的，更能反映柔性车间生产的实际情况，调度更具有实际意义。

参考文献：

[1]Demir Y，Isleyen S K. Evaluation of mathematical models for flexible job-shop scheduling problems [J]. Applied Mathematical Modeling，2013（3）：977-988.

[2]Zribi N，Kacem I，Karnel A E. Assignment and scheduling in flexible job-shops by hierarchical optimization[J]. IEEE Transactions on Systems， Man， and Cybernetics， Part C （Applications and Reviews），2007（4）：652-661.

[3]彭乘风，陈庆新，毛宁，等.具有无序工序生产特征的混合柔性流水车间在线调度[J].计算机集成制造系统，2019（11）：2775-2787.

[4]Chaudhy I. Job shop scheduling problem with alternative machines using genetic algorithms [J]. Journal of central south university，2012（5）：1322-1333.

[5]吴锐，郭顺生，李益兵，等.改进人工蜂群算法求解分布式柔性作业车间调度问题[J].控制与决策，2019（12）：2527-2536.

[6]赵诗奎.柔性作业车间调度的改进邻域结构混合算法[J].计算机集成制造系统，2018（12）：3060-3072.

[7]石小秋，李炎炎，邓丁山，等.基于自適应变级遗传杂草算法的FJSP研究[J].机械工程学报，2019（6）：223-232.

[8]王崴，马跃，徐浩，等.基于多色集合理论的螺栓装配工艺建模方法[J].计算机集成制造系统，2014（20）：1851-1858.

[9]傅卫平，刘冬梅，来春为，等.基于多色集合的改进遗传算法求解多品种柔性调度问题[J].计算机集成制造系统，2011（5）：1004-1010.

[10]刘明周，凌琳，唐娟.基于漂移瓶颈的制造车间生产批量/提前期研究[J].中国机械工程，2013（2）：220-225.

[11]谢志强，杨静，周勇，等.基于工序集的动态关键路径多产品制造调度算法[J].计算机学报，2011（2）：406-412.

[12]Mohammad， Raeesi N， Ziad.Kobti. A memetic algorithm for job shop scheduling using a critical-path-based local search heuristic[J]. Memetic computing，2012（3）：231-245.

随便看

科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。