上海交通大学学报

上海交通大学学报（自然版） ›› 2017, Vol. 51 ›› Issue (1): 82-.

• 能源与动力工程 • 上一篇    下一篇

作业时间依赖资源分配决策的项目调度问题建模与算法

  

  1. 同济大学 机械与能源工程学院， 上海 201804
  • 出版日期:2017-01-31 发布日期:2017-01-31

Modeling of and Algorithm for Resource Constrained Project Scheduling Problem with Resource  Allocation Dependent Processing Time

  1. School of Mechanical and Energy Engineering, Tongji University, Shanghai 201804, China
  • Online:2017-01-31 Published:2017-01-31

摘要：

摘要：  针对实际问题的需求，提出了作业时间依赖资源分配决策的项目调度问题.以最小化项目工期为目标，建立了作业时间与资源分配量呈函数关系的资源受限项目的调度模型，提出了基于1opt及2opt局部搜索的遗传算法以提高算法的求解质量，分析了2opt局部搜索中的作业组合情形，归纳与证明了不同作业组合调整与问题目标之间的关联性质，在此基础上建立了选取有效作业组合的方法，以提高算法在局部搜索求解中的效率.数据实验结果表明，所提算法相较于现有算法，其求解的质量和速度均具有优越性.

关键词: 项目调度, 作业时间, 可变, 资源分配, 2-opt局部搜索, 遗传算法

Abstract:

Abstract： In classical resourceconstrained project scheduling problems, the job processing times are assumed to be constant parameters. However, in many practical cases, the processing times depend on the resource allocated to the job. In this paper, the resourceconstrained project scheduling problem was introduced with resource allocation dependent processing time to minimize the duration of the project. A model was established and a genetic algorithm was proposed to solve the problem. To improve the ability of the algorithm, a 1opt based local search scheme and a 2opt based local search scheme were introduced.The related properties between different job combinations and the objective of the problem were summarized and proved. Based on these properties, the approach  for selecting effective job combinations was established, which greatly improved the efficiency of the algorithm in local search. Comparative computational results reveal that the algorithm proposed in this paper can solve the problem effectively.

Key words: project scheduling, processing time, controllable, resource allocation, 2opt local search, genetic algorithm

中图分类号: