论文部分内容阅读
本文以经典排序模型P2||C<,max>为例，研究一类新的排序模型，可重排在线排序问题，即当工件到来时必须确定它将在那台机器上加工，但当所有工件都安排完毕后，可以在一定的条件下对已安排的工件进行重新安排．研究了四类不同的模型，第一类是我们可以重排整个工件序列中的最后k个工件，其下界为3/2．第二类是可重排全部工件安排完毕后每台机器上的最后一个工件，其下界是平方根2，同时给出了最优算法．第三类是可以重排任意有限的k个工件，其下界为4/3，同时我们设计出只需重排一个工件的最优算法．在第四类模型中，研究带费用重排问题，即可以在工件安排完毕后重排任意工件，重排费用为工件加工时间的α倍，目标函数为makespan和重排费用之和．给出了问题的下界，并分析了一些简单算法的竞争比．全文结构编排如下：
第一章是绪论，介绍排序相关知识和初步结论．
第二章研究了前三类不需重排费用的可重排模型：
第三章研究带费用重排模型.