Dec 25
运筹学和决策论的研究人员运用马尔可夫APS生产排程决策过程研究序列决策问题已经有很多年的历史了。在近十几年中，人工智能的研究人员运用马尔可夫决策过程研究了包含不确定性的计划问题。马尔可夫决策过程是一种基于决策论的计划方法。
在马尔可夫决策过程中，状态之间的迁移在本质上是随机的。求解过程所面对的一个主要挑战是状态空间的容量，因为各个状态之间的随机迁移，导致了问题的空间十分庞大。
除状态空间的容量外，马尔可夫决策过程还有下列不足：
1、马尔可夫决策过程假定每一个作业完成后的效果均可以观测到，但这在实际项目中未必能够做到。而专门针对这类问题的部分可观马尔可夫决策过程，又只能求解规模较小的问题。
2、时间是离散的。每个作业都即刻完成，而且不可中断。当考虑并行事件或外部事件时，状态空间的容量问题又会凸显出来。
3、由于马尔可夫决策过程的复杂性，它无法严格保证在指定的决策成本范围内一定能达到期望的目标，因而不便于描述目标十分明确的计划问题。