工件加工時(shí)間非恒定的排序模型研究.pdf

1、排序問(wèn)題是運(yùn)籌學(xué)中一類重要的組合優(yōu)化問(wèn)題.在經(jīng)典排序問(wèn)題中，通常假設(shè)工件的加工時(shí)間是恒定的.但是在諸多有實(shí)際背景的問(wèn)題中，工件的實(shí)際加工時(shí)間由于加工機(jī)器設(shè)備，工件本身以及加工順序(位置)等因素的影響而不可能始終是恒定的.此產(chǎn)生一類重要的新型排序問(wèn)題—工件加工時(shí)間非恒定的排序問(wèn)題.一般來(lái)說(shuō)，這類排序問(wèn)題比經(jīng)典排序問(wèn)題更為復(fù)雜，絕大多數(shù)均為NP-hard問(wèn)題.而對(duì)于NP-hard問(wèn)題的研究，一般是研究它的多項(xiàng)式時(shí)間近似算法，并分析該近似算法

2、的最壞情況界.然而由于生產(chǎn)實(shí)踐的需要，研究某NP-hard問(wèn)題一些特例的多項(xiàng)式時(shí)間算法是很有必要的.它一方面可以為求出該NP-hard問(wèn)題一些特例的最優(yōu)解提供方法，另一方面也可以為解決原NP-hard問(wèn)題提供近似算法，從而使排序理論更好地服務(wù)于生產(chǎn)實(shí)踐.本文主要對(duì)工件加工時(shí)間非恒定的排序模型進(jìn)行了研究.并在以下幾個(gè)方面做了一些探討： 1.本文介紹了有關(guān)排序問(wèn)題，計(jì)算復(fù)雜性，近似算法以及最壞情況界等基本概念，并對(duì)近年來(lái)出現(xiàn)的各種工

3、件加工時(shí)間非恒定的排序模型及其有關(guān)結(jié)果作了簡(jiǎn)要的歸納. 2.對(duì)工件加工時(shí)間是其正常加工時(shí)間和開(kāi)始加工時(shí)間的線性函數(shù)的排序模型. (1)對(duì)目標(biāo)函數(shù)為加工全程的單機(jī)排序問(wèn)題，給出了相應(yīng)的最優(yōu)算法；對(duì)于加權(quán)總完工時(shí)間的單機(jī)排序問(wèn)題證明了其為NP-hard的 (2)對(duì)機(jī)器具有某種優(yōu)勢(shì)關(guān)系的流水作業(yè)排序問(wèn)題進(jìn)行了研究，取目標(biāo)函數(shù)分別為加工全程和完工時(shí)間之和，對(duì)它們分別給出了最優(yōu)算法. 3.對(duì)工件加工時(shí)間是其開(kāi)始加工

4、時(shí)間的線性函數(shù)的排序模型. (1)對(duì)工件間有調(diào)整時(shí)間和沒(méi)有調(diào)整時(shí)間的單機(jī)排序問(wèn)題，以加工全程，加權(quán)完工時(shí)間之和以及最大延誤等為目標(biāo)函數(shù)作了研究，并給出了相應(yīng)問(wèn)題的最優(yōu)算法或者證明了其計(jì)算復(fù)雜性. (2)對(duì)目標(biāo)函數(shù)為極小化最大完工時(shí)間和極大化最小機(jī)器完工時(shí)間的平行機(jī)排序問(wèn)題進(jìn)行了探討，分別給出了近似算法并分析了相應(yīng)的性能比. (3)證明了工件具有調(diào)整時(shí)間的兩臺(tái)機(jī)器的流水作業(yè)排序問(wèn)題是NP-hard的，討論了機(jī)器具有

5、一定優(yōu)勢(shì)關(guān)系下的一些特殊情況，對(duì)目標(biāo)函數(shù)為極小化最大完工時(shí)間的情形給出了最優(yōu)算法. 4.對(duì)具有學(xué)習(xí)效應(yīng)的排序模型. (1)提出了一種新的具有學(xué)習(xí)效應(yīng)的單機(jī)排序模型，并對(duì)目標(biāo)函數(shù)為極小化最大完工時(shí)間，完工時(shí)間之和，超前遲后，多目標(biāo)函數(shù)以及一些經(jīng)典的目標(biāo)函數(shù)的情況進(jìn)行了研究.并分別給出了最優(yōu)算法. (2)針對(duì)流水作業(yè)排序問(wèn)題，首先研究了目標(biāo)函數(shù)為最大完工時(shí)間和完工時(shí)間之和的情況，給出了相應(yīng)問(wèn)題的近似算法并分析了其性能