单机E/T调度问题的动态规划新解法

NEW DYNAMIC PROGRAMMING ALGORITHMS FOR SINGLE MACHINE E/T SCHEDULING PROBLEMS

本文利用最优调度的目标函数的性质，放弃了参数为整数的假定，改进了求解单机的Ｅ／Ｔ调度问题的动态规划算法。

While dynamic programming algorithms are efficient for solving single machine E/T scheduling problems, they usually require the assumption that some parameters must be integers. In this paper, we relax this assumption by taking advantage of piecewise property of object functions of the optimal schedulings, which reduces time complexities and space complexities of dynamic programming algorithms.