工件有优先约束的分批排序问题

摘要

排序论作为运筹学的一个重要分支，有深刻的实际背景和广阔的应用前景，一直受到国内外学术界的重视.而其中的分批排序问题，因其明显的实际意义，更是吸引了许多学者的关注. 本文研究了工件带有优先约束的单机分批排序问题，工件有优先约束是指工件加工时必须按一定先后顺序加工，一般的，若工件Ji与Jj有优先序，即Ji＜Jj,，它表示Jj必须在Ji完工之后才能开始加工.这里的目标函数为极小化工件的最大完工时间即最后被加工工件的完成时间.论文共分三部分： 第一部分(引言)主要介绍了排序的产生背景，发展及其相关的基础知识.第二部分，我们讨论了工件有不同的到达时间和平行链约束的分批排序问题，即问题1|chainas，B，rj|Gmax.平行链约束是指每一个工件至多有一个前驱工件和一个后继工件，例如工件Ji，Jj和Jk满足平行链约束Ji＜Jj＜Jk，意思是工件Ji是工件Jj的唯一的前驱而工件Jk是工件Jj的唯一的后继，换句话说，工件Jj必须在工件Ji之后工件Jk之前加工. 我们先对两条平行链，工件有不同的到达时间，其中一条链上有n个工件，另外一条链上的工件数为常数K的情形给出了计算时间为O(nK)的多项式时间算法；接着考虑有m条链，其中一条链上包含n个工件，其余的m-1条链上的工件数总和∑mi=2ki为常数，对于所有工件在不同的时间到达时，我们给出了一个多项式算法，其计算次数为O(n∑mi=2ki). 同时，我们指出对于一般的正则目标函数，当有m条链，其中一条链上包含n个工件，其余的m-1条链上的工件数总和为常数，且工件在不同的时间到达时，也是多项式时间内可解的. 第三部分，我们研究了工件有优先约束且尺寸不同的分批排序问题.工件尺寸是指工件的体积.当工件放进某一批加工时，我们既要考虑此工件的尺寸又要考虑工件之间的优先约束.对于这类问题，目前很少有人涉及.我们考虑的情形是：加工时间相同但尺寸不同的工件之间有一定的优先约束关系，在满足优先约束的条件下，将工件安排到单台批处理机上加工，使目标函数值最大完工时间最小，即问题1|B，sj,prec,rj=e+kjp,pj=p|Gmax其中kj=「rj/p」，e为常数，且0≤e≤p-1，p，rj，1≤j≤n为整数. 本章先对工件尺寸相同的情况给出了计算次数为O(n2)的多项式最优算法，而后在此基础上对工件可拆分的情形提出最优算法，再把拆分工件放进一批放在可行的位置加工，这样，我们就得到了此问题的2-近似算法. 其中，文中提出的对于批量有限时工件到达时间的修正法和批量有限且工件有不同尺寸的工件到达时间的修正法，就我们所知，是有优先约束分批排序问题的一个突破和创新，并且此方法也可应用到其他的目标函数上. 除了完成上述分批排序论文外，我还在导师的指导下对组合最优化的最小费用流问题和场址设置问题进行了初步研究，第四部分是已发表的两论文的主要结论.

目录

文摘

英文文摘

第一章引言

第二章带链优先约束的分批排序

第三章工件有优先约束和尺寸的单机分批排序问题

第四章有关说明

参考文献

硕士生期间撰写的论文

致谢