同类机上最小化时间表长的在线排序问题

摘要

在恒同机中机器有相同的速度，工件的加工时间与机器没有任何关系仅与它自身的长度有关；而在一致机中，机器的速度是不相同的，且每一个工件的加工时间不仅与它自身的长度有关系而且与该工件所排的机器速度也密切相关.
　　在本文第二章中，我们探讨了在m台同类机上，每个工件的长度均为1,且批容量为无界的在线排序问题，用三参数表不为Qm|online, p-batch,b=∞,pj=1|Cmax(m≥2),其中前a(a≥2)台机器的速度为1,后 m-a台机器的速度为v(0＜v＜1).在线排序是指工件是按时间顺序到达的，工件到达之前，我们不知道它的任何信息.平行分批即是在一台机器上可以同时加工至多b个工件,且该批次的加工长度为该批工件中加工长度最长的工件加工长度.根据批次能容纳工件个数的限制，可分为两个不同的模型.一种模型是一台机器上可以同时加工的工件个数b是有限的，称该模型为批容量有界的；另一种模型是一台机器上可以同时加工的工件个数b是无限的，称该模型为批容量无界的.本章我们研究的是批容量为无界的情形.给出了竞争比为此处为公式的最好可能的在线算法.其中α是方程（1+α)α+1=2+α的正根,β是方程此处为公式的正根（a表示速度为1的机器的数量, m表示总机器的数量).
　　在本文第三章中，我们研究了两台同类机上批容量为有界的最小化时间表长的在线排序问题，用三参数表示为此处为公式,其中M机器的速度为1, M2机器的速度为v(0＜v＜1).这里工件也是按时间顺序到达的，在工件未到达之前我们不知道它的任何信息.在该章中所有工件的标准加工长度Pj均为1,而两台机器的速度是不相同的，第一台机器的速度为1,第二台机器的速度为v,则我们可知排在速度为1的机器上的工件的实际加工时间为该工件自身的加工时间1,而排在速度为v的机器上的工件的加工时间等于该工件的标准加工时间1与机器速度v的比值v/1.本章给出的竞争比的下界为此处为公式其中α1是方程此处为公式的正根，α2是方程此处为公式的正根，α3是方程此处为公式的正根.当0＜v＜2/1时,给出了竞争比为1+α1的最好可能的在线算法,当2/1≤v＜1时,给出了竞争比为1+α的在线算法,其中α是方程（1+α)2=2+α的正根.

目录

第一个书签之前