工件加工時間可變的現(xiàn)代排序問題.pdf

1、本文研究工件加工時間可變的現(xiàn)代排序問題,主要在如下幾個方面做了一些工作:1.工件加工時間是開工時間的增加函數(shù)的排序問題.(a)最大完工時間單機(jī)排序問題.對于一般模型中工件具有有跟森林約束和有串并有向圖約束的極小化最大完工時間單機(jī)問題分別給出了最優(yōu)算法.(b)加權(quán)完工時間和單機(jī)排序問題.對增長率與基本加工時間相關(guān)且工件具有有跟森林約束和有串并有向圖約束的的單機(jī)問題進(jìn)行研究,分別給出了最優(yōu)算法.(c)流水作業(yè)排序問題.對機(jī)器間滿足優(yōu)勢關(guān)系的

2、不等待或無空閑問題進(jìn)行研究,目標(biāo)函數(shù)分別為最大完工時間、加權(quán)完工時間和與最大延誤,對它們分別給出了最優(yōu)算法.2.工件加工時間是開工時間的減少函數(shù)的排序問題.(a)單機(jī)排序問題.研究遞減率與基本加工時間相關(guān)的單機(jī)問題,對最大完工時間問題、加權(quán)完工時間和問題、工件具有平行鏈約束的加權(quán)完工時間和問題、最大費用問題與最大延誤問題分別給出了最優(yōu)算法.(b)流水作業(yè)排序問題.對兩臺機(jī)器極小化最大完工時間問題,證明了利用Johnson規(guī)則可以求得最優(yōu)

3、排序.對工件各工序基本加工時間均相等的流水作業(yè)問題進(jìn)行了研究,并對某些情況給出了明確結(jié)論.3.加工時間可控的單機(jī)可控排序問題.首先,研究加工時間一般可控的排序問題,目標(biāo)函數(shù)分別為極小化完工時間和、完工時間偏差和與壓縮費用的線性組合,等待時間和、等待時間偏差和與壓縮費用的線性組合,提前時間、延誤時間、工期與壓縮費用的線性組合.所有這些問題都可轉(zhuǎn)化為指派問題,從而多項式時間可解.其次,研究加工時間離散可控的排序問題,對幾類多目標(biāo)問題進(jìn)行了轉(zhuǎn)