论文部分内容阅读
本文主要研究单机批处理排序问题的动态规划算法，问题的目标函数为完工时间和。
首先对问题1｜ri={0，r}，pi=p，B=6｜∑Cj提出了一个复杂性为O(n3)的动态规划算法，并进一步讨论了如何降低该算法的复杂性到O(n)。
在该动态规划算法中，我们定义状态(t，γ)，其中t为某个机器空闲时刻，γ表示在t时刻或之前已经到达、但还未开始加工的工件个数。进而考虑如何安排工件使得上述γ个工件的完工时间和到达最小，并建立了相应的递推关系。该动态规划算法的思想也可以推广到k个加工时间的一般情况。
另外，本文还讨论了问题1｜ri={0，r}，B=6｜∑Cj的近似算法，得到了一个性能比为2的算法。