排序问题是组合最优化领域中的一类重要的问题。所谓排序就是指在一定的约束条件下分配时间和资源去完成一些任务，使一个或多个目标达到最优。近年来，在线排序和半在线排序是两个发展比较迅速的分支。在线排序是指工件信息在到达之前是一无所知的，并且工件一旦被安排后就不允许改变。离线排序是指在工件安排之前就知道所有工件的信息。在现实生活中，有许多问题既不是在线问题，也不是离线问题，而是介于两者之间的，这就是半在线问题。在排序之前知道后面就绪的工件的部分信息。同类机平行机排序问题是一个重要的平行机排序。一般地，问题可描述为：设有一个工件集J={J1，J2，…，Jn}包含n个相互独立的工件，其中工件Ji的加工时间用Pi来表示，工件需分给m（m＞1）台机器M1，M2，…，Mm进行加工．机器Mj的速度为sj，j=1，2，…，m．任意工件在不同机器上的加工时间有相同的比例关系．若工件Pi分给Mj加工，则可用Pi/sj个单位时间完成该工件。在传统的经典排序问题中总假设机器均可以在零时刻加工工件，但我们知道在现实生活中情况往往并非如此，比如说每台机器有一个准备时间．只有在准备时间之后机器才可以开始加工工件。这些问题称为带有机器准备时间的排序问题．本文主要讨论了具有机器准备时间的两台机器的半在线排序问题。其中sum代表所有工件的总加工时间，Pmax代表最大工件的加工时间。本文的主要结果如下：（1）给出了排序模型Q2，rj|sum|Cmin的一个竞争比至少为（s+1）/（2s+1）的半在线算法．（2）给出了排序模型P2，rj|Pmax，sum|Cmin的一个竞争比为4/5的最优的半在线算法．（3）给出了排序模型Q2，rj|Pmax，sum|Cmin的一个竞争比至少为（2s+2）/（3s+2）的半在线算法．
本文来源: https://www.lw50.cn/article/c96fe352cff40a33f5ab6cf3.html