﻿ 带资源空窗期的资源投入型问题的建模与优化
 文章快速检索
 同济大学学报(自然科学版)  2019, Vol. 47 Issue (10): 1520-1527.  DOI: 10.11908/j.issn.0253-374x.2019.10.019 0

引用本文

LU Zhiqiang, ZHOU Haoxue. Modeling and Optimization of Resource Investment Problem with Resource Window[J]. Journal of Tongji University (Natural Science), 2019, 47(10): 1520-1527. DOI: 10.11908/j.issn.0253-374x.2019.10.019

文章历史

Modeling and Optimization of Resource Investment Problem with Resource Window
LU Zhiqiang , ZHOU Haoxue
School of Mechanical Engineering, Tongji University, Shanghai 201804, China
Abstract: Resource investment problem with resource window constraint was considered in the context of aircraft mobile assembly line. A mathematical model was proposed to solve the problem with the objective of the total cost minimization of resource. Firstly, based on the characteristics of the resource window constraint, a constructive heuristic algorithm with non-critical activity priority decision rules was developed to solve small-scale problems. Secondly, a genetic algorithm, which was coded by a double-linked list including non-critical activity priority and critical activity start time and decoded by non-critical activity priority decision rules, was proposed for the large-scale problems. Finally, numerical experiments were carried out to compare the advantages and disadvantages between heuristic algorithm, genetic algorithm and CPLEX, and the effectiveness of the two proposed algorithms was proved.
Key words: resource investment    resource window    heuristic algorithm    genetic algorithm

1 问题描述及数学模型 1.1 问题描述

1.2 空窗期

 图 1 资源空窗期示意图 Fig.1 Schematic diagram of resource window
1.3 数学模型

 $\min \sum\limits_{p = 1}^P {\left( {{C_p}\max \left( {{R_{tp}}} \right)} \right)}$ (1)

 ${R_{tp}} = \sum\limits_{j = 1}^J {{r_{jp}}} {x_{jt}}, t = 1, 2, \cdots , T, p = 1, 2, \cdots , P$ (2)
 $\sum\limits_{t = {t_{{\rm{ES}}, j}}}^{{t_{{\rm{LF}}, j}}} {{x_{jt}}} = {t_j}, j = 1, 2, \cdots , J$ (3)
 $t_{j} x_{j t} \leqslant \sum\limits_{k=1}^{t-1} x_{j^{*} k}, \quad \forall j^{*} \in p(j)$ (4)
 $\sum\limits_{m=1}^{M} z_{j m} t_{\mathrm{e}, m-1} \leqslant \sum\limits_{t=t_{\mathrm{EF}, j}}^{t_{\mathrm{LF}, j}} t x_{j t} \leqslant \sum\limits_{m=1}^{M} z_{j m} t_{\mathrm{b}, m}, j \in A_{\mathrm{e}}$ (5)
 $t_{j} x_{j t}-t_{j} x_{j(t+1)}+\sum\limits_{k=t+2}^{T} x_{j k} \leqslant t_{j}, j=1, 2, \cdots, J, t=1, 2, \cdots, T$ (6)
 $t x_{j t} \leqslant T, t=1, 2, \cdots, T$ (7)

2 启发式算法设计

2.1 第一阶段：生成非关键任务优先级列表

(1) 工期规则

(2) EST规则

2.2 第二阶段：关键任务排入方式的确定 2.2.1 相关关键任务j0*

 图 2 相关关键任务调整 Fig.2 Related critical activity adjustment
2.2.2 关键任务调整基准

2.3 第三阶段：非关键任务的调度决策 2.3.1 相关任务与相关距离dij

2.3.2 任务jJ开始时间tST, j可排区间点集

 $t_{\mathrm{ES}, j}^{\prime}=\max \left\{t_{\mathrm{ES}, j}, \max\limits_{i \in R_{\mathrm{e}}}\left(t_{\mathrm{ST}, i}+d_{i j}\right)\right\}, d_{i j}>0$ (8)
 $t_{\mathrm{LS}, j}^{\prime}=\min \left\{t_{\mathrm{LS}, j}, \min\limits_{i \in R_{\mathrm{e}}}\left(t_{\mathrm{ST}, i}+d_{i j}\right)\right\}, d_{i j}<0$ (9)

 $\sum\limits_{m = 1}^M {{t_{{\rm e}, m}}} \le \sum\limits_{t = {t_{{\rm{ST}}, j}}}^{{t_{{\rm{TF}}, j}}} t \le \sum\limits_{m = 1}^M {{t_{{\rm{b}}, m}}}$ (10)

 $S_{\text {move }, j}=\left\{t_{\mathrm{ST}, j 1}, t_{\mathrm{ST}, j 2}, \cdots, t_{\mathrm{ST}, j n}\right\}$ (11)
2.3.3 任务jJ开始时间tST, j可变区间点集

 $S_{\text {change }, j}=\left\{t_{\mathrm{ST}, j 1}^{\prime}, t_{\mathrm{ST}, j2}^{\prime}, \cdots, t_{\mathrm{ST}, j n}^{\prime}\right\}$ (12)

2.3.4 局部最优判断基准

3 遗传算法设计

3.1 编码

 图 3 编码示例 Fig.3 Coding example
3.2 遗传操作 3.2.1 初始种群

3.2.2 选择

 $f(s) = \sum\limits_{p = 1}^P {\left( {{C_p}\max {R_{tp}}} \right)}$ (13)
3.2.3 交叉

 图 4 交叉操作示例 Fig.4 Cross example

(1) 对非关键任务优先级的链表进行交叉操作.对染色体C2，选择与染色体C1x位置之前的基因不相同的基因链，与染色体C1x位置之后的基因段互换，生成新的染色体Sg；对染色体C1，同理生成新的染色体D.

(2) 对关键任务开始时间的链表进行交叉操作.对染色体C2，选择与染色体C1x位置之前的基因链，与染色体C1x位置之后的基因段互换，若互换后的开始时间点处在区间[tES, tLS]内，则直接互换；若互换后的开始时间点小于tES，则互换后的基因取值为tES；若互换后的开始时间点大于tLS，则互换后的基因取值为tLS；生成新的染色体Sg；对染色体C1，同理生成新的染色体D.

3.2.4 变异

(1) 对k=1, 2, …, b，在[1, b]之间随机产生两个数xy，交换xy两位置所对应的任务的优先级，生成新的列表.

(2) 对k=2, 3, …, a，在[2, a]之间随机产生一个数z，改变位置z所对应任务的开始时间，并重新生成位置z后序所有关键任务的开始时间.具体过程如图 5所示.

 图 5 变异操作示例 Fig.5 Variation example
3.3 解码

4 数值实验

 $g_{1}=\frac{H-C}{H} \times 100 \%$ (14)
 $g_{2}=\frac{G-C}{G} \times 100 \%$ (15)
 $g_{3}=\frac{H-G}{H} \times 100 \%$ (16)

5 总结与展望

 [1] MÖHRING R H. Minimizing costs of resource requirements in project networks subject to a fixed completion time[J]. Operations Research, 1984, 32(1): 89 DOI:10.1287/opre.32.1.89 [2] DREXL A, KIMMS A. Optimization guided lower and upper bounds for the resource investment problem[J]. Operational Research Society, 2001, 52(3): 340 [3] RODRIGUES S B, YAMASHITA D S. An exact algorithm for minimizing resource availability costs in project scheduling[J]. European Journal of Operational Research, 2010, 206(3): 562 DOI:10.1016/j.ejor.2010.03.008 [4] SONG Y, LIU J, WIMMERS M O, et al. A differential evolution algorithm with local search for resource investment project scheduling problems[C]//Evolutionary Computation. Sendai: IEEE, 2015: 1725-1731. [5] MYSZKOWSKI P B, SKOWROŃSKI M E, OLECH L P, et al. Hybrid ant colony optimization in solving multi-skill resource-constrained project scheduling problem[J]. Soft Computing, 2015, 19(12): 3599 DOI:10.1007/s00500-014-1455-x [6] VAN PETEGHEM V, VAN HOUCKE M. An artificial immune system algorithm for the resource availability cost problem[J]. Flexible Services and Manufacturing Journal, 2013, 25(1/2): 122 [7] HE L H, ZHANG L Y. Dynamic priority rule-based forward-backward heuristic algorithm for resource leveling problem in construction project[J]. Journal of the Operational Research Society, 2013, 64(8): 1106 DOI:10.1057/jors.2013.33 [8] QI J J, LIU Y J, JIANG P, et al. Schedule generation scheme for solving multi-mode resource availability cost problem by modified particle swarm optimization[J]. Journal of Scheduling, 2015, 18(3): 285 DOI:10.1007/s10951-014-0374-0 [9] 胡淑芳.考虑资源技能和时间窗特性的任务可拆分项目调度[D].武汉: 华中科技大学, 2012. HU Shufang. Preemptive project scheduling with resources of multi-skill and time-windows[D]. Wuhan: Huazhong University of Science and Technology, 2012. http://cdmd.cnki.com.cn/Article/CDMD-10487-1013012309.htm [10] 廖广瑞, 刘振元, 毕阳.多技能资源时间窗约束下项目调度研究[C]//中国控制与决策会议.长沙: 出版者不详, 2014: 4885-4891. LIAO Guangrui, LIU Zhenyuan, BI Yang. Project scheduling with time window constraints on multi-skill resources[C]//Chinese Control and Decision Conference. Changsha: [s.n.], 2014: 4885-4891. http://cpfd.cnki.com.cn/Article/CPFDTOTAL-KZJC201405001924.htm [11] 綦方中, 胡丹, 叶雷宏. 基于时间窗和关键链的多项目资源分配问题的研究[J]. 科技管理研究, 2013, 33(13): 229 QI Fangzhong, HU Dan, YE Leihong. Study on resource allocation of multi-project based on time window and critical chain[J]. Science and Technology Management Research, 2013, 33(13): 229 [12] 刘振元, 黄亚健. 资源多时间窗约束下的项目调度[J]. 系统工程, 2014(10): 126 LIU Zhenyuan, HUANG Yajian. Project scheduling with constraints of multiple time windows on resources[J]. Systems Engineering, 2014(10): 126 [13] 吴怡薇, 陆志强. 飞机移动装配线资源水平问题的建模研究[J]. 工业工程与管理, 2017, 22(1): 95 WU Yiwei, LU Zhiqiang. Modeling resource leveling for aircraft moving assembly line[J]. Industrial Engineering and Management, 2017, 22(1): 95