多技能资源时间窗约束下可中断项目调度的分支定界算法

Branch-and-bound based approach for preemptive project scheduling with time-window constraints on multi-skilled resources

资源的多技能和时间窗属性是软件开发、工程设计、设备维修等领域在人力资源调度时常考虑的关键因素,而且在很多实际项目中,任务的执行允许中断.研究一类资源具有多技能和时间窗约束的任务可中断项目调度问题,建立了相应的整数规划模型,设计了一种分支定界算法构造搜索树进行求解,搜索树的每个节点代表一个任务组合,同时为减少分支节点数,提出了两个有效的剪枝规则,并设计了节点优先规则,对各节点任务组合则采用贪婪算法来进行资源约束判断.利用改进的PSPLIB案例库设计多组计算实验,实验结果检验了优选策略的有效性,经与CPLEX模型求解和基本启发式方法的对比揭示了算法在解决这类问题上的效率和有效性,求解结果可为实际项目调度提供决策依据.

The characteristics of multi-skilled resources and time window constraints on them are the key factors often considered in the field of software development,engineering design,equipment maintenance and so on.In many real projects,the execution of tasks allows to be interrupted.In this paper,an integer programming model is established for this preemptive project scheduling problem with time-window constraints on multi-skilled resources,and a branch and bound method is developed to construct a search tree to find solutions of the problem where each node represents a combination of tasks.To reduce the number of branch nodes,two valid pruning rules are proposed and the node priority rules are designed.For the task combination of each node,a greedy algorithm is employed to verify resource constraints.Using improved PSPLIB in experiments,the results show the effectiveness of dominance strategies,and the comparisons with the CPLEX and the basic heuristic algorithm reveal the efficiency and effectiveness of the proposed method in solving such problem.The solutions can provide support for the actual project scheduling to make better decisions.