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