论文部分内容阅读
主要考虑了在线和离线两种模型下的工件带运输时间的单机分批排序问题,工件一但被加工完将会被马上运往目的地.我们考虑了三种限制模型:(1)在线模型:批量B无穷大,工件的加工时间和运输时间一致,即:若工件Ji的加工时间Pi大于等于工件Jj的加工时间Pj,那么它们的运输时间有qi≥qj(2)在线模型:批量B无穷大,工件的最大运输时间和最小的运输时间的比小于等于1+√5/2对于(1),(2)这两种模型我们给出了一个竞争比为1+√5/2的在线算法,并且这个结果是最好的.(3)离线模二型:批量B有限,当工件的到达时间是