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

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

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

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