工件加工時間非恒定且工件可拒絕的排序問題.pdf

1、排序問題是一類重要的組合優(yōu)化問題。本文提出一類新型的排序問題--工件加工工時間非恒定且工件可拒絕的排序問題，并對這類問題做了初步研究，具體分為以下幾方面； 1. 介紹了有關(guān)排序問題，計算復(fù)雜性及近似算法等的一些基本概念，并對加工時間非恒定排序問題及工件可拒絕的排序問題的相關(guān)結(jié)果做了簡要的介紹。同時，闡述了研究加工時間非恒定且工件可拒絕的排序問題理論意義與應(yīng)用價值。 2.工件加工時間是其開始加工時間的線性函數(shù)且工件可拒絕的

2、排序問題。 對于最小化最大完工時間與拒絕懲罰和的問題，最小化加權(quán)總完工時間與拒絕懲罰和的問題以及最小化最大延遲/延誤與拒絕懲罰和的問題，我們分別證明了它們是NP-困難的，并設(shè)計了偽多項式時間的最優(yōu)算法及充分多項式時間近似算法。 3.工件加工時間是其基本加工時間和開始加工時間的線性函數(shù)且工件可拒絕的排序問題。 對于最小化最大完工時間與拒絕懲罰和的問題，我們證明了它是NP-困難的，并設(shè)計了偽多項式時間的最優(yōu)算法及充分

3、多項式時間近似算法。 對于最小化加權(quán)總完工時間與拒絕懲罰和的問題，我們證明了它是NP-困難的，并對它的一個特例設(shè)計了多項式時間的最優(yōu)算法。 4.工件加工時間是其正常加工時間和開始加工時間的線性函數(shù)且工件可拒絕的帶優(yōu)勢關(guān)系流水作業(yè)問題。 對于最小化最大完工時間與拒絕懲罰和的問題，最小化總完工時間與拒絕懲罰和的問題，我們分別設(shè)計了多項式時間的最優(yōu)算法。 5.工件加工時間與工件所排位置有關(guān)且工件可拒絕的排序問題

4、。 對于最小化最大完工時間與拒絕懲罰和的問題，我們分別設(shè)計了多項式時間的最優(yōu)算法。 此外，本文還研究了以下加工時間恒定的問題。 1.證明了加工時間恒定的最小化誤工工件個數(shù)與拒絕懲罰和的排序問題是NP-困難的。 2.約束條件下加工時間恒定的工件可拒絕的排序問題。 對于在拒絕懲罰和的約束條件下最小化最大完工時間的問題，在拒絕懲罰和的約束條件下最小化最大延遲/延誤的問題，我們分別證明了它們是NP-困難的