具有随机返工且可中断的设计任务调度

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

Preemptive Scheduling of Design Tasks with Random Rework

The characteristics of random rework and preemption make the design task scheduling problem become very difficult. To address this issue, a mathematical model is constructed based on Markov decision processes. An optimal solution that minimize the expected total weighted tardiness cost is obtained by the dynamic programming. To deal with the curse of dimensionality that faced by traditional dynamic programming, a method based on multi-rule combination is employed to reduce the amount of feasible actions in each state, which can efficiently obtain a suboptimal solution. Experimental results show that the traditional dynamic programming can only handle some very small-scale problem instances, while the proposed multi-rule combination method effectively balances the optimization effect and computational efficiency, which is more practical.