帶有安裝時間的單機(jī)成組排序問題.pdf

1、排序問題也稱調(diào)度問題，是組合最優(yōu)化中的一個重要分支.排序問題的一大特點是：模型繁多，適用于某一模型的算法，只要將模型的條件稍加變化，該算法即可能不適用.在許多排序問題中，安裝時間通常假設(shè)為常數(shù)，但在現(xiàn)實中，安裝時間往往不是獨立存在的，往往需要受加工時間的影響，因而研究和已經(jīng)加工完工件的加工時間有關(guān)的安裝時間的單機(jī)成組排序問題顯得尤為重要.在這一排序模型中，工件的加工不可中斷、工件組的安裝時間是和已經(jīng)加工完工件的加工時間有關(guān)的連續(xù)函數(shù).本

2、文主要對帶有安裝時間的單機(jī)成組排序問題進(jìn)行了討論. 本文首先介紹了排序問題的定義、表示方法及分類，帶有有安裝時間的排序問題和單機(jī)成組排序問題的研究成果和發(fā)展情況.然后對帶有安裝時間的單機(jī)成組排序問題進(jìn)行了討論.在本文的第二章中，主要討論了帶有安裝時間和準(zhǔn)備時間的單機(jī)成組排序問題，其中每個工件都具有自己的準(zhǔn)備時間，組和組之間具有安裝時間，并且安裝時間和已經(jīng)加工完工件的加工時間有關(guān).所有工件在機(jī)器上加工時，一次只能加工一個工件，工件

3、不可中斷，組內(nèi)工件連續(xù)加工，組和組之間需要安裝時間，對目標(biāo)函數(shù)為極小化最大完工時間的單機(jī)成組排序問題，給出了求解最優(yōu)排序的多項式算法，并利用具體例子對算法的應(yīng)用做出解釋.第三章討論了帶有安裝時間和加工時間受資源約束的單機(jī)成組排序問題，其中包括兩個問題.一個問題是在資源消耗量受限條件下極小化最大完工時間的最優(yōu)排序和資源分配方法，另一個問題是目標(biāo)函數(shù)在滿足資源消耗總量限制條件下極小化最大完工時間的最優(yōu)排序和資源分配方法.在這兩個問題中，同一