论文部分内容阅读
排序问题是组合最优化的一个重要分支，由于其实际应用背景一直受到人们的广泛关注.本报告主要研究了线性规划（凸规划）在设计排序问题近似算法中的应用，报告主要分以下几个部分: 1.第1章为前言部分，主要介绍了一些预备知识，以及本报告所涉及的几个问题的国内外研究现状. 2.第2章对于工件具有到达时间及加工费用的无关机排序问题进行了研究;在工件的总加工费用不超过C的条件下，极小化工件的最大完工时间.对于工件的加工时间固定的情形，利用线性规划舍入的方法得到了一个2近似算法;而对于工件的加工时间不固定的情形，则给出了一个2+ε近似算法. 3.第3章对于工件带有优先约束的同型机排序问题（机器数目充分多）进行了探讨.工件可以不加工，但要付出相应的惩罚.工件与其前，后继之间存在着信息延误.目标函数为极小化加工工件的最大完工时间与被拒绝工件的总惩罚费用之和.对于这一问题，同样运用线性规划舍入的方法得到了一个4近似算法. 4.第4章对于工件带优先约束及加工可拒绝的单台机器排序问题进行了研究，目标函数为极小化加工工件的加权完工时间和与被拒绝工件的总惩罚费用之和.我们考虑了该问题的特殊情形:工件i为工件j的前继，若工件i加工，则工件j也要加工.对于这一情形给出了一个4近似算法. 5.第5章对于工件加工可拒绝的无关机排序问题进行了研究，讨论了2台机器的特殊情形.工件可以不加工，但要付出相应的惩罚.目标函数为极小化加工工件的最大完工时间与被拒绝工件的总惩罚费用之和.对于这一问题，运用线性规划舍入的技巧给出了一个近似比为3的确定性算法，以及两个近似比分别为2，3的随机算法. 6.第6章对于工件加工可拒绝的无关机排序问题进行了研究，目标函数为极小化加工工件的加权完工时间和与被拒绝工件的总惩罚费用之和.通过建立该问题的凸规划松弛的方法，得到了该问题的三个近似算法，近似比分别为2+√3,(7+√33)/4和3/2. 7.第7章为结论，对本报告所做的工作进行了总结.