幾類交貨期指派的排序問題.pdf

1、作為一門應(yīng)用科學(xué)，排序問題有著廣闊的應(yīng)用前景，它主要應(yīng)用于機(jī)械制造領(lǐng)域，后來被廣泛應(yīng)用于工程技術(shù)，交通運(yùn)輸，計(jì)算機(jī)科學(xué)等眾多行業(yè)。隨著工業(yè)的快速發(fā)展，排序問題的模型不斷突破。在一些排序模型中，工件在規(guī)定的交貨期前完工需要儲(chǔ)存，產(chǎn)生一定費(fèi)用；在交貨期后完工要引發(fā)消費(fèi)懲罰。在排序問題中交貨期指派問題是重要因素之一。本文將討論三種不同的交貨期指派問題。具體內(nèi)容概括如下：
　　1.討論帶有公共交貨期的排序問題。工件的加工時(shí)間是與工件在排序

2、中的位置、資源分配、維修活動(dòng)的位置和工件的開始加工時(shí)間有關(guān)的函數(shù)。目標(biāo)是確定工件的最優(yōu)排序、最優(yōu)的資源分配、最優(yōu)的維修位置和最優(yōu)的交貨期指派，使得總目標(biāo)函數(shù)值最小。將該問題歸結(jié)為指派問題，得到了一個(gè)最優(yōu)算法，其時(shí)間復(fù)雜性為O?n4?。
　　2.討論帶有多個(gè)交貨期窗口的單機(jī)排序問題，且工件的加工時(shí)間是退化的。研究了兩種目標(biāo)函數(shù)，第一種是帶有提前、延誤、最大完工時(shí)間及交貨期的開始位置與大小的總費(fèi)用；第二種是帶有提前、延誤、所有工件完工