论文部分内容阅读
研究了在给定截止期限（deadline）下的单机分批（batch）排序问题，目标函数是最大提前完工时间。由于工件不能延迟，因此先讨论了问题可行解的存在。当问题有可行解时，证明了工件按最早截止期限（Earliest Deadline，ED）规则的排序是一个最优排序，接着给出一个时间复杂度为O（n^3）的动态规划算法来获得最优分批。