多台平行批处理机在线排序和带有运输时间的在线排序

《多台平行批处理机在线排序和带有运输时间的在线排序》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、摘要在线排序是近年来现代排序领域发展最为迅速的模型之一．与经典的离线排序相比较，在线排序最明显的的特点是工件的所有信息是分阶段逐步释放给决策者的，并且，决策者只能根据当前已有的信息来做排序决策．这样的特点不仅仅为研究工作带来大量的困难，而且也让研究者们产生了很大的兴趣．在工业生产和计算机系统中，在线排序都有着广泛的实际应用背景．文献中有很多关于在线排序的定义．最常见的两种是列表在线(online-lisQ排序和时间在线(online-time)排序．在列表在线排序问题中，工件事先排在一个列表中，并且按照列表中的顺序一个接一个的呈现给决策

2、者．在下一个工件出现之前，决策者必须将当前工件安排在某一台机器上．工件一旦出现，决策者就知道该工件的所有信息．在时问在线排序问题中，工件是随时间到来的．每个工件的信息在其到达后决策者才被告知．在工件到达时，决策者可以不立即安排此工件．在本学位论文中，我们考虑的是后一个模型，即，时间在线排序．一个在线算法的优劣往往是通过它的竞争比来衡量的．我们称一个在线算法是伊竞争的是指：对于任何一个实例，在线算法产生的目标函数值至多是离线情形下最优排序目标函数值的P倍．给定一个在线排序问题P，称算法以是问题P的一个最好可能的在线算法是指不存在比算法A具

3、有更好竞争比的在线算法．批处理排序也是近20年来被研究者们广泛研究的一个现代排序模型．它一般包括两种模型：继列分批(serial-batch)排序和平行分批(parallel-batch)排序．在继列分批排序模型中，若几个工件在同一台机器上共享一段安装时间，则称这些工件在同一批中加工．机器一次只能加工一个工件，即，批的加工时间等于安装时问加上该批中所有工件的加工时间之和．在平行分批排序中，在不超过批的容量范围内机器允许同时加工多个工件．批的加工时间是由该批中最长的加工时间来决定．同一批中的工件具有相同的开工时间和相同的完工时间．在文献中

4、平行分批排序一般包含两种模型：一个是批无界情形，即，b=oo；另一种是批有界情形，即，b

5、工件的完工时间和运输时间之和．其中，第四章考虑了具有限制运输时间的单个机器在线排序问题；第五章考虑的是具有限制运输时间的单个平行批处理机在线排序模型；在最后一章中，我们讨论了具有无限制运输时间的单个平行批处理机在线排序模型．具体地，本论文主要结果如下：1．在第二章中，我们考虑了m台批无界平行分批处理机在线排序问题．目标函数是最小化最大完工时间．我们证明了该问题所有在线算法的竞争比的下界是1+‰，其中，‰是方程am2+mQm一1=0的正根，并且给出了一个最好可能的在线算法．同时，我们还考虑了此问题的稠密算法：证明了所有稠密算法的下界为3／

6、2，并且也给出了一个最好可能的稠密算法．2．在第三章中，我们考虑了具有不相容工件组的m台批无界平行分批处理机在线排序问题．不相容工件组是指不同工件组的工件不能放在同一批中加工．我们假设工件组的个数与机器的台数相等．目标函数是最小化最大完工时间．我们证明了此问题所有在线算法的竞争比下界为(佰+1)／2，并且提供了一个在线算法Hm(e)，其中，口是～个参数．当同一个组的工件具有相同的加工时间或者机器数目m=2时，我们证明了算法‰陋)是最好可能的在线算法，其中，口=(锯一1)／2．当机器数目m≥3时，我们证明了算法‰(p)的竞争比是(3+p)

7、／2，其中，p=以一1．同时，我们还证明无论口取何值，当m≥3时算法‰(口)的竞争比不会小于l+ji-石／5．3．在第四章中，我们考虑了具有限制运输时间的单机在线排序问题．目标函数是最小化所有工件被送到目的地的时间．我们假设所有工件的运输时间都不超过其本身的加工时间．我们证明了此限制模型所有在线算法的竞争比下界是钜，并且给出了一个最好可能的在线算法．4．在第五章中，我们考虑了具有限制运输时间的单个批无界平行分批处理机在线排序问题．目标函数是最小化所有工件被送到目的地的时间．我们假设所有工件的运输时间都不小于其本身的加工时间．我们证明了此

8、限制模型所有在线算法竞争比的下界是(锈+I)／2，并且给出了一个具有竞争比(锯+1)／2的在线算法．5．在第六章中，我们考虑了具有无限制运输时间的单个批无界平行分批处理机在线排序问题．目标函数是最小化所有工