基于动态规划的资源受限随机工序调度  

Resource Constrained Stochastic Job Scheduling Based on Dynamic Programming

作　　者：蒋维[1] 陈开[1] 钟小强[1] 王成恩[2] 竺长安[1] 

机构地区：[1]中国科学技术大学工程科学学院,合肥230027 [2]东北大学教育部流程工业重点实验室,沈阳110004

出　　处：《计算机工程》2008年第16期19-21,共3页Computer Engineering

基　　金：中国科学院创新基金资助项目(200417009)

摘　　要：为解决资源受限条件下的随机工序调度问题,该文提出一种基于离散随机动态系统描述的加工时间离散随机分布且同时具有不兼容和多种可更新资源约束的资源受限项目调度模型,使得在满足资源约束和工序约束的前提下,总的平均加工时间最短。该系统研究了动态规划算法求解该问题的方法。通过实例,验证了该方法的有效性和可行性。To deal with resource constrained stochastic job scheduling problem, a discrete-time.job during distribution stochastic project scheduling problem subject to an incompatibility constraint and multiple renewable resource constraints is described by a discrete-time discrete-event dynamic system. The objective is to minimize the expected project duration under the resource and job order constraints. The optimal solution can be obtained by solving a stochastic dynamic program. The solution modeled as a Markov decision process is described in detail. A typical example validates the feasibility of the method.

关 键 词：资源受限 随机工序调度 动态规划 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]