论文部分内容阅读
在排序理论中，提前与延误问题根据目标函数的不同主要分为两大类：总费用最小化问题和最大费用最小化问题。在给定工件集合，以及每个工件的加工时间、惩罚系数，相同工期的条件下，本文讨论了最大费用最小化问题的各个模型以及相应的算法。主要的研究工作和成果有以下几个方面：
1.相比cheng在1987年利用线性规划给出1 ||maxEj+Tj最优时间表，本文给出了一个比较简单的多项式时间算法，并且给出了当工期为限制条件下的最优解算法。
2.对于1||maxαEj+βTj模型，我们对工期为非限制和限制情形分别给出了相应的多项式时间算法。
3.1||max ωj|Cj=d|是NP困难的，但本文就工件加工时间相等的情形给出了多项式时间算法，并且把这个算法推广到了工期为限制条件下的情况。另外，在加工时间与惩罚系数相等的情形，我们在开工时间给定的情况下给出了一个动态规划算法。
4.给出了P2||max|Cj=d|与P2||Cmax的等价性证明，并在此基础上给出了一个近似算法，最后把该算法推广到了m台机器的情况。对于Q2||max|Cj=d|也有相似的结论。
5.对于多台机器上工件加工时间相等的模型P2|pj=P|maxωj|Cj-d|，给出了一个类似于单台机器的算法，并且推广到m台机器。