·664· 智能系统学报 第17卷 2.1 RCPSP与PRCPSP sip,dp∈No,ieN;p=1,2,…,P4l (12) 目前，RCPSP充分应用于各场景。此外，非 其中：式(6)为目标函数；式(7)表示时刻0开始 抢占式RCPSP]以及抢占式PRCPSP(preemptive 维修：式(8)为时序约束，工序的完成后工序j开 resource-constrained project scheduling problem, 始；式(9)表示子工序的优先关系，子活动结束 PRCPSP)P的应用取决于：该工序可否暂停，占用 后开始；式(I0)表示工序工时等于子工序工时 的资源被另一工序使用。研究表明，抢占可高度 之和；式(11)表示工序资源限制；式(12)表示子 利用资源，减少闲置情况，从而减小工时。文献 工序开始时刻和工时为非负整数；拆分工序的子 [33]对离散PRCPSP问题，在整数时刻对工序进 工序p开始时间sp,工序工期dp 行抢占，并分为一次抢占和多次抢占。 2.2其他调度问题 1)RCPSP 1)目标函数 一个任务由n个工序i=1,2,…,n组成，给定任 经典的RCPSP数学模型是以工期最短为目 务维修时间范围[O,T],K种资源中资源k拥有量 标，但实际维修保障中，单一指标难以评价方案 R,工序需资源k数量r,工序对资源的需求不大 优劣，决策者常需考虑多个指标并进行权衡。 于该资源总量。工序i维修时间d:。虚拟工序 对于维修资源受限式维修工序调度问题，需 i=0和i=n+1表示任务的开始和结束，不占用维 要考虑的目标有以下几个： 修时间和资源。工序开始时间s,完成时间c,则 ①最小化项目工期： 3:+d,=c。假设工序不允许抢占。采用图G(WE) min s 表示任务网络，工序集合为V={0,1,…,n+1,弧集 该式最小化最后虚拟活动的开始时间，等价 合为E={,,jeVi→，表示工序是的紧前工 于最小化项目工期s。 序。工序i紧前工序集合pre()={j,)∈E,工序 ②最小化项目拖期： i的后继活动集合suc()={(i,)∈E}。RCPSP主要 min∑B,max0,f-D,l 约束有时序和资源约束，最小化任务完成时间 C=C}为优化目标B。 该式最小化活动加权拖期之和，其中活动拖 RCPSP概念性模型为 期严重程度B,活动实际完成时间f,计划交付时 mins (1) 间D。该目标适于有时间限制调度问题7。 S.t ③资源均衡： :+d,≤s,(i,)∈E (2) 之≤R,k=1,,K,t=l,T (3) ∑∑c} k=1=0 S0=0 (4) 该式最小化资源使用量平方加权和。时刻 siE int",i=1,…,n (5) t需资源k数量a=∑k,时刻t正在执行活动集合 其中：式(1)为目标函数；：式(2)为工序时序约束； V,={sp≤t≤sp+dp。资源均衡可确保资源利用 式(3)为资源约束；式(4)说明从时刻0开始维 稳定，是项目调度的重要目标。 修；式（⑤）限制工序开始时间为非负整数。 ④最小化资源可用量成本： 2)PRCPSP K 6 若允许抢占发生在整数时间点，则为离散抢 minc=∑ Ck·a+z k=1=0 占；若允许抢占发生在任意时间点，则称为连续 其中，活动中断成本z。该目标函数增加了活动抢 抢占。 占成本B PRCPSP概念性模型为 2)约束条件 s.t. mins (6) 对于工序调度，资源是非常重要的约束条件。 501=0 (7) 装备维修保障资源分为可更新资源、消耗性资源 S≥5P,+dP,(i,)∈A (8) 以及双重资源。 sp*1≥Sp+dp,i∈N;p=1,2,…,P (9) 1)可更新资源在每个时刻的供应链是有限 P d=dp,ieNP=l,2…,d (10) 的，并不随维修保障的进度而消耗，例如人力、设 =1 备等。可更新资源约束表示： ≤1=12Tk=12K (11) ∑ra≤R,k=1,2,,K,1=1,…,T2.1 RCPSP 与 PRCPSP 目前，RCPSP 充分应用于各场景。此外，非 抢占式 RCPSP[33] 以及抢占式 PRCPSP(preemptive resource-constrained project scheduling problem, PRCPSP)[28] 的应用取决于：该工序可否暂停，占用 的资源被另一工序使用。研究表明，抢占可高度 利用资源，减少闲置情况，从而减小工时。文献 [33] 对离散 PRCPSP 问题，在整数时刻对工序进 行抢占，并分为一次抢占和多次抢占。 1) RCPSP n i = 1,2,··· ,n [0,T] K k Rk i k riki di i = 0 i = n+1 i si ci si +di = ci G(V,E) V = {0,1,··· ,n+1} E = {(i, j)|i, j ∈ V,i → j} i j i pre(i) = {j|(j,i) ∈ E} i suc(i) = {j|(i, j) ∈ E} Cmax = max i∈V {Ci} 一个任务由 个工序 组成，给定任 务维修时间范围 ， 种资源中资源 拥有量 ，工序 需资源 数量 ，工序对资源的需求不大 于该资源总量。工序 维修时间 。虚拟工序 和 表示任务的开始和结束，不占用维 修时间和资源。工序 开始时间 ，完成时间 ，则 。假设工序不允许抢占。采用图 表示任务网络，工序集合为 ，弧集 合为 ，表示工序 是 的紧前工 序。工序 紧前工序集合 ，工序 的后继活动集合 。RCPSP 主要 约束有时序和资源约束，最小化任务完成时间 为优化目标[34]。 RCPSP 概念性模型为 minsn (1) s.t. si +di ⩽ sj , ∀(i, j) ∈ E (2) ∑ i∈A(t) rik ⩽ Rk , k = 1,··· ,K,t = 1,··· ,T (3) s0 = 0 (4) si ∈ int+ ,i = 1,··· ,n (5) 其中：式 (1) 为目标函数；式 (2) 为工序时序约束； 式 (3) 为资源约束；式 (4) 说明从时刻 0 开始维 修；式 (5) 限制工序开始时间为非负整数。 2) PRCPSP 若允许抢占发生在整数时间点，则为离散抢 占；若允许抢占发生在任意时间点，则称为连续 抢占。 PRCPSP 概念性模型为 minsn (6) s.t. s0,1 = 0 (7) sj,1 ⩾ si,Pi+1 +di,Pi+1 ,∀(i, j) ∈ A (8) si,p+1 ⩾ si,p +di,p,∀i ∈ N;p = 1,2,···,Pi (9) di = ∑Pi p=1 di,p ，∀i ∈ N;Pi = 1,2,··· ,d1 (10) ∑ i∈At rik ⩽ Rk ,t = 1,2,··· ,T; k = 1,2,··· ,K (11) si,p,di,p ∈ N0,∀i ∈ N;p = 1,2,···,Pi+1 (12) i j iip ip+1 i i p sip dip 其中：式 (6) 为目标函数；式 (7) 表示时刻 0 开始 维修；式 (8) 为时序约束，工序 的完成后工序 开 始；式 (9) 表示子工序的优先关系，子活动 结束 后 开始；式 (10) 表示工序 工时等于子工序工时 之和；式 (11) 表示工序资源限制；式 (12) 表示子 工序开始时刻和工时为非负整数；拆分工序 的子 工序 开始时间 ，工序工期 。 2.2 其他调度问题 1) 目标函数 经典的 RCPSP 数学模型是以工期最短为目 标，但实际维修保障中，单一指标难以评价方案 优劣，决策者常需考虑多个指标并进行权衡。 对于维修资源受限式维修工序调度问题，需 要考虑的目标有以下几个： ① 最小化项目工期： min sn 该式最小化最后虚拟活动的开始时间，等价 于最小化项目工期[35-36]。 ② 最小化项目拖期： min∑ i∈N βi max{0, fi − Di} i βi i fi Di 该式最小化活动加权拖期之和，其中活动 拖 期严重程度 ，活动 实际完成时间 ，计划交付时 间 。该目标适于有时间限制调度问题[37]。 ③ 资源均衡： min∑K k=1 ∑δ t=0 ck ·(ukt) 2 t k ukt = ∑ i∈Vt rik t Vt = {i|si,p ⩽ t ⩽ si,p +di,p} 该式最小化资源使用量平方加权和。时刻 需资源 数量 ，时刻 正在执行活动集合 。资源均衡可确保资源利用 稳定，是项目调度的重要目标[38]。 ④ 最小化资源可用量成本： minC = ∑K k=1 ∑δ t=0 ck · ukt +z 其中，活动中断成本 z 。该目标函数增加了活动抢 占成本[39]。 2) 约束条件 对于工序调度，资源是非常重要的约束条件。 装备维修保障资源分为可更新资源、消耗性资源 以及双重资源。 1) 可更新资源在每个时刻的供应链是有限 的，并不随维修保障的进度而消耗，例如人力、设 备等。可更新资源约束表示： ∑ i∈A(t) rik ⩽ Rk , k = 1,2,··· ,K,t = 1,··· ,T ·664· 智 能 系 统 学 报 第 17 卷