Abstract: 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.

Key words: design task, random rework, preemption, Markov decision processes, dynamic programming, multi-rule combination