论文部分内容阅读
本文考虑了两台同型机上一类特殊的在线排序问题，即加工时间可控的在线排序。在这个问题中，工件的加工时间不是固定的常数，而是决策变量，排序者可以选择支付一定的费用而使工件的加工时间变小，目标函数是需要支付的总费用与工件的最大完工时间之和。在连续可控模型中，工件的加工时间可以在一个区间内任意取值，每个工件有一个正常加工时间、单位压缩费用和最大压缩量，它的实际加工时间是正常加工时间与压缩量的差，压缩费用是压缩量与单位压缩费用的积。我们讨论了最大压缩量等于和小于正常加工时间两种情形，分别给出了竞争比为1.618的在线算法。在离散可控模型中，工件的加工时间只能从给定的有限个数值中选取，并且每一个加工时间对应一个加工费用，我们讨论了只有两种加工时间、单位压缩费用恒定和具有任意压缩费用的情形，分别给出了竞争比为1.618的在线算法．并证明了给出的算法是最优的。