(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111409139.8 (22)申请日 2021.11.25 (71)申请人 中国人民解 放军海军航空大 学 地址 264001 山东省烟台市二马路18 8号接 改装训练大队 (72)发明人 苏析超　崔荣伟　韩维　刘湘一　 肖楚琬　郭放　 (74)专利代理 机构 北京永创新实专利事务所 11121 代理人 易卜 (51)Int.Cl. G06Q 10/06(2012.01) G06Q 10/04(2012.01) G06Q 50/30(2012.01) (54)发明名称 一种考虑飞机转移的地面维护作业串行调 度方法 (57)摘要 本发明公开了一种考虑飞机转移的地面维 护作业串行调度方法， 属于运筹与优化领域； 具 体为： 首先， 初始化调度阶段， 已调度作业集C和 所有停机位状态 变量； 针对当前调度阶段计算可 调度作业集Dg， 并选择调度优先级最高的作业 (i*,j*)， 根据执行所需资源类型， 寻找停机位用 于该待调度作业的保障， 设定开始和结束时刻， 并更新停机位状态变量； 最后， 将待调度作业添 加至已调度作业集C， 返回继续选择当前调度阶 段的可调度作 业集Dg中的下一个作 业， 直至集合 Dg中的所有作 业都完成调度； 令调度阶段自增1， 重复选择下一个调度阶段中， 可调度作业集按优 先级排序的各作业， 直至所有调度阶段下的所有 作业完成调度后结束。 本发明有助于优化调度方 案， 给出最优作业决策方案 。 权利要求书3页 说明书7页 附图2页 CN 114091927 A 2022.02.25 CN 114091927 A 1.一种考虑飞机转移的地 面维护作业串行调度方法， 其特 征在于， 具体步骤如下： 首先， 针对n架飞机组成的待保障机群， 初始化调度阶段g， 已调度作业集C和所有停机 位状态变量； 针对当前第g个调度阶段， 计 算该阶段下的可调度作业集Dg， 并选择集合Dg中调 度优先级最高的作业(i*,j*)， 作为当前调度阶段的待调度作业； 然后， 根据待调度作业(i*,j*)执行所需资源类型， 寻找停机位用于待调度作业(i*, j*)的保障， 设定待调度作业(i*,j*)的开始和结束时刻， 并更新停机位状态变量； 最后， 将待调度作业添加至已调度作业集C， 返回继续选择当前调度阶段的可调度作业 集Dg中的下一个作业， 直至集合Dg中的所有作业都完成调度； 令调度阶段g＝g+1， 重复选择 下一个调度阶段中， 可调度作业集按优先级排序的各作业， 直至所有调度阶段下 的所有作 业完成调度后结束。 2.如权利要求1所述的一种考虑飞机转移的地面维护作业串行调度方法， 其特征在于， 所述待保障机群的编号集合表 示为I＝{1,2, …,i,...,n}； 其中第i架飞机的作业工序集合 为Ji＝{1,2,…,|Ji|}， 用数组(i,j)表示第i架飞机的第j道工序； 调度阶段初始化为 g＝1， 已调度作业集C为待调度飞机虚拟的开始工序集合， 即 保障场地上的保障停 机位的编号集合PS＝{1 ,2 , …p ,...,m} ； 初始化所有停机位状态为空闲， 即 Tp(t)为停机 位p在时刻t的状态， Tp(t)＝i表示停机位p被第i架飞 机占用； Tp(t)＝‑1表示飞机在停机位p上解系留； Tp(t)＝‑2表示飞机在停机位p上系留。 3.如权利要求1所述的一种考虑飞机转移的地面维护作业串行调度方法， 其特征在于， 所述可调度作业集Dg计算公式为： 即可调度作业集为紧前作 业全部完成调度且自身未被调度的作业集合； Pij为第i架飞机的第j道工序的紧前作业集 合。 4.如权利要求1所述的一种考虑飞机转移的地面维护作业串行调度方法， 其特征在于， 所述调度优先级由各作业的工期时间决定， 作业工期时间越短， 优先级越高， 对于相同工期 的作业， 优先选择编号较小的作业。 5.如权利要求1所述的一种考虑飞机转移的地面维护作业串行调度方法， 其特征在于， 所述寻找停机位用于待调度作业(i*,j*)的保障， 设定待调度作业(i*,j *)的开始和结束时 刻， 并更新停机位状态变量， 具体步骤如下： 步骤4.1、 时间变量t初始化 为待调度作业(i*,j*)所有紧前作业完成时刻的最大值t0； 即： Eij为作业(i,j)的结束时刻； 步骤4.2、 根据停 机位状态 变量找到时刻t0之后， 飞机i*转移所需的若干停 机位， 并依次 记录飞机i*在各停机位上的开始解系留时刻； 记时刻t0之后， 飞机i*转移所需的第一个停机位为p*， 为时刻t0之后飞机i*在停机 位p*上的开始解系留时刻； 步骤4.3、 依次判断待调度飞机时刻t0之后安排的停机位p*是否可 以用于待调度作业 (i*,j*)的执行， 若是， 输出该停机位p*及作业开始时刻， 更新停机位p*在当前时间段内为 被飞机i*占用， 终止； 否则， 转入步骤4.4；权　利　要　求　书 1/3 页 2 CN 114091927 A 2停机位p*用于待调度作业(i*,j*)执 行的条件为： 1)该停机位可提供待调度作 业执行所需的资源类型； 2)飞机i*在该停机位驻留时间段 长度大于待调度工序工期； 步骤4.4、 搜索所有可为待调度作业(i*,j*)提供保障资源的停机位， 选出符合条件的 停机位储存在集合EM中， 其余不符合条件的停机位储存在集合UM中； 若集合EM不是空集， 则 针对集合EM中的停机位， 选择最后一个非空闲时刻最小的停机位q*， 将待调度飞机i*转移 至该停机位q*， 终止； 否则转入步骤4.5； 条件是指： 该停机位的最后一个非空 闲时刻为飞机解系留； 步骤4.5、 从集合UM中选择具有最早空闲时刻的停机位o*， 将占用该停机位o*的飞机e 转移至具有最早解系留时间的空闲停机位v*， 再将待调度 飞机i*转移至该停机位o*， 以执 行待调度作业(i*,j*)。 6.如权利要求5所述的一种考虑飞机转移的地面维护作业串行调度方法， 其特征在于， 所述步骤4.4中飞机i*从停机位p*转移至停机位q*， 具体为： 首先， 确定停机位p*的最后一个非空闲时刻 则飞机i*到达停 机位q*开始系留的时刻为 tx为飞机到达停 机位进行作业之前的系留时间； tas为停机位s的最后一个非空闲时刻； 为飞机在停机位p*和q*之间的转移时间； 然后， 进一 步分别计算待调度作业(i*,j*)的开始时刻和结束时刻； 开始时刻为： 结束时刻为： 为作业(i*,j*)的工期； 当停机位p*在时间段 内为解系留， 停机位q*在时间段[t1+ 1,t1+tx]内为系留时， 设置停机位q*在时间段 内为被飞机i*占用； 若飞机i*在原停机位p*开始解系留时刻 则说明飞机i*需要在原停 机 位 p * 停 留 一 段 时 间 后 才 能 转 移 至 停 机 位 q * ， 设 置 停 机 位 p * 在 时 间 段 内被飞机i*占用， 即 7.如权利要求5所述的一种考虑飞机转移的地面维护作业串行调度方法， 其特征在于， 所述步骤4.5具体为： 首先， 确定飞机e到达停机位v*的时刻 设置停机位v*在 时间段[t2+1,t2+tx]内为系留， 在时刻t2+tx+1为被飞机e占用； 确定飞机e在停机位o*上开 始解系留的时刻为 设置停机位 o*在时间段 内为解系留； 若飞机e在停机位o*上开始解系留的时刻大于停机位o*的最后一个非空闲时刻， 即 则说明飞机e需要在原停机位o*停留一段时间后才能转移至停机位 v*， 设置停机位 o*在时间段 内为被飞机e占用；权　利　要　求　书 2/3 页 3 CN 114091927 A 3