物料供应干扰环境下的飞机移动生产线调度问题本质上是一类不确定环境下的项目调度问题, 现有文献针对此类问题进行了较为充分的研究。部分****从前摄调度方法入手, 考虑了作业时长的不确定性, 通过插入缓冲时间来提高模板调度计划的稳定性, 设计了基于抽样仿真评价的启发式和元启发式算法来优化分配整个调度中的缓冲区[6-9]。Lambrechts[10]和Ma[11]等考虑了资源可用性的不确定性, 设计了前摄-反应调度框架, 前摄阶段以调度计划解鲁棒性为优化指标生成模板调度计划, 执行阶段采用反应式调度策略, 以最小化与模板调度计划的偏差为目标函数生成新调度计划。van de Vonder等[12]针对作业突发中断问题, 提出了鲁棒串行和并行调度机制, 结合优先级规则和启发式算法, 设计了鲁棒反应式调度程序。Chakrabortty等[13]分别考虑资源中断干扰场景, 建立了混合整数规划模型, 提出了多种启发式算法来求解模型。Davari和Demeulemeester[14]针对作业时长的不确定性, 综合考虑前摄调度和反应调度所产生的成本, 提出了基于多阶段动态规划的数学模型来解决最优化问题。Chand等[15]针对资源干扰环境的项目调度问题, 建立了多目标规划模型, 并设计了基于遗传规划的改进优先规则启发式程序进行求解。针对物料供给延期干扰, 陆志强等[16]建立了以最小化调度计划变动成本和资源额外投入成本加权和为目标函数的调度模型, 设计了基于支持向量数据描述的动态调度算法进行求解。
从上述文献来看, 考虑的不确定性因素主要集中在作业时长、作业所需资源可用性等方面, 对考虑作业所需物料供应不确定性的项目调度问题研究较为匮乏。文献[16]虽然在飞机移动生产线背景下考虑了物料供应不确定环境, 但在问题描述中仅考虑后续作业的物料预计可送达时间, 简化了对物料供应不确定性的处理。实际上, 随着飞机装配进度的推进及对物料供应过程的实时监测, 生产管理人员除了能准确获知某些作业的物料延期到达时间以外, 还能对后续作业的物料到达时间概率分布进行预测。在物料延期干扰发生时, 生产管理人员希望利用最新掌握的物料供应信息, 兼顾调度决策的反应性和预见性, 从而最大程度地降低物料供应干扰环境对飞机移动生产线正常运作的影响。针对此需求, 本文以物料供应干扰环境下的飞机移动生产线装配作业调度问题为研究对象, 借鉴文献[17]中针对多阶段随机优化过程的、基于二阶段近似优化模型的决策框架, 提出了物料供应干扰环境下的动态调度框架, 建立了滚动决策点的二阶段近似优化模型。针对模型的决策逻辑, 设计了以两阶段禁忌搜索算法为框架的启发式算法进行求解。通过数值实验, 验证了所提动态调度方法的有效性。
1 问题描述与数学模型 1.1 问题描述与基本假设 物料供应干扰环境下的飞机移动生产线装配作业调度问题, 是在物料供应延期导致装配作业无法按原始计划执行的情况下, 通过反应调度优化决策未开始作业的开始时间, 以减少实际执行计划与模板装配计划的偏差和装配工期, 从而达到最小化反应调度总成本的目的。针对飞机移动生产线装配工位特点, 给出如下基本假设:①装配工位的模板装配计划已定; ②将装配工位调度问题抽象为资源受限项目调度问题, 即装配作业的调度应同时满足作业优先级、可用资源上限等基本约束; ③如图 1所示, 在飞机移动生产线各个装配工位中考虑多类共享的可更新资源, 包括装配工人、关键装配设备、能源供应设备、线边存储空间等; ④装配作业所需物料动态到达且为齐套准时化配送; ⑤时间轴作离散化处理。
 |
| 图 1 飞机移动生产线装配工位布局图 Fig. 1 Assembly station layout of aircraft mobile production line |
| 图选项 |
表 1汇总了参数及决策变量, 其中作业编号0与n+1为虚作业, 其执行工期与资源需求量为0。
表 1 参数与决策变量 Table 1 Parameters and decision variables
| 参数 | 定义 |
| J | 作业集合 |
| n | 作业数量 |
| j∈[0, 1, …, n, n+1] | 作业序号 |
| K | 可更新资源集合 |
| k∈K | 资源种类编号 |
| T | 时间集合 |
| t∈T | 时间编号 |
| pj | 作业j的执行工期 |
| Pj | 作业j的紧前作业集合 |
| rjk | 作业j对第k种资源的需求量 |
| Rk | 第k种资源总量 |
| sj0 | 作业j的模板计划开始时间 |
| Aj0 | 作业j的物料计划到达时间 |
| d | 作业的物料配送提前期 |
| 决策变量 | 定义 |
| sj | 整数变量, 作业j的开始时间 |
| xjt | 0/1变量, 作业j在时刻t开始取1, 否则取0 |
表选项
1.2 物料供应干扰环境下的动态调度框架 本文所考虑的物料供应干扰具体体现为2个方面:①当前某一作业的物料供应发生延期且延期到达时间已知, 此类干扰直接导致作业推迟执行; ②部分未开始作业的物料到达时间服从某概率分布, 换言之, 这些作业的物料到达情况具备多个可能的场景, 每个场景均可能发生物料延期干扰, 这些干扰虽尚未发生, 但隐含在后续计划执行过程中。由此, 本文将受干扰作业的物料延期到达时间归为确定性信息, 将部分未开始作业的物料到达时间概率分布定义为不确定性信息。
由于部分作业的物料供应方式为JIT供货方式, 其物料供应过程易受外部环境影响, 此类作业的物料到达时间具有不确定性。对于此类作业, 在其物料开始配送之前, 管理人员只能通过预测获得其物料到达时间的概率分布, 且概率分布的方差(即预测准确度)会随着预测时间的临近越来越小。此外, 当干扰事件发生时, 即作业的物料到达时间晚于计划配送时间时, 触发反应调度动作, 此时延期物料的到达时间变为确定性信息, 同时后续作业的物料到达时间概率分布得到更新。
在反应调度动作层面, 本文所提出的动态调度方法是由干扰事件驱动的, 干扰事件发生的时间点为滚动决策点。与常规重调度方法不同的是, 本文将后续作业的调度决策分为两阶段进行:将第q次干扰发生的时刻记为Tq, 将Tq后具有完全确定性信息的时间段记为固定决策阶段, 将Tq后首次出现不确定性信息的时间点记为Tq+1, 则Tq到Tq+1之间的时间为固定决策阶段, 该阶段的决策模型为确定性模型, 其决策用以替代该阶段的原始计划; 而Tq+1后的时间为预测决策阶段, 该阶段的决策模型为不确定性模型, 通过构建场景的方法建模求解, 其决策无需实际执行, 仅用于评价固定决策阶段的决策。
依据上述分析, 在Tq时刻, 将作业划分为3类集合, 如图 2所示。图中:虚线框为物料配送作业, 实线框为装配作业。3类作业的决策属性描述如下:
 |
| 图 2 Tq时刻的甘特图 Fig. 2 Gantt chart at Tq |
| 图选项 |
1) JF类。物料配送作业已经完成或已经开始但未完成的作业(作业1、2), 按原始计划执行。
2) JD类。物料计划配送时间位于固定决策阶段内的作业, 包括物料延期到达的作业(作业3), 以及物料到达时间已确定的作业(作业4、5、6), 将进行固定决策。
3) JP类。物料计划配送时间在Tq+1(作业7的物料到达时间不确定)后的作业(作业7、8、9、10、11、12、13), 将进行不同场景下的预测决策。
为了明确描述相邻滚动决策点间的决策更新情况, 以图 2中Tq时刻的甘特图为例进行说明。此时JD类作业将进行固定决策, 决策结果将替代原始计划并实际执行; 当时间推进至Tq+1, 得到图 3所示的甘特图, 其中作业3、4、5、6的开始时间为Tq时刻进行固定决策的结果, 对于作业7、8、9、10、11、12、13而言, 由于物料到达信息的更新, 保留了其在Tq+1进行决策更新的权利。在Tq+1, 作业1、2、3、4、5、6更新为JF类作业, 作业7、8、9、10更新为JD类作业, 作业11、12、13更新为JP类作业。
 |
| 图 3 Tq+1时刻的甘特图 Fig. 3 Gantt chart at Tq+1 |
| 图选项 |
结合信息和操作层面的分析, 以及对不同作业类型决策属性的描述, 给出物料供应干扰环境下的动态调度框架, 如图 4所示。
 |
| 图 4 动态调度框架 Fig. 4 Framework of dynamic scheduling |
| 图选项 |
1.3 二阶段近似优化模型 根据1.2节的两阶段决策逻辑, 本节建立二阶段近似优化模型。由于飞机装配复杂度高, 集成在生产线上的装配资源种类较多, 模板装配计划耦合了大量的装配资源配置计划。一旦出现作业因物料供应延期而推迟执行的干扰, 模板装配计划将不再可行, 实际执行的调度结果会产生不可避免的偏差, 将加重装配资源调配负担, 同时装配工位实际工期也将被迫延长。因此, 本文的目标函数同时考虑了实际执行计划与模板装配计划的偏差和装配工期2类指标。根据企业实际需求, 可为2类优化指标设定单位时间成本权重ω1和ω2, 并采用加权求和的标量化方法将2个不同的优化指标转化为单目标函数。由此, 本文以最小化与模板装配计划的偏差及工期的加权和作为调度决策(记为S)的综合成本衡量指标f(S), 可写为
 | (1) |
设Aj表示作业j的物料到达时间。对于物料到达时间已知的作业, 直接获取其物料到达时间确定值; 对于物料到达时间不确定的作业, 采用蒙特卡罗抽样法, 从已知概率分布中随机抽样, 获取其物料到达时间样本值。对每个概率分布进行单次抽样后, 含有n个作业物料到达时间的序列Y可表示为
 |
将每次抽样后获得的序列Y定义为一个物料到达场景。重复抽样N次后, 物料到达场景集合Θ可表示为
 |
通过设置物料到达场景集合, 将不确定性问题转化为若干个场景下的优化问题, 其中每个场景下的优化问题均包含对JD类作业的固定决策(记为S1)和JP类作业的预测决策(记为S2, θ, θ∈Θ)。2个阶段的决策分别对应固定成本f(S1)和期望成本E[f(S2, θ)], 目标函数可表示为两者之和, 即
 | (2) |
式(2)可通过不同场景下的预测决策, 评估固定决策的自身效能及应对不同场景的反应能力, 达到兼顾调度决策反应性和预见性的目的。为了使模型表达更为简洁, 决策变量统一用场景进行表述。补充参数并修正决策变量, 修正后的参数和决策变量如表 2所示。
表 2 修正的参数与决策变量 Table 2 Modified parameters and decision variables
| 参数 | 定义 |
| q∈[0, 1, …, ε] | 干扰编号, 0代表无干扰, ε为干扰总数 |
| Tq | 第q次干扰发生时刻 |
| JF, JD, JP | 3类作业集合 |
| sR, j(j∈JF) | JF类作业j的实际开始时间 |
| ω1, ω2 | ω1为与模板装配计划偏差的单位时间成本权重, ω2为工期的单位时间成本权重, 且满足ω1+ω2=1 |
| Θ | 物料到达场景集合 |
| N | 场景数量 |
| θ∈Θ | 场景编号 |
| Aj, θ | 场景θ下, 作业j的物料到达时间 |
| 决策变量 | 定义 |
| sj, θ | 整数变量, 场景θ下, 作业j的开始时间 |
| xjt, θ | 0/1变量, 场景θ下, 作业j在时刻t开始取1, 否则取0 |
表选项
修正参数与决策变量后, 式(2)可改写为目标函数式(3), 目标函数受式(4)~式(12)的约束。
 | (3) |
 | (4) |
 | (5) |
 | (6) |
 | (7) |
 | (8) |
 | (9) |
 | (10) |
 | (11) |
 | (12) |
式(4)表示任意场景下任意JF类作业的决策一致; 式(5)表示对JD类作业的固定决策在任意场景下保持一致; 式(6)表示决策变量sj, θ与xjt, θ之间的关系; 式(7)表示任意场景下任意作业均应满足作业优先级约束; 式(8)表示任意场景下任意时刻所有执行的作业对任意种类的资源需求量均不大于该资源供给上限; 式(9)表示任意场景下任意作业一旦开始不能中断; 式(10)表示任意场景下任意作业的物料开始配送时间不应早于物料到达时间; 式(11)表示任意场景下任意JD和JP类作业的物料开始配送时间不应早于干扰发生时刻; 式(12)表示决策变量xjt, θ的可行域。
2 算法设计 依据模型的决策逻辑, 本文设计了以两阶段禁忌搜索算法为框架的启发式算法(Two-stage Tabu Search Based Heuristic, TTSBH), 其中解码算法采用了基于局部前瞻搜索的串行调度机制。算法设计思路如下:TTSBH算法分2层嵌套运用禁忌搜索算法, 依次搜索JD类作业的固定决策和不同场景下JP类作业的预测决策。具体而言, 对于搜索到的每一个固定决策结果(即JD类作业的调度结果), 进一步地, 在该固定决策结果基础上, 重复搜索不同场景θ(θ∈Θ)下JP类作业的预测决策结果, 通过计算目标函数值, 来反馈评估该固定决策结果的优劣。TTSBH算法采用作业列表进行编码, 编码顺序代表作业的调度顺序。依据3类作业的决策属性, 对编码进行拆分, 如图 5所示。其中, 对于JF类作业的固定编码按照实际执行顺序升序排列, 每经过一次滚动决策都将进行更新; 对应JD类作业的固定决策编码, 其初始列表(记为L1)按模板装配计划开始时间升序排列; 对应JP类作业的预测决策编码, 其初始列表(记为L2)按模板装配计划中的开始时间升序排列。TTSBH算法框架及流程如图 6所示。
 |
| 图 5 作业列表编码拆分示意图 Fig. 5 Schematic diagram of job list coding splitting |
| 图选项 |
 |
| 图 6 TTSBH算法流程 Fig. 6 Flowchart of TTSBH algorithm |
| 图选项 |
2.1 第一阶段禁忌搜索TS1 第一阶段禁忌搜索TS1为JD类作业搜索固定决策。对候选编码个体L1indiv, 任取2个作业进行位置互换, 生成邻域个体LD。由于作业间存在优先级关系, 该方式可能生成不可行的作业列表, 由此本文针对邻域个体生成方式进行如下改进:
步骤1??已知候选编码个体L1indiv={j1M, j2M, …, jmM}, 任意选取2个不同作业jfM和jgM(1≤f＜g≤m)。
步骤2??交换jfM和jgM, 令jfD←jgM, jgD←jfM, 得到待判定个体LD={j1D, j2D, …, jmD}。
步骤3??若存在u∈{f, f+1, …, g}, 使得
重复上述过程, 构建邻域集合N(L1indiv)。禁忌对象为最近若干次迭代的作业互换操作, 禁忌表长度为TL-1, 禁忌对象遵守先进先出原则, 迭代次数为Iter-1。对搜索到的每一个作业列表, 调用TS2算法模块进行评估。
2.2 第二阶段禁忌搜索TS2 第二阶段禁忌搜索TS2为JP类作业搜索不同场景下的预测决策。禁忌搜索的邻域生成方式、禁忌对象设置与TS1相同, 禁忌表长度为TL-2, 迭代次数为Iter-2。在获取TS1中待评估作业列表基础上, 对搜索到的每一个作业列表, 采用基于局部前瞻搜索的串行调度机制进行解码, 得到当前场景下的调度结果。需要注意, 在各个场景下重复进行禁忌搜索寻优过程中, 对JP类作业的决策结果均补充自同一个固定决策。
2.3 基于局部前瞻搜索的串行调度机制 结合目标函数中所考虑的优化指标, 本文设计了基于局部前瞻搜索的串行调度机制对作业列表进行解码, 算法具体步骤如下:
步骤1??获取场景θ所对应的作业物料到达时间序列(A1, θ, A2, θ, …, An, θ), 合并2个决策阶段的作业列表, 得到作业数量为I的调度序列{j1, j2, …, jI}, 令i=1。
步骤2??选取作业ji, 将其紧前作业的最晚完成时间max{sj+pj, j∈Pji}作为拟安排开始时间Tji。
步骤3??若Tji≥max(Tq+d, Aji, θ+d), 转步骤4, 否则令Tji=max(Tq+d, Aji, θ+d), 转步骤4。
步骤4??若?t∈[Tji, Tji+pji], ?k∈K, rjik≤Rk恒成立, 转步骤6, 否则转步骤5。
步骤5??Tji=Tji+1, 转步骤4。
步骤6??若Tji>s0ji, sj=Tji, 转步骤10, 否则令待决策值v=Tji, 待决策值集合Ωji=?, 转步骤7。
步骤7??若作业ji的开始时间安排为v时, 且?t∈[v, v+pji], ?k∈K, rjik≤Rk恒成立, 则Ωji=Ωji∪ v, 转步骤8, 否则直接转步骤8。
步骤8??若v＜s0ji, v=v+1, 转步骤7, 否则转步骤9。
步骤9??对Ωji中的待决策值进行局部前瞻搜索。依次将待决策值安排为作业开始时间, 将后续作业按照尽早开始原则进行预解码。对预解码后得到的局部调度计划, 计算其与模板装配计划的偏差及工期的加权和, 作为待决策值的适应度。取最小适应度所对应的待决策值作为作业的最佳开始时间sji, 转步骤10。
步骤10??若i < I, 令i=i+1, 转步骤2, 否则输出决策结果。
为了更好地说明基于局部前瞻搜索的串行调度机制, 以图 5中作业列表编码为例, 依次决策作业3、4、5、6的开始时间, 解码过程如图 7所示。对于作业3, 其待决策值仅为5, 直接决策作业3的开始时间为5;对于作业4, 其待决策值集合为{7, 8, 9, 10}, 对每个待决策值进行局部前瞻搜索, 计算其所生成局部调度计划的适应度, 将其中最小适应度所对应的待决策值9作为作业4的最佳开始时间; 作业5、6的解码方式与作业4相同, 不再赘述。依次解码作业列表, 直至确定完全部作业的开始时间。
 |
| 图 7 解码过程示例 Fig. 7 An example of decoding process |
| 图选项 |
3 数值实验 以文献[16]中模板装配计划实例为参考, 结合所研究问题的特点, 进行算例扩充, 构造作业数量为20、30、60、90、120等5类规模的数据, 分别生成10组算例。取ω1=0.5, ω2=0.5。设置物料配送提前期为10。假设受干扰作业占作业数量的10%。其余作业的物料到达时间均已知, 且与物料计划配送时间的偏差值在[10,20]内随机选取。受干扰作业的物料实际延期时间在区间[20,30]内随机选取。将进度时间距离作业模板开始时间的差值记为λ, 在λ所在的不同范围(λ>90, 50＜λ≤90, 10＜λ≤50), 其预估的物料到达时间与实际到达时间的偏差分别服从正态分布N(0, 2), N(0, 1), N(0, 0.5)。在每个滚动决策点设置场景池, 大小为2 000, TS2从中抽取30个场景作为物料到达场景集合。实验通过MATLAB(2014b)平台进行, 计算机配置为Intel i7-4790U处理器, 3.6 GHz主频, 8 GB内存。获取后验精确解使用的CPLEX软件版本号为12.6.3。以作业规模为120的10个算例作为预实验对象, 确定TTSBH算法所用的参数: Iter-1为10, TL-1为4, Iter-2为2, TL-2为1。选取其中一个算例的测试结果, 给出TTSBH算法的收敛曲线, 如图 8所示。
 |
| 图 8 TTSBH算法收敛曲线 Fig. 8 Convergence curve of TTSBH algorithm |
| 图选项 |
3.1 与CPLEX后验求解结果对比 为了验证TTSBH算法的精确性及解码算法的有效性, 本节利用后验信息(即所有作业的物料实际到达时间提前已知), 设计了如下对比实验:
1) 实验1。使用CPLEX软件单次求解数学模型。
2) 实验2。采用简化的动态调度框架和TTSBH算法(固定决策阶段的作业为前两次干扰发生时刻之间的作业, 后续作业利用后验信息进行预测决策), 单次求解数学模型。
3) 实验3。设计类似实验2, 但两阶段禁忌搜索算法中的解码算法采用传统的串行调度机制(SSGS), 该机制将作业开始时间安排为最早可开始时间。将该实验的算法命名为基于串行调度机制的两阶段禁忌搜索算法, 简记为TTS-SSGS。
由于CPLEX不适用于求解大规模算例, 表 3给出作业规模V为20、30、60各10组不同算例的求解结果, 其中Z为目标函数值, t为求解时间, G为其他算法得到的Z值与CPLEX求解结果的差值百分比, 带“*”的算例编号表示该算例在使用CPLEX求解时仅能获得3 h内所得的最优低界值。
表 3 基于后验信息的实验结果 Table 3 Experiment results based on posterior information
| V | 算例 | 实验1 | 实验2 | 实验3 | |||||||
| Z | t/min | Z | t/min | G | Z | t/min | G | ||||
| 20 | 1 | 260.0 | 0 | 260.0 | 0.1 | 0 | 287.0 | 0.1 | 10.4 | ||
| 2 | 304.5 | 0.1 | 304.5 | 0 | 0 | 304.5 | 0 | 0 | |||
| 3 | 300.0 | 0 | 300.0 | 0.1 | 0 | 304.5 | 0 | 1.5 | |||
| 4 | 242.0 | 0 | 245.0 | 0.1 | 1.2 | 261.5 | 0 | 8.1 | |||
| 5 | 281.0 | 0 | 281.0 | 0.1 | 0 | 287.0 | 0.1 | 2.1 | |||
| 6 | 264.5 | 0.1 | 264.5 | 0.1 | 0 | 267.0 | 0 | 0.9 | |||
| 7 | 328.0 | 0 | 356.0 | 0.1 | 8.5 | 356.5 | 0.1 | 8.7 | |||
| 8 | 358.5 | 0.3 | 358.5 | 0.1 | 0 | 360.0 | 0 | 0.4 | |||
| 9 | 232.0 | 0.1 | 232.0 | 0.1 | 0 | 243.0 | 0.1 | 4.7 | |||
| 10 | 346.5 | 0.4 | 362.0 | 0.1 | 4.5 | 370.5 | 0.1 | 6.9 | |||
| 均值 | 291.7 | 0.1 | 296.4 | 0.1 | 1.4 | 304.2 | 0.1 | 4.4 | |||
| 30 | 1 | 315.5 | 0.6 | 315.5 | 0.2 | 0 | 315.5 | 0.2 | 0 | ||
| 2 | 262.5 | 0.7 | 300.0 | 0.2 | 14.3 | 300.0 | 0.1 | 14.3 | |||
| 3 | 344.0 | 0.6 | 369.5 | 0.3 | 7.4 | 369.5 | 0.2 | 7.4 | |||
| 4 | 353.5 | 0.6 | 353.5 | 0.1 | 0 | 353.5 | 0.1 | 0 | |||
| 5 | 250.5 | 0.9 | 250.5 | 0.4 | 0 | 250.5 | 0.2 | 0 | |||
| 6 | 249.0 | 0.7 | 256.0 | 0.3 | 2.8 | 256.0 | 0.3 | 2.8 | |||
| 7 | 398.5 | 1.4 | 398.5 | 0.8 | 0 | 406.0 | 0.6 | 1.9 | |||
| 8 | 261.0 | 0.7 | 261.0 | 0.4 | 0 | 261.0 | 0.1 | 0 | |||
| 9 | 448.5 | 1.8 | 448.5 | 0.6 | 0 | 448.5 | 0.4 | 0 | |||
| 10 | 383.0 | 1.1 | 394.5 | 0.5 | 3.0 | 416.5 | 0.3 | 8.7 | |||
| 均值 | 326.6 | 0.9 | 334.8 | 0.4 | 2.8 | 337.7 | 0.3 | 3.5 | |||
| 60 | 1 | 543.5 | 126 | 543.5 | 4.6 | 0 | 544.0 | 3.3 | 0.1 | ||
| 2 | 538.5 | 42 | 541.0 | 3.8 | 0.5 | 541.0 | 2.9 | 0.5 | |||
| 3 | 815.0 | 137 | 848.0 | 4.7 | 4.0 | 903.5 | 3.3 | 10.9 | |||
| 4 | 667.5 | 92 | 667.5 | 3.5 | 0 | 682.0 | 2.1 | 2.2 | |||
| 5* | 803.5 | 180 | 803.5 | 4.6 | 0 | 835.0 | 3.4 | 3.9 | |||
| 6 | 547.0 | 38 | 552.0 | 3.1 | 0.9 | 567.0 | 2.9 | 3.7 | |||
| 7 | 440.5 | 30 | 458.0 | 3.7 | 4.0 | 458.0 | 2.8 | 4.0 | |||
| 8* | 665.5 | 180 | 750.0 | 3.0 | 12.7 | 756.0 | 2.8 | 13.6 | |||
| 9 | 506.0 | 142 | 506.0 | 4.7 | 0 | 522.0 | 4.1 | 3.2 | |||
| 10 | 587.0 | 83 | 618.5 | 3.7 | 5.4 | 618.5 | 2.4 | 5.4 | |||
| 均值 | 611.4 | 105 | 628.8 | 3.9 | 2.8 | 642.7 | 3.0 | 4.8 | |||
表选项
通过与CPLEX实验对比可以发现, TTSBH算法在各个规模算例中均能获得较优解, 且在部分算例中获得了精确解。在各个作业规模下, 与CPLEX求解结果的G均值分别为1.4%、2.8%和2.8%, 证明了TTSBH算法的有效性。随着作业规模增加, CPLEX求解所需时间迅速上升, 在作业规模为60下, 平均时间达到了105 min, 部分算例甚至无法在可接受时间得到理想低界。而TTSBH算法不仅能在较短时间内得到优质解, 且求解时间稳定, 说明TTSBH算法在求解时间上也具有较大优势。TTS-SSGS算法虽然在求解时间方面略优于TTSBH算法, 但求解结果在各作业规模下的G均值分别达到4.4%、3.5%和4.8%, 其求解质量劣于TTSBH算法, 表明基于局部前瞻搜索的串行调度机制相比于传统SSGS具有一定优势, 解码效果更优。
3.2 物料供应干扰环境下的对比实验 为了验证本文动态调度方法的求解效果, 本节设计了物料供应干扰环境下的对比实验:
1) 实验4。采用本文的动态调度框架和TTSBH算法, 滚动求解数学模型。
2) 实验5。以各个概率分布的期望值构建期望场景, 预测决策阶段仅利用期望场景下的预测决策结果对固定决策阶段决策进行评价, 滚动求解数学模型。
3) 实验6。采用单阶段决策方法, 即仅进行固定决策, 并利用TTSBH中的TS1算法和解码算法滚动求解简化后的数学模型。
4) 实验7。采用典型的右移策略(Right Shift, RS), 滚动应对执行过程中发生的物料延期干扰。
5) 实验8。采用文献[18]中的前摄-反应决策框架, 即在计划执行前预先考虑已知的物料到达时间概率分布, 在原始模板装配计划的基础上使用该文献中基于代理目标评价的自适应遗传算法建立前摄性计划, 反应阶段使用右移策略应对实际发生的延期干扰。其中, 代理目标函数考虑前摄计划的工期(即质量鲁棒性指标)和文献[18]采用的松弛时间代理指标2项指标, 松弛时间为作业在不影响后续作业情况下可推迟执行的最大时间, 自适应遗传算法的编码、种群初始化、交叉、变异、选择等操作均借鉴文献[4]中的方法, 并采用传统的串行调度机制对作业列表解码。
采用3.1节中的CPLEX求解结果作为对比基准。由于CPLEX在作业规模为60时已出现部分算例无法在可接受时间内求解, 因此作业规模为90和120的算例不再进行实验1的求解。实验2是采用后验信息进行求解的, 由表 3可知其与CPLEX所求解足够接近, 因此在更大规模下采用实验2的算法结果作为后验对比基准。表 4和表 5分别给出规模为20、30、60和规模为90、120的求解结果, Z值为滚动求解后的实际执行计划与模板装配计划偏差与实际工期的加权和, GAP1为本文方法的Z值与后验结果的差值百分比, GAP2、GAP3、GAP4和GAP5分别为其他方法与本文方法的Z值差值百分比。
表 4 小规模算例实验结果 Table 4 Experiment results of small-scale example
| V | 算例 | 实验4 | 实验5 | 实验6 | 实验7 | 实验8 | |||||||||
| Z | GAP1 | Z | GAP2 | Z | GAP3 | Z | GAP4 | Z | GAP5 | ||||||
| 20 | 1 | 260.0 | 0 | 260.0 | 0 | 260.0 | 0 | 307.5 | 18.3 | 265.0 | 1.9 | ||||
| 2 | 309.5 | 1.6 | 310.5 | 0.3 | 310.5 | 0.3 | 358.5 | 15.8 | 313.5 | 1.3 | |||||
| 3 | 300.0 | 0 | 300.5 | 0.2 | 304.5 | 1.5 | 363.5 | 21.2 | 324.5 | 8.2 | |||||
| 4 | 262.0 | 8.3 | 262.0 | 0 | 266.5 | 1.7 | 356.5 | 36.1 | 271.5 | 3.6 | |||||
| 5 | 281.0 | 0 | 284.0 | 1.1 | 281.0 | 0 | 357.0 | 27.0 | 299.0 | 6.4 | |||||
| 6 | 271.0 | 2.5 | 275.5 | 1.7 | 268.5 | -0.9 | 390.0 | 43.9 | 285.5 | 5.4 | |||||
| 7 | 356.0 | 8.5 | 361.0 | 1.4 | 356.0 | 0 | 369.5 | 3.8 | 368.0 | 3.4 | |||||
| 8 | 366.5 | 2.2 | 366.5 | 0 | 364.5 | -0.5 | 419.0 | 14.3 | 378.5 | 3.3 | |||||
| 9 | 234.5 | 1.1 | 234.5 | 0 | 241.5 | 3.0 | 356.0 | 51.8 | 243.0 | 3.6 | |||||
| 10 | 364.0 | 5.1 | 365.0 | 0.3 | 370.0 | 1.6 | 392.5 | 7.8 | 370.0 | 1.6 | |||||
| 均值 | 300.5 | 2.9 | 302.0 | 0.5 | 302.3 | 0.7 | 367.0 | 24.0 | 311.9 | 3.9 | |||||
| 30 | 1 | 315.5 | 0 | 319.0 | 1.1 | 315.5 | 0 | 317.5 | 0.6 | 315.5 | 0 | ||||
| 2 | 302.5 | 15.2 | 303.5 | 0.3 | 307.5 | 1.7 | 331.0 | 9.4 | 323.0 | 6.8 | |||||
| 3 | 369.5 | 7.4 | 370.0 | 0.1 | 369.5 | 0 | 378.5 | 2.4 | 370.0 | 0 | |||||
| 4 | 353.5 | 0 | 355.0 | 0.4 | 356.5 | 0.8 | 353.5 | 0 | 358.5 | 1.4 | |||||
| 5 | 259.0 | 3.4 | 260.5 | 0.6 | 260.5 | 0.6 | 314.5 | 21.4 | 279.5 | 7.9 | |||||
| 6 | 257.5 | 3.4 | 260.0 | 1.0 | 256.0 | -0.6 | 268.0 | 4.1 | 264.0 | 2.5 | |||||
| 7 | 402.5 | 1.0 | 405.0 | 0.6 | 407.0 | 1.1 | 418.5 | 4.0 | 410.5 | 2.0 | |||||
| 8 | 261.0 | 0 | 261.0 | 0 | 261.0 | 0 | 261.0 | 0 | 261.0 | 0 | |||||
| 9 | 448.5 | 0 | 451.0 | 0.6 | 457.5 | 2.0 | 487.5 | 8.7 | 467.5 | 4.2 | |||||
| 10 | 401.5 | 4.8 | 408.5 | 1.7 | 420.0 | 4.6 | 483.5 | 20.4 | 442.5 | 10.2 | |||||
| 均值 | 337.1 | 3.5 | 339.4 | 0.6 | 341.1 | 1.0 | 361.4 | 7.1 | 349.2 | 3.5 | |||||
| 60 | 1 | 543.5 | 0 | 548.0 | 0.9 | 549.5 | 1.1 | 558.0 | 2.8 | 555.5 | 2.2 | ||||
| 2 | 542.5 | 0.7 | 547.5 | 0.9 | 538.5 | -0.7 | 547.0 | 0.8 | 546.5 | 0.7 | |||||
| 3 | 852.5 | 4.6 | 875.5 | 2.7 | 913.5 | 7.3 | 974.5 | 14.3 | 941.0 | 10.4 | |||||
| 4 | 674.5 | 1.0 | 678.0 | 0.5 | 676.5 | 0.3 | 780.5 | 15.7 | 702.0 | 4.1 | |||||
| 5* | 810.5 | 0.9 | 824.5 | 1.7 | 824.5 | 1.7 | 827.5 | 2.1 | 827.0 | 2.0 | |||||
| 6 | 558.0 | 2.0 | 565.5 | 1.3 | 552.0 | -1.1 | 633.0 | 13.4 | 573.5 | 2.8 | |||||
| 7 | 465.5 | 5.7 | 472.5 | 1.5 | 504.5 | 8.4 | 522.0 | 12.1 | 495.5 | 6.4 | |||||
| 8* | 722.5 | 8.6 | 730.0 | 1.0 | 750.0 | 3.8 | 857.5 | 18.7 | 765.5 | 6.0 | |||||
| 9 | 511.0 | 1.0 | 515.0 | 0.8 | 548.5 | 7.3 | 548.5 | 7.3 | 529.0 | 3.5 | |||||
| 10 | 622.5 | 6.0 | 631.5 | 1.4 | 635.5 | 2.1 | 631.5 | 1.4 | 632.5 | 1.6 | |||||
| 均值 | 630.3 | 3.1 | 638.8 | 1.3 | 649.3 | 3.0 | 688.0 | 8.9 | 656.8 | 4.0 | |||||
表选项
表 5 大规模算例实验结果 Table 5 Experiment results of large-scale example
| V | 算例 | 后验结果 | 实验4 | 实验5 | 实验6 | 实验7 | 实验8 | ||||||||||
| Z | Z | GAP1 | Z | GAP2 | Z | GAP3 | Z | GAP4 | Z | GAP5 | |||||||
| 90 | 1 | 652.5 | 668.5 | 2.5 | 702.5 | 5.1 | 802.5 | 20.0 | 859.5 | 28.6 | 739.0 | 10.5 | |||||
| 2 | 654.0 | 674.5 | 3.1 | 691.5 | 2.5 | 918.0 | 36.1 | 962.5 | 42.7 | 849.5 | 25.9 | ||||||
| 3 | 918.0 | 930.0 | 1.3 | 949.0 | 2.0 | 1 155.5 | 24.2 | 1 016.5 | 9.3 | 1 005.0 | 8.1 | ||||||
| 4 | 891.0 | 921.0 | 3.4 | 965.0 | 4.8 | 1 162.5 | 26.2 | 1 104.5 | 19.9 | 993.5 | 7.9 | ||||||
| 5 | 702.5 | 774.0 | 10.2 | 796.5 | 2.9 | 952.5 | 23.1 | 962.5 | 24.4 | 871.5 | 12.6 | ||||||
| 6 | 776.5 | 808.0 | 4.1 | 814.5 | 0.8 | 776.5 | -3.9 | 914.0 | 13.1 | 867.5 | 7.4 | ||||||
| 7 | 652.5 | 715.0 | 9.6 | 715.0 | 0 | 728.0 | 1.8 | 864.0 | 20.8 | 782.5 | 9.4 | ||||||
| 8 | 823.5 | 843.5 | 2.4 | 850.5 | 0.8 | 843.5 | 0 | 1 281.0 | 51.9 | 922.5 | 9.4 | ||||||
| 9 | 988.0 | 1 002.0 | 1.4 | 1 032.5 | 3.0 | 1 063.0 | 6.1 | 1 071.0 | 6.9 | 1 071.0 | 6.9 | ||||||
| 10 | 946.0 | 959.0 | 1.4 | 967.5 | 0.9 | 974.0 | 1.6 | 1 124.0 | 17.2 | 1 008.5 | 5.2 | ||||||
| 均值 | 800.5 | 829.6 | 3.9 | 848.5 | 2.3 | 937.6 | 13.5 | 1 016.0 | 23.5 | 911.1 | 10.3 | ||||||
| 120 | 1 | 1 224.5 | 1 269.5 | 3.7 | 1 335.5 | 5.2 | 1 582.5 | 24.7 | 1 684.0 | 32.7 | 1 405.5 | 10.7 | |||||
| 2 | 1 239.5 | 1 279.0 | 3.2 | 1 343.0 | 5.0 | 1 520.5 | 18.9 | 1 678.0 | 31.2 | 1 414.5 | 10.6 | ||||||
| 3 | 1 228.0 | 1 275.0 | 3.8 | 1 339.5 | 5.1 | 2 283.0 | 79.1 | 1 626.0 | 27.5 | 1 471.0 | 15.4 | ||||||
| 4 | 1 247.0 | 1 314.0 | 5.4 | 1 374.0 | 4.6 | 1 380.0 | 5.0 | 1 548.0 | 17.8 | 1 445.0 | 10.0 | ||||||
| 5 | 1 035.5 | 1 057.5 | 2.1 | 1 134.0 | 7.2 | 1 691.5 | 60.0 | 1 476.0 | 39.6 | 1 267.0 | 19.8 | ||||||
| 6 | 1 086.5 | 1 208.0 | 11.2 | 1 263.5 | 4.6 | 1 281.0 | 6.0 | 1 743.0 | 44.3 | 1 363.5 | 12.9 | ||||||
| 7 | 855.0 | 904.5 | 5.8 | 945.0 | 4.5 | 1 117.5 | 23.5 | 1 395.0 | 54.2 | 1 073.5 | 18.7 | ||||||
| 8 | 965 | 968.0 | 0.3 | 983.0 | 1.5 | 1 003.0 | 3.6 | 1 003.5 | 3.7 | 1 003.0 | 3.6 | ||||||
| 9 | 1 282 | 1 370.5 | 6.9 | 1 413.0 | 3.1 | 1 433.5 | 4.6 | 1 735.5 | 26.6 | 1 510.5 | 10.2 | ||||||
| 10 | 1 270 | 1 302.0 | 2.5 | 1 392.5 | 7.0 | 1 539.0 | 18.2 | 1 756.5 | 34.9 | 1 496.5 | 14.9 | ||||||
| 均值 | 1 143.3 | 1 194.8 | 4.5 | 1 252.3 | 4.8 | 1 483.2 | 24.4 | 1 564.6 | 31.3 | 1 345.0 | 12.7 | ||||||
表选项
通过表 4和表 5可以发现, 在采用了本文方法的情况下, 各个作业规模的GAP1均值分别为2.9%、3.5%、3.1%、3.9%和4.5%, 且个别算例求解结果能获得精确解, 可见不同场景下的预测决策能有效辅助固定决策阶段作出更优的决策, 体现本文方法的后验优化能力。对比实验4和实验5, 不同作业规模下的GAP2均值为0.5%、0.6%、1.3%、2.3%和4.8%, 表明仅利用期望信息, 虽在小规模算例中达到了和本文方法相似的调度效果, 但随着规模不断增加, 其调度效果呈现越来越劣的趋势, 显示出随机场景信息在预测决策阶段的价值。对比实验4和实验6, 不同规模下的GAP3均值为0.7%、1.0%、3.0%、13.5%和24.4%, 表明随着算例规模增大, 单阶段决策方法的全局优化能力越来越差, 体现了本文方法中的固定决策在不同场景的预测决策评估影响下具备了较强的全局优化能力, 显示出本文的动态调度方法具有兼顾调度反应性和预见性的优势。对比实验4和实验7, 不同规模下的GAP4均值为24.0%、7.1%、8.9%、23.5%和31.3%, 显示出右移策略在应对干扰时的被动性, 体现了本文方法在应对物料延期干扰事件时所具有的明显优势, 也体现了充分利用物料到达场景信息的重要性。对比实验4和实验8, 不同作业规模下的GAP5均值为3.9%、3.5%、4.0%、10.3%和12.7%, 表明本文方法相比于现有的前摄-反应方法, 具有更优的调度效果。具体而言, 前摄-反应方法虽然能确保生成的前摄计划具有较强的鲁棒性, 但缺乏对不确定性信息更新的反馈, 易造成作业间松弛时间过大或不足的情况, 导致调度效果较差, 侧面体现了本文方法能充分利用不断更新的不确定性信息, 进而做出更有效的决策。
3.3 不同干扰程度影响下的方法性能对比 飞机装配在不同环境中会受到不同干扰程度的影响, 本节通过改变干扰发生次数(即干扰作业数量), 对本文方法的优化效果进行有效性验证。以作业规模为90的10组算例为测试对象, 将干扰发生次数从0逐渐增大到9, 记录不同方法下求得Z值, 结果如图 9所示。可知, 本文方法在不同干扰次数下得到的调度结果均优于其他方法, 且能够保持接近后验结果的求解性能。随着干扰次数增加, 本文方法与单阶段决策方法、RS方法、前摄-反应方法的求解效果差距越来越明显。与期望场景方法对比, 当干扰次数小于6时, 本文方法的求解优势较小, 当干扰次数达到6以上时, 求解优势开始呈现越来越明显的趋势。由分析可知, 本文方法在不同干扰程度影响下能获得较优的调度效果, 能较大程度降低物料供应干扰环境对飞机装配过程的影响。
 |
| 图 9 不同干扰次数下的方法性能对比 Fig. 9 Performance comparison of methods under different interference times |
| 图选项 |
3.4 不同目标权重比下的方法性能对比 上述实验均取ω1=0.5, ω2=0.5, 然而在实际生产调度中, 权重需根据企业实际需求确定。因此, 本节通过改变目标函数中2个子目标的权重比, 对本文方法的适应性进行测试。以作业规模为90的10组算例为测试对象, 将工期权重从0逐渐增大到1, 记录不同方法所求得的评价指标Z值及2类子目标指标的均值, 结果如图 10所示。可知, 随着工期权重的增加, 不同方法的Z值均逐渐降低。本文方法在不同权重比下得到的Z值均接近后验结果的Z值, 且随着工期权重增加, 越来越逼近后验结果, 表明动态调度方法具有良好的求解质量和适应性。当工期权重为1时, 不同方法求得的结果相差不大, 相比较于其他4种方法, 动态调度方法没有明显优势。在工期权重从0增大到1的过程中, 本文方法求得的结果均显著优于单阶段决策方法、RS方法和前摄-反应方法。从柱形图中可以看出, 不同工期权重下各个方法的工期目标值相差不大, 但在与模板装配计划的偏差值方面, 本文方法均能获得更优的求解结果, 表明该方法能较好地兼顾调度计划的稳定性和调度质量, 即本文提出的动态调度方法可适用于解决不同权重下的飞机装配反应调度问题。
 |
| 图 10 不同工期权重下的方法性能对比 Fig. 10 Performance comparison of methods under different duration weights |
| 图选项 |
3.5 应用案例 以某型号客机尾翼部分的装配工位为例,验证本文方法在实际应用中的可行性。该工位包含23项装配作业,其中作业1和作业23为虚作业,资源包括装配工人、关键装配设备、能源供应设备、线边存储空间4类,资源上限数量分别为[12,7,10,12], 物料配送提前期为5。模板装配计划如表 6所示。作业5、19、8为受物料供应干扰的作业, 其物料实际延期时间分别为28、31、30。在λ所在的不同范围(λ>75, 40＜λ≤75, 5＜λ≤40), 对干扰作业预估的物料到达时间与实际到达时间的偏差分别服从正态分布N(2, 2), N(1, 1), N(0, 0.5)。
表 6 尾翼装配工位模板装配计划 Table 6 Template assembly plan of tail assembly station
| 作业编号 | 开始时间 | 装配工时 | 物料计划到达时间 | 资源占用 | 紧后作业 |
| AO15001 | 0 | 0 | [0,0,0,0] | 2,3,4 | |
| AO15002 | 0 | 12 | 0 | [2,1,1,2] | 7,8 |
| AO15003 | 0 | 12 | 0 | [2,1,1,2] | 5,6,11 |
| AO15004 | 0 | 14 | 0 | [2,2,1,2] | 10 |
| AO15005 | 12 | 24 | 6 | [3,2,1,2] | 9 |
| AO15006 | 12 | 52 | 0 | [5,2,1,5] | 8 |
| AO15007 | 12 | 8 | 2 | [2,2,1,5] | 11,12 |
| AO15008 | 132 | 21 | 126 | [2,2,1,4] | 18 |
| AO15009 | 92 | 60 | 77 | [4,3,1,5] | 17 |
| AO15010 | 14 | 48 | 7 | [4,2,1,2] | 13 |
| AO15011 | 20 | 18 | 12 | [6,4,1,5] | 14,16,19 |
| AO15012 | 132 | 48 | 117 | [4,2,1,2] | 16,18 |
| AO15013 | 64 | 13 | 47 | [4,3,1,4] | 15 |
| AO15014 | 64 | 28 | 48 | [6,4,1,5] | 15 |
| AO15015 | 92 | 40 | 85 | [6,4,1,5] | 20 |
| AO15016 | 180 | 16 | 175 | [5,2,1,5] | 21 |
| AO15017 | 152 | 35 | 146 | [6,4,1,5] | 20 |
| AO15018 | 187 | 14 | 180 | [5,4,1,2] | 20 |
| AO15019 | 38 | 10 | 30 | [2,1,1,2] | 22 |
| AO15020 | 201 | 32 | 196 | [2,1,1,2] | 21,22 |
| AO15021 | 233 | 25 | 226 | [2,1,1,2] | 23 |
| AO15022 | 233 | 11 | 228 | [2,1,1,2] | 23 |
| AO15023 | 258 | 0 | [0,0,0,0] | ||
| 注:紧后作业一栏为简写, 如2表示作业编号为AO15002的作业。 | |||||
表选项
分别利用本文方法和前述对比方法求解该应用案例, 结合调度结果绘制甘特图, 如图 11~图 16所示。图中不同方法所求得的Z值(即实际执行计划与模板装配计划的偏差和实际工期的加权和)分别为280.5、284.5、310、307.5、339和309.5, 可见本文方法的求解结果与后验信息下的求解结果相差不大, 体现了其较强的后验优化能力。对比本文方法与其他方法的调度结果可以看出, 本文方法具有更优的求解效果。具体而言, 本文方法和其他方法所求得的实际工期分别为279、279、278、288和288, 实际执行计划与模板装配计划的偏差分别为290、341、337、390、331, 表明本文所提出的动态调度方法不仅能获得较短的工期, 还能使实际执行计划与模板装配计划之间的变动性更小, 兼顾了调度质量和调度计划执行的稳定性。结合实验结果和应用案例可知, 本文方法相比于现有方法, 具有更优的求解效果, 且在实际应用中具备可行性。
 |
| 图 11 后验求解调度结果(Z=280.5) Fig. 11 Scheduling results of posteriori solution(Z=280.5) |
| 图选项 |
 |
| 图 12 本文方法调度结果(Z=284.5) Fig. 12 Scheduling results of proposed method(Z=284.5) |
| 图选项 |
 |
| 图 13 单阶段决策方法调度结果(Z=310) Fig. 13 Scheduling results of single stage decision method(Z=310) |
| 图选项 |
 |
| 图 14 期望场景方法调度结果(Z=307.5) Fig. 14 Scheduling results of expectation scenario method(Z=307.5) |
| 图选项 |
 |
| 图 15 RS方法调度结果(Z=339) Fig. 15 Scheduling results of right shift method(Z=339) |
| 图选项 |
 |
| 图 16 前摄-反应方法调度结果(Z=309.5) Fig. 16 Scheduling results of proactive-reactive method(Z=309.5) |
| 图选项 |
4 结论 1) 以物料供应干扰环境下的飞机移动生产线装配作业调度问题为研究对象, 建立了动态调度框架, 将滚动决策点的调度决策划分为固定决策阶段和预测决策阶段, 并建立了二阶段近似优化模型。
2) 设计了以两阶段禁忌搜索为框架的启发式算法来求解二阶段近似优化模型, 算法中内嵌了基于局部前瞻搜索的串行调度机制。数值实验表明, 算法在求解质量方面具有良好的性能。
3) 物料供应干扰环境下的数值实验和应用案例表明, 预测决策阶段充分利用了最新获得的不确定性信息, 能有效辅助固定决策阶段做出更优的决策结果, 增强了调度决策的后验优化能力, 验证了动态调度方法的有效性和可行性。
后续研究将进一步考虑物料供应干扰环境下的飞机移动生产线周期性调度问题, 以完善飞机移动生产线的干扰管理方法。
参考文献
| [1] | LU H, LIU X, PANG W, et al. Modeling and simulation of aircraft assembly line based on quest[J]. Advanced Materials Research, 2012, 569: 666-669. DOI:10.4028/www.scientific.net/AMR.569.666 |
| [2] | 郑倩, 奚立峰. 飞机移动生产线作业调度问题的启发式算法[J]. 工业工程与管理, 2015, 20(2): 116-121. ZHENG Q, XI L F. Heuristics for aircraft moving assembly line scheduling problem[J]. Industrial Engineering & Management, 2015, 20(2): 116-121. DOI:10.3969/j.issn.1007-5429.2015.02.018 (in Chinese) |
| [3] | SHAN S, HU Z, LIU Z, et al. An adaptive genetic algorithm for demand-driven and resource-constrained project scheduling in aircraft assembly[J]. Information Technology and Management, 2017, 18(1): 41-53. |
| [4] | 胡鑫铭, 陆志强. 考虑物料配送的飞机移动生产线调度问题优化[J]. 北京航空航天大学学报, 2017, 44(12): 2573-2582. HU X M, LU Z Q. Optimization of aircraft moving assembly line scheduling problem considering material delivery[J]. Journal of Beijing University of Aeronautics and Astronautics, 2017, 44(12): 2573-2582. (in Chinese) |
| [5] | BANERJEE A G, YUND W, YANG D, et al.A hybrid statistical method for accurate prediction of supplier delivery times of aircraft engine parts[C]//Proceedings of the ASME 2015 International Design Engineering Technical Conferences & Computers and Information in Engineering Conference.New York: ASME, 2015: 286-295. |
| [6] | CHTOUROU H, HAOUARI M. A two-stage-priority-rule-based algorithm for robust resource-constrained project scheduling[J]. Computers & Industrial Engineering, 2008, 55(1): 183-194. |
| [7] | VAN DE VONDER S, DEMEULEMEESTER E, HERROELEN W. Proactive heuristic procedures for robust project scheduling:An experimental analysis[J]. European Journal of Operational Research, 2008, 189(3): 723-733. DOI:10.1016/j.ejor.2006.10.061 |
| [8] | CHAKRABORTTY R K, SARKER R A, ESSAM D L. Resource constrained project scheduling with uncertain activity durations[J]. Computers & Industrial Engineering, 2017, 112: 537-550. |
| [9] | BRUNI M E, DI PUGLIA PUGLIESE L, BERALDI P, et al. An adjustable robust optimization model for the resource-constrained project scheduling problem with uncertain activity durations[J]. Omega, 2016, 71: 66-84. |
| [10] | LAMBRECHTS O, DEMEULEMEESTER E, HERROELEN W. Proactive and reactive strategies for resource-constrained project scheduling with uncertain resource availabilities[J]. Journal of Scheduling, 2008, 11(2): 121-136. DOI:10.1007/s10951-007-0021-0 |
| [11] | MA Z Q, DEMEULEMEESTER E, HE Z W, et al. A computational experiment to explore better robustness measures for project scheduling under two types of uncertain environments[J]. Computers & Industrial Engineering, 2019, 131: 382-390. |
| [12] | VAN DE VONDER S, BALLESTíN F, DEMEULEMEESTER E, et al. Heuristic procedures for reactive project scheduling[J]. Computers & Industrial Engineering, 2007, 52(1): 11-28. |
| [13] | CHAKRABORTTY R K, SARKER R A, ESSAM D L. Single mode resource constrained project scheduling with unreliable resources[J]. Operational Research, 2018, 1: 1-35. |
| [14] | DAVARI M, DEMEULEMEESTER E. The proactive and reactive resource-constrained project scheduling problem[J]. Journal of Scheduling, 2019, 22(2): 211-237. DOI:10.1007/s10951-017-0553-x |
| [15] | CHAND S, SINGH H, RAY T. Evolving heuristics for the resource constrained project scheduling problem with dynamic resource disruptions[J]. Swarm and Evolutionary Computation, 2019, 44: 897-912. DOI:10.1016/j.swevo.2018.09.007 |
| [16] | 陆志强, 胡鑫铭, 朱宏伟. 物料供给不确定环境下的飞机移动生产线动态调度方法[J]. 同济大学学报(自然科学版), 2019, 47(5): 723-730. LU Z Q, HU X M, ZHU H W. Dynamic scheduling method for aircraft moving assembly line under uncertain supply of material[J]. Journal of Tongji University (Natural Science), 2019, 47(5): 723-730. (in Chinese) |
| [17] | ZHANG G M, SMILOWITZ K, ERERA A. Dynamic planning for urban drayage operations[J]. Transportation Research Part E:Logistics and Transportation Review, 2011, 47(5): 764-777. DOI:10.1016/j.tre.2011.02.003 |
| [18] | 韩笑乐, 许可, 陆志强. 集装箱码头泊位-堆场资源的鲁棒性模板决策[J]. 计算机集成制造系统, 2020, 26(3): 784-794. HAN X L, XU K, LU Z Q. Robust scheduling of berth and yard resource template in container terminal[J]. Computer Integrat-ed Manufacturing Systems, 2020, 26(3): 784-794. (in Chinese) |
