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

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

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

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

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