论文部分内容阅读
排序问题一直受到国际学术界的重视，其中分批排序问题，因其明显的实际意义，更是吸引了国内外许多学者。
本文主要研究了两个单机分批排序问题。文章讨论了工件有到达时间和尺寸的单机分批排序问题1|B，rj，sj|Cmax。对于这一类问题，本文严格限制机器的容量B是和问题规模无关的常量。就最差性能比方面来说，得出了更好的研究结果；文章同时讨论了工件有到达时间的目标函数是极小化最大延误时间的单机分批排序问题1|B，rj|Lmax，在机器的容量B是常数的情形下给出了PTAS算法。