孙晓雅, 林焰. 任务可定点拆分的资源受限项目调度问题研究[J]. 微电子学与计算机, 2012, 29(7): 98-102.
引用本文: 孙晓雅, 林焰. 任务可定点拆分的资源受限项目调度问题研究[J]. 微电子学与计算机, 2012, 29(7): 98-102.
SUN Xiao-ya, LIN Yan. A Study on Resource-constrained Project Scheduling with Activities Splitable at Fixed Points[J]. Microelectronics & Computer, 2012, 29(7): 98-102.
Citation: SUN Xiao-ya, LIN Yan. A Study on Resource-constrained Project Scheduling with Activities Splitable at Fixed Points[J]. Microelectronics & Computer, 2012, 29(7): 98-102.

任务可定点拆分的资源受限项目调度问题研究

A Study on Resource-constrained Project Scheduling with Activities Splitable at Fixed Points

  • 摘要: 任务可定点拆分的资源受限项目调度问题是标准资源受限项目调度问题的一个扩展.针对这一问题提出了一种离散人工蜂群求解算法.离散人工蜂群算法中采用基于任务排列的食物源编码方式,并提出了能够一种保证解的可行性和离散型的候选食物源生成方法.项目中允许定点拆分的任务首先要转换为满足先序关系的分任务,然后在通过串行调度机制生成可行调度.实算表明,该算法能够有效求解任务可定点拆分的资源受限项目调度问题,同时也看到在不影响完成质量情况下,项目通过任务拆分能够在一定程度上缩短项目工期.

     

    Abstract: Resource-constrained project scheduling problem (RCPSP) with activities splitable at fixed points is an extension of the standard RCPSP.We provide a new discrete artificial bee colony (DABC) algorithm for this problem.In DABC each food source location represents a feasible permutation of the set of activities.We give a new method to produce candidate food sources which can keep the solution discrete and feasible.The activities allowed to split at fixed points should be changed into subtasks which meet the first and last relations, and then the feasible scheduling is generated through the serial scheduling scheme.The actual computation shows that this algorithm can solve RCPSP with activities splitable at fixed points effectively.We also see that the project makespan can be shorten in a certain extent by splitting activities without affecting its quality.

     

/

返回文章
返回