东北大学学报（自然科学版）

东北大学学报(自然科学版) ›› 2006, Vol. 27 ›› Issue (9): 961-964.DOI: -

• 论著 • 上一篇    下一篇

任务可拆分项目调度问题

雒兴刚;汪定伟;唐加福;   

  1. 东北大学计算中心;东北大学信息科学与工程学院;东北大学信息科学与工程学院 辽宁沈阳110004;东北大学信息科学与工程学院;辽宁沈阳110004;辽宁沈阳110004;辽宁沈阳110004
  • 收稿日期:2013-06-23 修回日期:2013-06-23 出版日期:2006-09-15 发布日期:2013-06-23
  • 通讯作者: Luo, X.-G.
  • 作者简介:-
  • 基金资助:
    国家自然科学基金资助项目(70431003)

Project scheduling problem involving time-splittable tasks

Luo, Xing-Gang (1); Wang, Ding-Wei (2); Tang, Jia-Fu (2)   

  1. (1) Computing Center, Northeastern University, Shenyang 110004, China; (2) School of Information Science and Engineering, Northeastern University, Shenyang 110004, China
  • Received:2013-06-23 Revised:2013-06-23 Online:2006-09-15 Published:2013-06-23
  • Contact: Luo, X.-G.
  • About author:-
  • Supported by:
    -

RichHTML

0

PDF (PC)

864

摘要： 经典资源受限的项目调度问题的前提之一是任务不可拆分,即每个任务只能被一次执行,中间不能停顿.但是在企业实际的项目调度中,许多任务是允许被拆分成若干次执行的.针对任务可拆分的项目调度问题提出了总项目工期最短的数学模型,该模型在任务较多、任务工期较长或时间粒度小时解空间很大,不利于精确求解.提出了一种结合邻域搜索方法的混合遗传算法求解该模型.给出了算法的编码方案、解码规则、适值函数、选择方法、交叉算子和变异算子的实现方法.最后通过算例验证了算法的有效性,列出了任务不能拆分和任务可拆分两种情况下算例最优解的甘特图.

关键词: 项目调度, 资源受限, 遗传算法, 可拆分任务, 邻域搜索

Abstract: One of the prerequisites for conventional resource constrained project scheduling problems is that the involved task is time-nonsplittable. But, not a few project scheduling problems in practice revealed that the execution time for an involved task is allowed to split into several parts, which are different from those problems not allowed to interrupt. A mathematic model is therefore developed for the project scheduling problem whose task is splittable to minimize all the time required for a project. However, the model is hard to solve exactly because of so big solution space when the time for the task is long, time slice is thin or there are many splitted parts of the task. So, a hybrid genetic algorithm in combination with neighborhood searching approach is designed to solve the model. The implementation of coding scheme, decoding rule, fitness function, the way to select, crossing operator and genetic operators of the algorithm are described. The effectiveness of the algorithm is verified by simulation results, by which the Gantt charts show the comparison between the cases of non-splittable tasks and splittable tasks.

中图分类号: