(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111613343.1 (22)申请日 2021.12.27 (71)申请人 惠州学院 地址 516001 广东省惠州市惠城区演达大 道46号 (72)发明人 张晓欢　王震　张丹　 (74)专利代理 机构 广东创合知识产权代理有限 公司 44690 专利代理师 赵瑾 (51)Int.Cl. G06Q 10/06(2012.01) G06Q 10/04(2012.01) G06Q 50/04(2012.01) (54)发明名称 一种可回溯 的二车间工序序列择时调度方 法 (57)摘要 本发明涉及一种可回溯调整的二车间工序 序列择时综合调度方法， 包括以下步骤： 将产品 工艺树中工序之间偏序关系取反， 得到逆序工艺 树； 按工序序列排序方法确定产品工艺树中各工 序加工顺序， 并存入工序队列Qu； 将第一工序序 列上工序从工序队列Qu中出队， 并在同一车间内 进行调度， 形成初始调度方案； 将工序队列Qu中 位于队头的工序出队， 按二车间择时调度策略和 二车间冲突调整策略确定其调度方案； 判断所述 调度方案加工总时间是否超过其 “调度参照时 间”， 若不超过， 则选 择该调度方案； 若超 过， 则启 动二车间回溯调整策略重新调度该工序以及相 关工序， 最终得到该工序调度方案。 本发明能够 有有效优化综合调度的结果。 权利要求书3页 说明书7页 附图2页 CN 114493125 A 2022.05.13 CN 114493125 A 1.一种可回溯调整的二车间工序 序列择时综合调度方法， 其特 征在于， 包括以下步骤： 将产品工艺 树中工序之间偏序关系取反， 得到逆序工艺 树； 按工序序列排序方法确定产品工艺 树中各工序加工顺序， 并存 入工序队列Qu； 将第一工序序列上工序从工序队列Qu中出队， 并在同一车间内进行调度， 形成初始调 度方案； 将工序队列Qu中位于队头的工序出队， 按二车间择时调度 策略和二车间冲突调整策略 确定其调度方案； 判断所述调度方案加工总时间是否超过其 “调度参照时间 ”， 若不超过， 则选择该调度 方案； 若超过， 则启动二车间回溯调整 策略重新调 度该工序以及相关工序， 最 终得到该工序 调度方案 。 2.根据权利要求1所述的可回溯的二车间工序序列 择时调度方法， 其特征在于， 所述二 车间回溯调整 策略为在调度工序的基础调 度方案中， 分别 在两个车间中寻找该调度工序的 准调度时间点， 分别在准调度时间点上对该工序进行 试调度， 得到若干 工序试调度方案 。 3.根据权利要求1所述的可回溯的二车间工序序列 择时调度方法， 其特征在于， 所述二 车间回溯调整策略为根据回溯参数值进行二车间回溯调整， 得到若干工序试调度方案， 在 试调度方案当中选择加工总用时最少的工序试调度方案作为该工序的调度方案 。 4.根据权利要求1所述的可回溯的二车间工序序列 择时调度方法， 其特征在于， 包括步 骤： 步骤A1： 定义产品在第一车间和第二车间中进行加工， 设置回溯参数值 n； 步骤A2： 将产品工艺 树中加工偏序关系逆置， 形成产品逆序工艺 树； 步骤A3： 按工序序列排序 策略为逆序工艺树划分工序序列， 并按工序序列由长到短， 将 其中各工序分别加入工序队列； 步骤A4： 在第一车间中， 调度逆序工艺树中最长工序序列上的N个工序,形成初始调度 方案； 步骤A5： 设非最长 工序序列上工序数为m， 此时工序队列中有m个工序未调度； 步骤A6： i ＝1； 步骤A7： 判断i<＝m是否成立， 若成立 转至步骤A8， 若不成立 转至步骤A 20； 步骤A8： 利用二车间择时调度策略和二车间冲突调整策略调度第i个非最长工序序列 工序； 步骤A9： 判断该工序调度方案加工总时间是否大于该工序的 “调度参照时间 ”， 若是转 至步骤A10， 若否转至步骤A19； 步骤A10： 找到该工序的工序序列中第1个工序X， 计算工序X排在当前调度工序之前的 位数， 将该位数记为 k； 步骤A11： 若k<n成立， 则n取k的值； 步骤A12： j＝n.设置工序调度方案链表， 将工序队列中排在第N+i ‑j‑1位工序的调度方 案加入第N+i ‑j‑1位工序调度方案链 表； 步骤A13： 判断j>＝0是否成立， 若成立 转至步骤A14， 不成立 转至步骤A18； 步骤A14： 判断第N++i ‑j‑1位工序调度方案链表是否为空， 若不为空， 转至步骤A15， 若 为空， 转至步骤A17；权　利　要　求　书 1/3 页 2 CN 114493125 A 2步骤A15： 将第N+i ‑j‑1位工序调度方案链表中排在表头的工序调度方案出队， 作为第N +i‑j位工序的基础调度方案； 在第一车间和第二车间中分别找到第N +i‑j位工序的 “准调度 时间点”， 在这些“准调度时间点 ”上分别应用二车间择时调度策略和二车间冲突调整策略 对该第N+i ‑j位工序进行试调度， 得到若干第N+i ‑j位工序准调度方案， 依次将这些准工序 调度方案存 入第N+i‑j位工序调度方案链 表中； 步骤A16： 判断第N+i ‑j‑1位工序调度方案链表是否为空， 不为空， 转至步骤A15， 为空， 转至步骤A17； 步骤A17： j ‑‑， 转至步骤A13； 步骤A18： 在第N+i位工序调度方案链表中选择加工用时最少的工序调度方案作 为第N+ i位工序调度方案； 步骤A19： i+ +， 转至步骤A7； 步骤A20： 当前所得到的第N+m位工序调度方案即该产品最终调度方案； 步骤A21： 输出调度结果甘特图。 5.根据权利要求1所述的可回溯的二车间工序序列 择时调度方法， 其特征在于， 所述二 车间择时调度策略包括 步骤： 步骤B1： 设工序为Wi(n1+1<＝i<＝N)， 其加工时间为ti， 加工设备为Mi， 基础调度方案为 Pi‑1； 步骤B2： 确定第一车间中Mi上的m1(m1>＝1)个“准调度时间点 ”， 并将其逐一加入集 合C； 步骤B3： 确定第二车间中Mi上的m2(m2>＝1)个“准调度时间点 ”， 并将其逐一加入集 合C； 步骤B4： 对集合C中的m＝(m1+m2)个“准调度时间点 ”按从小到大 的规则排序， 结果依次 入队列QTi； 步骤B5： k ＝1； 步骤B6： 判断队列QTi是否为空， 为空转至步骤B12， 不 为空转至步骤B7； 步骤B7： 对QTi做出队操作， 结果存 入T； 步骤B8： 判断T是否为方案Pi‑1中其所在车间Mi上的空闲时间或某个工序的加工结束时 间， 是则转至步骤B10， 否则转至步骤B9； 步骤B9： 在方案Pi‑1上以时间点T作为Wi.st对工序Wi进行调度， 将Wi加入到其加工车间 中设备Mi的已调度工序链 表中， 且位置在工序Wj(1<＝j<＝ i‑1)之前， 转至步骤B1 1； 步骤B10： 在 方案Pi‑1上以时间点T作为Wi.st对工序Wi进行调度， 将Wi按加工开始时间升 序的顺序加入到其加工车间中设备Mi的已调度工序链 表； 步骤B11： 启动冲突调整策略生成工序Wi准调度方案Pik， k++， 转至步骤B6； 步骤B12： 在Pi1到Pim的方案中选择总加工用时最少的方案， 且判断其是否唯一， 是则 转 步骤B13， 否则转至步骤B14； 步骤B13： 选择其作为工序Wi调度方案， 转至步骤B15； 步骤B14： 选择工序Wi加工结束时间最 早的方案作为工序Wi调度方案； 步骤B15： 更新调度方案链 表信息， 计算当前 方案的加工总用时， 退 出。 6.根据权利要求1所述的可回溯的二车间工序序列 择时调度方法， 其特征在于， 所述二 车间冲突调整策略包括 步骤： 步骤C1： 将当前调度工序Wi入队Qa；权　利　要　求　书 2/3 页 3 CN 114493125 A 3