工件加工时间非恒定且工件可拒绝的排序问题

摘要

排序问题是一类重要的组合优化问题。本文提出一类新型的排序问题--工件加工工时间非恒定且工件可拒绝的排序问题，并对这类问题做了初步研究，具体分为以下几方面； 1. 介绍了有关排序问题，计算复杂性及近似算法等的一些基本概念，并对加工时间非恒定排序问题及工件可拒绝的排序问题的相关结果做了简要的介绍。同时，阐述了研究加工时间非恒定且工件可拒绝的排序问题理论意义与应用价值。 2.工件加工时间是其开始加工时间的线性函数且工件可拒绝的排序问题。 对于最小化最大完工时间与拒绝惩罚和的问题，最小化加权总完工时间与拒绝惩罚和的问题以及最小化最大延迟/延误与拒绝惩罚和的问题，我们分别证明了它们是NP-困难的，并设计了伪多项式时间的最优算法及充分多项式时间近似算法。 3.工件加工时间是其基本加工时间和开始加工时间的线性函数且工件可拒绝的排序问题。 对于最小化最大完工时间与拒绝惩罚和的问题，我们证明了它是NP-困难的，并设计了伪多项式时间的最优算法及充分多项式时间近似算法。 对于最小化加权总完工时间与拒绝惩罚和的问题，我们证明了它是NP-困难的，并对它的一个特例设计了多项式时间的最优算法。 4.工件加工时间是其正常加工时间和开始加工时间的线性函数且工件可拒绝的带优势关系流水作业问题。 对于最小化最大完工时间与拒绝惩罚和的问题，最小化总完工时间与拒绝惩罚和的问题，我们分别设计了多项式时间的最优算法。 5.工件加工时间与工件所排位置有关且工件可拒绝的排序问题。 对于最小化最大完工时间与拒绝惩罚和的问题，我们分别设计了多项式时间的最优算法。 此外，本文还研究了以下加工时间恒定的问题。 1.证明了加工时间恒定的最小化误工工件个数与拒绝惩罚和的排序问题是NP-困难的。 2.约束条件下加工时间恒定的工件可拒绝的排序问题。 对于在拒绝惩罚和的约束条件下最小化最大完工时间的问题，在拒绝惩罚和的约束条件下最小化最大延迟/延误的问题，我们分别证明了它们是NP-困难的，并设计了伪多项式时间的最优算法及充分多项式时间近似算法。