A Q‐Learning‐based method applied to stochastic resource constrained project scheduling with new project arrivals
A Q‐Learning‐based method applied to stochastic resource constrained project scheduling with new project arrivals
复制标题
基于 Q-Learning 的方法应用于新项目到达的随机资源受限项目调度
DOI：
10.1002/rnc.1164
复制
发表时间：
2007
影响因子：
3.9
通讯作者：
Jay H. Lee
中科院分区：
文献类型：
--
作者：
Jaein Choi;M. Realff;Jay H. Lee
在许多资源受限项目调度问题（RCPSP）中，候选项目集不是先验固定的，而是随时间而变化的。例如，当根据某个决策策略执行一组初始项目时，可能会出现一个新的有前途的项目。为了对这样的问题做出适当的资源分配决策，项目取消和资源闲置决策应该补充传统的调度决策。在这项研究中，随机RCPSP（sRCPSP）与动态项目到达的问题是解决项目取消和资源闲置的灵活性。为了解决这个问题，采用了基于Q-学习的方法。使用的方法，问题被制定为一个马尔可夫决策过程与适当的定义的状态，包括信息状态和动作变量。Q-Learning方法使我们能够从模拟数据中推导出经验状态转换规则，以便可以规避可能过于复杂的状态转换规则的分析计算。为了最大限度地利用经验学习的状态转换规则的优势，特殊类型的行动，包括项目取消和资源闲置，这是很难纳入竞争力，随机添加到模拟。在Q值迭代过程中过滤随机动作，并在在线决策中适当利用，以最大化总预期奖励。版权所有© 2007约翰威利父子有限公司。
In many resource‐constrained project scheduling problems (RCPSP), the set of candidate projects is not fixed a priori but evolves with time. For example, while performing an initial set of projects according to a certain decision policy, a new promising project can emerge. To make an appropriate resource allocation decision for such a problem, project cancellation and resource idling decisions should complement the conventional scheduling decisions. In this study, the problem of stochastic RCPSP (sRCPSP) with dynamic project arrivals is addressed with the added flexibility of project cancellation and resource idling. To solve the problem, a Q‐Learning‐based approach is adopted. To use the approach, the problem is formulated as a Markov Decision Process with appropriate definitions of states, including information state and action variables. The Q‐Learning approach enables us to derive an empirical state transition rules from simulation data so that analytical calculations of potentially exorbitantly complicated state transition rules can be circumvented. To maximize the advantage of using the empirically learned state transition rules, special type of actions including project cancellation and resource idling, which are difficult to incorporate into heuristics, were randomly added in the simulation. The random actions are filtered during the Q‐Value iteration and properly utilized in the online decision making to maximize the total expected reward. Copyright © 2007 John Wiley & Sons, Ltd.