摘要：随机返工和可中断特征使得设计任务调度问题异常复杂。针对该问题,采用马尔可夫决策过程理论建模,并利用动态规划方法求解使得加权拖期总成本期望最小的最优调度策略。为了应对传统动态规划面临的维数灾,引入多规则组合算法来限制每个状态下的可选行动数量,从而高效获得次优调度策略。实验结果表明,传统动态规划仅能够求解小规模问题,而所提出的多规则组合方法则有效权衡了优化效果和求解效率,更具实用价值。

关键词：设计任务 随机返工 可中断 马尔可夫决策过程 动态规划 

单位：广东工业大学广东省计算机集成制造重点实验室; 广东广州510006