可重排排序问题.研究

《可重排排序问题.研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章绪论2，y域表示要优化的目标函数，包括最大完工时间(G，。)，最小完工时间(ck。)，总完工时间(∑q)，加权总完工时间(∑嘶q)，最大延误(L～)，总误工(∑D，)等等．例如对于下面这个经典的排序问题：给定一个工件的集合J={^，五，⋯厶)，工件正的加工时间为A，需要将它们安排在m台同类平行机尬，M2，⋯^‰上加工，目标函数是极小化最大加工时间，那么用上面的记号就可以简单地将这个问题表示为A圳lG—．事实上，如果我们记I1，如果工件^分配在^母上，叫一10．其它．则此问题等价于如下定义的整数线性规划问题：r

2、ainGm扎t∑xo=1，i=1⋯2．．，佗jffiln‰≥∑鼽％，J=1⋯2。miffil％=0或1，i=1，2，⋯，n，J=1，2，⋯，m其中第一个约束表示每个工件仅分给一台机器加工，第二个约束表示第J台机器上加工的工件的总加工时间不超过G。。．因此可以看出排序问题其实是一类特殊组合优化问韪，在许多优化问题模型中都可以找到它的原型，之所以将它们单独作为一类问题来研究，除了由于它有着非常广泛的应用背景以外，问题本身具备的特殊性也是一个重要因素，而寻找一个晟优排序就是要充分利用这些特殊性质．因此，作为运筹学一门新兴

3、的学科分支，排序论在近几十年内正被越来越多的学者深入地研究，在国内也产生了大量的相关文献．在经典排序文献中，我们根据排序者在排序时掌握的工件信息的多少把排序问题分为离线排序，在线排序两类．在离线问题中，全部工件的所有信息在排序时均已知，排序者可以充分利用上述信息对工件进行安排．而对于在线问题，我们假设工件的信息是逐个释放的，即只有把当前到达的工件全部安捧完毕才会得知下一个工件的信息，另外工件加工是不可改变的，即一旦排序者将工件安排给某台机器加工，在其后的任何阶段都不能以任何方式加以改变．第一章绪论3随着排序和实际的

4、发展，又产生了新的一类排序，半在线排序『28，291．半在线排序是介于在线排序和离线排序之间，即排序者一方面不可能知道工件的所有信息，但拥有比经典在线模型更多的信息或有更大的排序自由度，并且工件安排加工后不可更改．半在线排序主要可以分为两类，第一类半在线模型是指排序者掌握后续工件的部分信息，第二类排序是指已安排的工件的加工进程可通过某种方式加以改变．目前研究较多的是第一类半在线模型『3，4，7，8，13，14，15，16，18，24，25，261，如已经工件总加工时间(Known眦m)，已知工件最大加工时间(Kno

5、wnlargestjob)，工件加工时间在一区间内(Interval)，工件加工时间非增(Non-increaaingjob)等以及它们之间的复合．第二类半在线模型主要有带缓冲区(Buffer)，两个平行处理子系统(Twoparallelproce∞Om)等【18，27】．求解离线和(半)在线问题的算法分别称为离线算法和(半)在线算法，对于(半)在线算法，我们采用竞争比分析来衡量算法的有效性，它属于最坏情况分析．对于在线问题的算法A，i己GA(I)ffⅧIC'(I)分别表示算法A解实例，所得的目标函数值和相应问题离

6、线情形的最优目标值，对于极大化排序问题，则称cA=inf{c≥116'*(1)≤。c4(j)，V，)为在线算法A的竞争比；对于极小化排序问题，则称ca=inf{c≥IlcA(I)≤cC’(nvl}为在线算法A的竞争比．若称在线问题的下界为c，则是指该问题不存在竞争比比c小的在线算法．为了得到问题下界，一般可以通过给出一系列实例，使得任何在线算法都不能很好的求解所有实例来得到．若算法A的竞争比等于该问题的下界，则称A为最优算法．从竞争比的意义上看，它是指在线问题可能得到的最好结果．第一章绪论41．2可重排在线排序在经

7、典排序中假设工件加工后不可重排，但在实际生活中未必如此．考虑下面实例：一个服务器，其存储设备由若干存储器组合，当信息文件到来时，必须当即安排其存储在某个存储器上，为保持文件读取的完整性，同一文件都必须存储在同一存储器上，同时为了高效性我们需要保持各个存储器的平衡，即有必要将文件在各个存储器上进行调整，但受CPU，网速等的影响我们的调整有一定的限制，另外重排也有可能产生一定费用．对于这类当工件到来时必须确定它将在那台机器上加工，当所有工件都安排完毕后，我们可以在一定的条件下对工件进行重排，称此类排序其为可重排排序．可

8、重排排序虽然是一个较新的领域，但在实际中有很大的用处，目前研究也有初步进展．在本论文中，我们主要研究四类可重排在线排序模型，第一类是我们可以重排整个工件序列中的最后k个工件，第二类是我们可重排全部工件安排完毕后每台机器上的最后一个工件，第三类是可以重排任意有限个工件，在第四类模型中，我们研究带费用重排问题，即可以在工件安排完毕后重排任意工件，重排费用为工件加