# 有竞争的多项目并行柔性协作计划与调度模型研究Research on a Model of Multi-Project Parallel Scheduling with Flexible Competitive Collaboration Planning

• 全文下载: PDF(1553KB)    PP.225-232   DOI: 10.12677/MSE.2018.74026
• 下载量: 160  浏览量: 620   科研立项经费支持

To solve the resource conflict in the process of implementation of the multi-project management, a model of multi-project parallel scheduling with flexible competitive collaboration planning in which tasks can be outsourced arbitrarily and be competed among multiple partners was proposed to minimize the total cost of the projects and the duration of each project. According to the characteristic of the problem, this paper designed an improved NSGA-II algorithm for the sched-uling model, including the three-dimensional chromosome encoding scheme to identify the at-tributes of collaboration ratio, partners and priorities. With the practice project confirmation, the practicality of this model and the validity of this algorithm are verified. The optimization method can effectively coordinate the resource allocation among projects and improve the efficiency of multi project management as well.

1. 引言

2. 模型建立

2.1. 问题描述

2.2. 目标函数

1) 项目总成本

$\text{V}=\underset{i=1}{\overset{N}{\sum }}\underset{j=1}{\overset{{J}_{i}}{\sum }}\left[\left(1-{x}_{ij}\right)\cdot {v}_{ij}+\underset{m=1}{\overset{{M}_{ij}}{\sum }}{v}_{ij}^{m}\cdot {x}_{ij}\cdot {\text{H}}_{ij}^{m}\right]$

${x}_{ij}=\left\{\begin{array}{l}0, {x}_{ij}\le 0.2\\ 1, \text{}\text{ }{x}_{ij}>0.8\end{array}$

2) 项目工期

${T}_{i}=\underset{i\in {C}_{i}}{\sum }\left[{t}_{ij}\cdot \left(1-{x}_{ij}\right)+\underset{m=1}{\overset{{M}_{ij}}{\sum }}{t}_{ij}^{m}\cdot {x}_{ij}\cdot {\text{H}}_{ij}^{m}\right]$

2.3. 约束条件

${S}_{ai}\ge {S}_{bj}+{T}_{bj}^{k},\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}{\phi }_{bj}\ge {\phi }_{ai}$

3. 算法设计

3.1. 编码方案

Figure 1. Three-dimensional chromosome encoding scheme

3.2. 交叉与变异操作

1) 协作染色体

$\lambda ={\text{e}}^{1-\frac{{G}_{m}}{{G}_{m}+1-G}},F={F}_{0}\cdot {2}^{\lambda }$ (1)

(2)

2) 协作伙伴染色体

3) 优先级染色体

3.3. 算法流程

1) 随机生成种群规模为 ${N}_{p}$ 的初始种群 ${P}_{0}$

2) 通过基于改进的拓扑排序的并行调度算法得到对应的目标函数值，再对初始种群按照支配等级和拥挤距离进行非支配排序；

3) 设当前进化代数为 $d=1$

4) 从父代种群中选择较优的子种群 ${Q}_{1}$

5) 基于差分进化算法对父代种进行交叉、变异操作，得到新种群 ${Q}_{2}$

6) 合并两个种群得到 $Q={Q}_{1}\cup {Q}_{2}$ ，对Q计算目标函数值并进行非支配排序(参照步骤2)，基于精英保留策略从中选择较优的 ${N}_{p}$ 个个体，得到子代种群 ${P}_{t}$

7) 令 $d=d+1$ ，如果 $d\le {G}_{\mathrm{max}}$ ，跳至步骤3；否则，进行步骤8；

8) 保存运行结果，输出Pareto最优解集，并根据决策者偏好输出对应调度计划的甘特图，算法终止。

4. 仿真结果分析

Figure 2. Multi-objective Pareto optimal solution set and Pareto optimal boundary surface

Figure 3. Multi-project scheduling Gantt chart

Table 1. Logical relation constraints, costs and cycles under complete homemade and outsourcing among the tasks of Project A

Table 2. Logical relation constraints, costs and cycles under complete homemade and outsourcing among the tasks of Project B

Table 3. Pareto partial optimal solution set of a model of multi-project parallel scheduling with flexible competitive collaboration planning

5. 结束语

Table 4. Pareto partial optimal solution set of a model of multi-project parallel scheduling with competitive collaboration planning

 [1] 黄健仓. 建设企业多项目管理中的资源调度问题研究[J]. 中国软科学, 2016(1): 176-183. [2] Vercellis, C. (1994) Constrained Multi-Project Planning Problems: A Lagrangean Decomposition Approach. European Journal of Operational Research, 78, 267-275. https://doi.org/10.1016/0377-2217(94)90389-1 [3] Harmann, S.A. (2002) Self-Adapting Genetic Algorithm for Project Scheduling under Resource Constraints. Naval Research, 49, 443-448. [4] AL-Fawzan, M.A. and Haouari, M.A. (2005) Bi-Objective Model for Robust Resource-Constrained Project Scheduling. International Journal of Operational Research, 96, 175-187. [5] 杨雪松, 胡昊. 基于关键链方法的多项目管理[J]. 工业工程与管理, 2005, 10(2): 52-56. [6] 寿涌毅. 多项目资源配置的拉格朗日分解方法[J]. 数量经济技术与经济研究, 2004, 21(8): 98-102. [7] 周永华, 陈禹六. 多项目环境下经营过程配置优化[J]. 计算机集成制造系统, 2003, 9(6): 436-443. [8] 马陈程. 多项目并行协作计划与调度的多目标优化模型[D]: [硕士学位论文]. 扬州: 扬州大学, 2018. [9] Deb, K., Pratap, A., Agarwal, S., et al. (2002) A Fast and Elitist Multi-Objective Genetic Algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6, 182-197. https://doi.org/10.1109/4235.996017 [10] 王樱, 徐雨明, 邹赛. 用信号量机制实现进程的同步与互斥[J]. 福建电脑, 2005(12): 15-16. [11] 刁训娣. 基于多目标遗传算法的项目调度及其仿真研究[D]: [博士学位论文]. 上海: 上海交通大学, 2010. [12] 张超勇, 董星, 等. 基于改进非支配排序遗传算法的多目标柔性作业车间调度[J]. 机械工程学报, 2010, 46(11): 156-164. [13] Hapke, M. and Jaszkiewicz, A. (2000) Pareto Simulated Annealing for Fuzzy Multi-Objective Combinatorial Optimization. Journal of Heuristics, 6, 329-345. https://doi.org/10.1023/A:1009678314795 [14] 曲志坚, 张先伟, 曹雁锋, 刘晓红, 冯晓华. 基于自适应机制的遗传算法研究[J]. 计算机应用研究, 2015, 32(11): 3222-3225 + 3229. [15] 刘波, 王凌, 金以慧. 差分进化算法研究进展[J]. 控制与决策, 2007, 22(7): 721-729. [16] 冯冬青, 王非, 马雁. 遗传算法中选择交叉策略的改进[J]. 计算机工程, 2008, 34(19): 189-192.