(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111413606.4 (22)申请日 2021.11.25 (71)申请人 西北工业大 学 地址 710072 陕西省西安市友谊西路127号 (72)发明人 王军强　王艳　胥军　孙涛　 (74)专利代理 机构 西北工业大 学专利中心 61204 代理人 陈星 (51)Int.Cl. G06Q 10/06(2012.01) G06Q 10/04(2012.01) (54)发明名称 考虑加工异速的两班倒多任务调度优化方 法 (57)摘要 本发明提出一种考虑加工异速的两班倒多 任务调度优化方法， 以两班倒多任务加工为研究 对象， 考虑工件在不同班次之间切换对生产目标 影响的实际问题。 通过建立工件切换的模型， 研 究具有不同加工速度的不同班次切换需要额外 切换成本的两班倒多任务调度， 分析工件切换的 切换成本与班次的关系， 设计伪多项式时间的动 态规划算法， 得到多任务调度决策方案。 本发明 面向生产实际， 旨在为企业协调两班倒工作制的 多任务调度优化决策提供理论依据， 也为其它类 型三班倒等工作模式提供 可借鉴的研究模式。 权利要求书2页 说明书7页 附图1页 CN 114186812 A 2022.03.15 CN 114186812 A 1.一种考虑加工异速的两班倒多任务调度优化方法， 其特 征在于： 包括以下步骤： 步骤1： 针对考虑加工异速的两班倒多任务调度问题， 构建考虑加工异速的两班倒多任 务调度模型： 模型优化目标为 最小化完 工时间和及总加急成本； 步骤2： 采用基于最优解性质的动态规划算法对步骤1中考虑加工异速的两班倒多任务 调度问题进行求 解， 得到最优调度。 2.根据权利要求1所述一种考虑加工异速的两班倒多任务调度优化方法， 其特征在于： 所述考虑加工异速的两班倒多任务调度问题为： 给定包含n个工件的工件集合J＝{J1,J2,…,Jn}， 工件Jj的加工时间为pj， 工期为dj， 记 将单台机器的时间分为奇数时间区间和偶数时间区间， 定义[0, τo],[ τo+τe,2τo+τe],[2 ( τo+τe),2( τo+τe)+τo],…记作[a( τo+τe),a( τo+τe)+τo]， a＝{0,1,2, …}为奇数区间； 定义 [τo, τo+τe],[2τo+τe,2( τo+τe)],[3τo+2τe,3( τo+τe)],…记作[b( τo+τe)‑τe,b( τo+τe)]， b＝ {1,2,…}为偶数区间； 安排工件在机器上加工， 工件有三种加工方式： 1、 工件仅在奇数区间加工； 2、 工件仅在 偶数区间加工； 3、 工件在奇数和偶数区间切换并加工完成； 前两种加工方式的工件称为非 切换工件， 第三种加工方式的工件称为切换工件； 工件在0时刻到达， 机器在0时刻开始加工， 工件在每个区间开始加工没有准备时间， 工 件加工过程可中断； 机器在不同加工区间以不同的速度运行， 其中机器在奇数区间的加工 速度为vo， 在偶数区间的加工速度为ve； 因此， 工件Jj在奇数区间的实际加工时间为pj/vo， 在 偶数区间的实际加工时间为pj/ve； 工件可选择在奇数区间和偶数区间来回切换以尽早完成 加工， 并产生 一个加急成本 。 3.根据权利要求1所述一种考虑加工异速的两班倒多任务调度优化方法， 其特征在于： 所述考虑加工异速的两班倒多任务调度问题是NP难的， 问题的最优调度具有的性质如下： 性质1:每 个仅在奇数或偶数加工 完成的非切换工件 满足SPT规则， 且机器无空 闲； 性质2:每 个在奇数和偶数区间连续加工切换工件 满足SPT规则， 且机器无空 闲。 4.根据权利要求1所述一种考虑加工异速的两班倒多任务调度优化方法， 其特征在于： 步骤2中基于最优解 性质的动态规划算法为： 令(j,to,w)为可行的部分调 度集合{J1,J2,…,Jj}的状态向量， 其中， 参数to表示在奇数 区间的工件初始加工时间和； 参数w表示部分调度的加急成本和； F(j,to,w)表示最小化对 应部分调度的总完工时间和及总加急成本， 其中， j＝0,1, …,n， w＝ 0,φ,…,nφ； 具体动态规划算法步骤为： 步骤2.1： 将工件集J中所有工件按照SPT规则进行排序， 且重新标号， 可得到初始序列： p1≤p2≤…≤pn； 步骤2.2： 确定边界条件： 权　利　要　求　书 1/2 页 2 CN 114186812 A 2步骤2.3： 算法迭代： 对于 其中， 如 果 奇 数 加 工 区 间 先 空 闲 ； 如果偶数加工区间先空 闲； 步骤2.4： 得到最优目标Z*＝min{F(n,to,w)|0≤to≤P,0≤w≤nφ+， 且通过逆向回溯得 到最优排序。 5.根据权利要求4所述一种考虑加工异速的两班倒多任务调度优化方法， 其特征在于： 采用动态规划算法对考虑加工异速的两班倒多任务调度问题进行求解， 得到最优调 度的时 间复杂度为O(n2P)， 其中状态变量to最多有P种可能， w 最多有n种可能。权　利　要　求　书 2/2 页 3 CN 114186812 A 3