﻿ 考虑资源转移时间的资源受限项目调度问题的算法
 首页 关于本刊 编 委 会 期刊动态 作者中心 审者中心 读者中心 下载中心 联系我们 English
 自动化学报  2018, Vol. 44 Issue (6): 1028-1036 PDF

Algorithm for Resource-constrained Project Scheduling Problem With Resource Transfer Time
LU Zhi-Qiang, LIU Xin-Yi
School of Mechanical and Energy Engineering, Tongji University, Shanghai 201804
Manuscript received : December 23, 2016, accepted: April 7, 2017.
Foundation Item: Supported by National Natural Science Foundation of China (61473211, 71171130)
Corresponding author. LU Zhi-Qiang Professor at Tongji University. He received his Ph. D. degree from Universite De Nanets, France in 2003. His research interest covers logistics and supply chain management. Corresponding author of this paper
Recommended by Associate Editor WANG Hong-Wei
Abstract: Most studies in the literature so far assume that resources can be transferred from one job to the other without any expense of time. However, in many practical cases, it takes time for resources to transfer from one job to another. In this paper, we introduce the resource-constrained project scheduling problem (RCPSP) considering resource transfer time, which aims at minimizing the makespan of the project. A linear model is established and a branch-and-bound embedded genetic algorithm is proposed. A new precedence-based coding method which adapts to the structure of the problem is also proposed. Comparative computational results reveal that the branch-and-bound embedded genetic algorithm improves about 10% in terms of solution accuracy compared with the algorithm proposed in the literature.
Key words: Project scheduling     resource constraint     resource transfer time     branch-and-bound embedded genetic algorithm

1 问题描述及数学模型

 $\mbox{目标函数:}~~\min F_n$ (1)

 $\sum\limits_{t = 0}^{T-d_j} {f_{jt}}=1, ~~\forall{j\in J}$ (2)
 $F_j=\sum\limits_{t = 0}^{T-d_j} {{(t+d_j)}\times{f_{jt}}}, ~~\forall{j\in J}$ (3)
 $F_j-F_i\geq d_j, ~~\forall{j\in J}, ~\forall{i\in JP_j}$ (4)
 $F_i+\Delta_{ijk}+d_j\leq F_j+M\times(1-z_{ijk}), \\\quad\forall{j\in J}, ~\forall{i\in JP_j}, ~\forall{k\in K}$ (5)
 $x_{ijk}\leq z_{ijk}\times \min{\{r_{ik}, r_{jk}\}}, \\\qquad\qquad\qquad\ \forall{j\in J}, ~\forall{i\in JP_j}, ~\forall{k\in K}$ (6)
 $z_{ijk}\leq x_{ijk}, ~~\forall{j\in J}, ~\forall{i\in JP_j}, ~\forall{k\in K}$ (7)
 $\sum\limits_{i\in JP_j}{x_{ijk}}=r_{jk}, ~~\forall{j\in J}, ~\forall{k\in K}$ (8)
 $\sum\limits_{j\in JS_i}{x_{ijk}}=r_{ik}, ~~\forall{i\in J}, ~\forall{k\in K}$ (9)
 $\sum\limits_{j=1}^{n}{\sum\limits_{\tau=t}^{t+d_j}{r_{jk}\times f_{j\tau}}}\leq R_{k}, ~~\forall{t\in T}, ~\forall{k\in K}$ (10)
 $f_{jt}\in\{0, 1\}, ~z_{ijk}\in\{0, 1\}, ~x_{ijk}\geq0\nonumber\\ \qquad\qquad\qquad\ \ \forall{t\in T}, ~\forall{k\in K}, ~\forall{j\in J}, ~\forall{i\in J}$ (11)

$f_{jt}, z_{ijk}, x_{ijk}$是决策变量, 如果任务$j$在时刻$t$开始, $f_{jt}$为1, 否则为0;如果资源$k$从任务$i$转移至任务$j, z_{ijk}$为1, 否则为0; $x_{ijk}$为从任务$i$调配至任务$j$的资源$k$的数量.

 图 3 带资源转移时间的资源受限项目调度问题实例 Figure 3 An example of the RCPSPTT
2.1.2 交叉与变异

 图 4 交叉方式 Figure 4 An example of crossover

 图 5 变异方式 Figure 5 An example of mutation
2.1.3 启发式调度生成方法

2.2 分支定界算法

2.2.1 分支方法

 图 7 条件3示例图 Figure 7 An example of condition 3

 图 8 条件4示例图 Figure 8 An example of condition 4

 图 9 任务区分示例 Figure 9 An example of the classifications of the activities

 \begin{align} LB_g=EST_n \end{align} (12)

 \begin{align} EST_j=&\ \min\{\max\{F_i+\Delta_{ijk}| k\in K\}| i\in A\notag \\ &\ \mbox{且}~ \sum\limits_{i}x_{ijk}=r_{jk}\} \end{align} (13)

 图 10 任务关系示例 Figure 10 An example of the relationship of the activities

 \begin{align*} {EST_j=} \begin{cases} \max\{EFT_i+\Delta_{ijk}| i\in P_j^\ast \text{且} k\in K^\ast\}, \\ \qquad\qquad\ \hfill r_{ik}+r_{jk}> R_k \\ \max\{EFT_i| i\in P_j\}, \\ \qquad\hfill r_{ik}+r_{jk}\leq R_k \end{cases} \end{align*}
2.2.3 分支定界算法步骤

3 数据试验

3.1 遗传算法参数选取

3.2 与CPLEX的对比

3.3 与现有文献的对比

4 结论

 1 Brucker P, Knust S, Schoo A, Thiele O. A branch and bound algorithm for the resource-constrained project scheduling problem. European Journal of Operational Research, 1998, 107(2): 272-288. DOI:10.1016/S0377-2217(97)00335-4 2 Dorndorf U, Pesch E, Phan-Huy T. A branch-and-bound algorithm for the resource-constrained project scheduling problem. Mathematical Methods of Operations Research, 2000, 52(3): 413-439. DOI:10.1007/s001860000091 3 Klein R. Bidirectional planning:improving priority rule-based heuristics for scheduling resource-constrained projects. European Journal of Operational Research, 2000, 127(3): 619-638. DOI:10.1016/S0377-2217(99)00347-1 4 Buddhakulsomsiri J, Kim D S. Priority rule-based heuristic for multi-mode resource-constrained project scheduling problems with resource vacations and activity splitting. European Journal of Operational Research, 2007, 178(2): 374-390. DOI:10.1016/j.ejor.2006.02.010 5 Valls V, Ballestín F, Quintanilla S. A hybrid genetic algorithm for the resource-constrained project scheduling problem. European Journal of Operational Research, 2008, 185(2): 495-508. DOI:10.1016/j.ejor.2006.12.033 6 Peteghem V, Vanhoucke M. A genetic algorithm for the preemptive and non-preemptive multi-mode resource-constrained project scheduling problem. European Journal of Operational Research, 2010, 201(2): 409-418. DOI:10.1016/j.ejor.2009.03.034 7 Cho J, Kim Y. A simulated annealing algorithm for resource constrained project scheduling problems. Journal of the Operational Research Society, 1997, 48(7): 736-744. DOI:10.1057/palgrave.jors.2600416 8 Krüger D, Scholl A. A heuristic solution framework for the resource constrained (multi-)project scheduling problem with sequence-dependent transfer times. European Journal of Operational Research, 2009, 197(2): 492-508. DOI:10.1016/j.ejor.2008.07.036 9 Krüger D, Scholl A. Managing and modelling general resource transfers in (multi-)project scheduling. OR Spectrum, 2010, 32(2): 369-394. DOI:10.1007/s00291-008-0144-5 10 Zong Yan, Liu Qiong, Zhang Chao-Yong, Zhu Hai-Ping. Multi-project scheduling problem with resource transfer time. Computer Integrated Manufacturing Systems, 2011, 17(9): 1921-1928.( 宗砚, 刘琼, 张超勇, 朱海平. 考虑资源传递时间的多项目调度问题. 计算机集成制造系统, 2011, 17(9): 1921-1928.) 11 Kolisch R, Sprecher A. PSPLIB——A project scheduling problem library:OR Software-ORSEP Operations Research Software Exchange Program. European Journal of Operational Research, 1996, 96(1): 205-216.