排序问题有着深刻的实际背景和广阔的应用前景，一直受到国际学术界的重视。本文主要研究了带有固定工件和工件运输时间的单机排序问题。固定工件是一类特殊的工件，它们的开工时间和完工时间都是预先确定的，在时间轴上占据着一些互不相交的区间。在整个加工过程中，工件不允许中断。每个工件有一个运输时间，我们假定在工件加工完后有足够多的卡车运输。论文共分两章。第一章（概述）主要介绍了排序的背景、发展、基本概念及排序模型的记法。第二章主要讨论了四个排序模型的复杂性、拟多项式时间算法和近似算法。用三参数法表示我们的模型即是：本文主要结果如下：（1）问题1|FB（F），qj|Lmax、1|FB（F）|maxwjGj和1|FB（F）|∑wjCj是NP-困难的，问题1|FB，qj|Lmax是强NP-困难的。（2）问题1|FB（F），qj|Lmax、1|FB（F）|maxwjCj和1FB（F）∑wjCj是拟多项式时间可解的。（3）对于问题1|FB，qj|Lmax给出了最坏性能比为2的近似算法，并证明这是最好可能的多项式时间近似算法；对于问题1|FB（1），qj|Lmax给出了最坏性能比为3/2的多项式时间近似算法；对于问题1|FB（1）|maxwjCj给出了最坏性能比为2的多项式时间近似算法，在为常数的情况下我们得到了PTAS算法。并证明除非P=NP，对于问题1|FB（2）|maxwjCj，不存在常数界的多项式时间近似算法。
本文来源: https://www.lw50.cn/article/4740b0af0316dc062699515c.html