平行机在线排序问题.ppt

平行机在线排序问题平行机在线排序问题平行机在线排序问题把需要完成的任务称为工件（job）

把完成任务需要的资源称为机器

平行机在线排序问题平行机在线排序问题平行机在线排序问题第一章：在线排序OnlineoverlistOnlineoverlistOnlineoverlistOnlineoverlistOnlineoverlistOnlineoverlistOnlineoverlist参考文献参考文献OnlineovertimeOnlineovertime的基本假设：
工件有到达时间，在到达时间之后才能开始加工
在某工件的到达时间之际，该工件的信息（加工时间）完全已知，且即被安排在某台机器上的某时刻起开始加工
在某时刻t，所有到达时间大于t的工件的信息未知
工件一旦被安排加工，其加工方式不可更改

尽管onlineovertime被称为在线，工件信息未知的原因并不是前个工件未安排，而是该工件的到达时间未来临。若一批工件的到达时间相同，则在此时刻它们的所有信息已知，具有离线排序的特征。考虑所有工件到达时间都为0的特殊情况，此时onlineovertime退化为离线模型而非onlineoverlist模型onlineovertimeonlineovertime参考文献OnlinewitharbitraryreleasetimesOnlinewitharbitraryreleasetimesOnlinewitharbitraryreleasetimesOnlinewitharbitraryreleasetimes……注意到Th1.5、Th1.6，当m=1即单台机时仍成立。此时LS算法的竞争比为2，且为最好算法。对一般情形，Li和Huang先后给出了竞争比为2.93920和2.78436的改进算法参考文献Non-clairvoyantNon-clairvoyantNon-clairvoyantOrdinalOrdinalOrdinalOrdinal参考文献参考文献Onlineoverlist的新进展下界下界下界下界下界下界下界下界下界下界下界下界下界下界算法算法算法算法新型算法的必要性参考文献Onlineoverlist的其他结果Onlineoverlist的其他结果Onlineoverlist的其他结果Onlineoverlist的其他结果a1b1a2b2Onlineoverlist的其他结果Q2||CmaxQ2||Cmin参考文献1.半在线排序概说
半在线排序问题分为以下两类
(1)已知未来工件的部分信息或工件集的一些整体信息
(2)额外的工件安排方式或设备
常见的半在线问题有：半在线排序半在线排序半在线排序半在线排序半在线排序半在线排序半在线排序参考文献参考文献半在线排序半在线排序半在线排序半在线排序半在线排序半在线排序半在线排序半在线排序半在线排序半在线排序半在线排序半在线排序半在线排序半在线排序半在线排序参考文献参考文献半在线排序半在线排序半在线排序半在线排序半在线排序半在线排序半在线排序半在线排序Step3.2.1(SC1implicitlysatisfied)Step4.2.2(SC1orSC2neversatisfied)半在线排序半在线排序dissum:

disopt:,可更小半在线排序半在线排序0.0445
0.7640参考文献半在线排序半在线排序参考文献半在线排序参考文献半在线排序半在线排序半在线排序TheoptimalboundsofQ2|sum|CminandQ2|opt|Cmin.TheboldlinesareforQ2|sum|Cmin参考文献第三章：其他在线排序问题参考文献其他在线问题其他在线问题其他在线问题其他在线问题参考文献其他在线问题参考文献其他在线问题参考文献