Abstract:
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.
Key words:
resource constrained,
stochastic job scheduling,
dynamic programming
摘要: 为解决资源受限条件下的随机工序调度问题,该文提出一种基于离散随机动态系统描述的加工时间离散随机分布且同时具有不兼容和多种可更新资源约束的资源受限项目调度模型,使得在满足资源约束和工序约束的前提下,总的平均加工时间最短。该系统研究了动态规划算法求解该问题的方法。通过实例,验证了该方法的有效性和可行性。
关键词:
资源受限,
随机工序调度,
动态规划
CLC Number:
JIANG Wei; CHEN Kai; ZHONG Xiao-qiang; WANG Cheng-en; ZHU Chang-an. Resource Constrained Stochastic Job Scheduling Based on Dynamic Programming[J]. Computer Engineering, 2008, 34(16): 19-21.
蒋 维;陈 开;钟小强;王成恩;竺长安. 基于动态规划的资源受限随机工序调度[J]. 计算机工程, 2008, 34(16): 19-21.