(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111413785.1 (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页 说明书8页 附图2页 CN 114186813 A 2022.03.15 CN 114186813 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时刻开始加工， 工件在每个区间开始加工没有准备时间， 工 件加工过程可中断， 工件可选择在相邻的时间区间切换一次， 切换过程不允许其他工件打 断， 工件从当前区间切换到相邻区间时， 在相邻区间产生一个切换时间s， s为正实数， 工件 切换至多一次， 记pj≤min{ τo， τe}。 3.根据权利要求1所述一种考虑切换时间的两班倒多任务调度优化方法， 其特征在于： 所述考虑切换时间的两班倒的多任务调度问题是NP难的， 问题的最优调度具有的性质如 下： 性质1： 每 个仅在奇数或偶数加工 完成的非切换工件 满足SPT规则， 且机器无空 闲； 性质2： 每 个在奇数和偶数区间连续加工切换工件 满足SPT规则， 且机器无空 闲。 4.根据权利要求1所述一种考虑切换时间的两班倒多任务调度优化方法， 其特征在于： 步骤2中基于最优解 性质的动态规划算法为： 令(j， to， ko， ke)为可行的部分调度集合{J1， J2， ...， Jj}的状态向量， 其中， 参数to表示在 奇数区间的工件初始加工时间和； 参数ko表示在奇数区间的切换时间的数量和； 参数ke表示 在偶数区间的切换时间的数量和； F(j， to， ko， ke)表示最小化对应部分调度的总完工时间 和， 其中， j， ko， ke＝0， 1， ...， n， 此外， 标记∈j， o为工件Jj在奇数区间 完工， 当前区间的空闲时间； ∈j， e为工件Jj在偶数区间完工， 当前区间的空闲时间， j＝0， 1， ...， n； 具体动态规划算法步骤为： 步骤2.1： 将工件集J中所有工件按照SPT规则进行排序， 且重新标号， 可得到初始序列： p1≤p2≤…≤pn； 步骤2.2： 确定边界条件：权　利　要　求　书 1/2 页 2 CN 114186813 A 2步骤2.3： 算法迭代： 对于j＝ko， ke＝0， 1， ...， n； to＝0， 1， ...， 0＜∈j， o＜ τo， o＜∈j， e＜ τe。 其中， 条件1： s＜ ∈o＜pj且 条件2： s＜ ∈e＜pj且 步骤2.4： 得到 最优目标Z*＝min{F(j， to， ko， ke)|0≤to≤P， ko＝0， 1， ...n， ke＝0， 1， ...， n}， 且通过逆向回溯得到最优排序。 5.根据权利要求4所述一种考虑切换时间的两班倒多任务调度优化方法， 其特征在于： 采用动态规划算法对考虑切换时间的两班倒的多任务调 度问题进 行求解， 得到最优调 度的 时间复杂度为O(n3P)， 其中状态变量to最多有P种可能， ko最多有n种可能， ke最多有n种可 能。权　利　要　求　书 2/2 页 3 CN 114186813 A 3