帶有交貨期和加工時間可控的單機排序問題答辯稿

專業(yè)：機械設(shè)計制造及其自動化 姓名： 西北工業(yè)大學(xué)明德學(xué)院 2010級本科生畢業(yè)設(shè)計答辯 題目： 帶有交貨期和加工時間可控的單機排序問題 任務(wù)：討論了帶有交貨期和工件的加工時間可控的單機排序問題。本文首先根據(jù)最優(yōu)排序的性質(zhì)確定了最優(yōu)資源的分配方法，并將問題轉(zhuǎn)化為指派問題 $通過構(gòu)造多項式時間算法確定最優(yōu)排序。 論文工作安排 第一章 緒 論 第二章 單機排序問題的建模 第三章 仿真與分析 第四章 總結(jié)與展望 第一章 緒 論 1.1課題研究的背景和意義 1.2課題研究的目的意義和主要內(nèi)容 1.3本章小結(jié) 近年來帶有可控加工時間的排序問題受到越來越多的關(guān)注。加工時間可控是指工件的實際加工時間是一個依賴資源量的函數(shù)。 在交貨期問題中若工件在交貨期中完工則不產(chǎn)生懲罰費用若工件在交貨期之前或之后完工則會產(chǎn)生提前或延誤的費用。 排序又稱調(diào)度 ,作為運籌學(xué)的一個分支 ,是一門應(yīng)用性很強的學(xué)科 ,有著其深刻的實際背景和廣泛的應(yīng)用空間。在現(xiàn)代企業(yè)競爭中，準(zhǔn)時生產(chǎn)已經(jīng)成為一種重要的競爭策略。根據(jù)準(zhǔn)時生產(chǎn)原則，工件的完工時間要盡量地靠近某一時刻（時間段）。如果工件在該時刻（時間段內(nèi)）完工，就不會產(chǎn)生懲罰 ； 如果工件在該時刻（時間段）之前或之后完工，就會產(chǎn)生提前或者延誤的懲罰，這就是工期問題（工期窗口問題）。同時為提高機器的生產(chǎn)效率，可以考慮在機器上執(zhí)行維修。本文主要討論的是帶有交貨期和加工時間可控的單機排序問題。 排序 (scheduling)問題是一類重要的組合優(yōu)化問題，它產(chǎn)生的背景主要是機器制造，后來在管理科學(xué)、計算機控制、硬件設(shè)計、生產(chǎn)調(diào)度和工程技術(shù)等很多領(lǐng)域應(yīng)用非常廣泛。 排序間題是一類重要的組合最優(yōu)化問題，因為排序問題中所涉及的機器、工件都是有限的，絕大多數(shù)的排序問題是從有限個可行解中找出一個最優(yōu)解，使得目標(biāo)函數(shù)達到極小。在排序問題中我們稱可行解為可行排序，稱最優(yōu)解稱最優(yōu)排序。 排序問題是組合最優(yōu)化學(xué)科的重要組成部分之一。一個醫(yī)院門診 ,大家是按照時間先來后到排序 ,還是按照病情輕重緩急排序 ；一個大型工程 ,各種機械設(shè)備是按照機器運行成本排序 ,還是按進度需要排序 ；一個工件加工車間 ,工件加工是按照資源利用率排序 ,還是按照完工期限排序 ,這些都要涉及排序問題。 排序問題普遍應(yīng)用于生產(chǎn)管理、運輸調(diào)度、計算機系統(tǒng)等領(lǐng)域，引起許多專家學(xué)者的廣泛關(guān)注，并以實際生產(chǎn)活動為基礎(chǔ)進行理論研究。 第二章 單機排序問題的建模 2.1 單機排序 2.2 應(yīng)用舉例及計算結(jié)果 。 J r Jp p r1 ( )J r Jp p r f c現(xiàn)給出單機排序的一般描述。設(shè)有 n個工件 J1， J2， ， Jn， 工件 Jj的權(quán)為 uj，工件 Jj的工期為 dj。若工件 Jj排在第 r個位置加工，則其加工時間為 ， j=1， 2， ， n。其中 pJ為工件 Jj的正常計算共時間，其單機排序問題可記為 。 。 設(shè)有 n個工件 J1， J2， ， Jn在一臺機器上加工。全部零件零時刻到達，加工不可中斷，且機器在同一時間只能加工一個工件。工件 Jj的時間加工時間 Pj（ j=1, ,n）是一個依賴資源量的線性非增函數(shù)。 顯而易見，最優(yōu)排序滿足工件的開始加工時間從零時刻開始，且機器沒有空閑。 () jaj r j jjp x p r u x( ) ( )jaj kjrjprpxx Lu Yuan-yuan等討論了具有具有學(xué)習(xí)效應(yīng)的加工時間可控的單機排序問題 ,1） 2） 。 本文討論的是工件的加工時間是資源分配的線性函數(shù)的單機排序問題及與位置相關(guān)的加工時間可控問題。給出了最優(yōu)排序的一些性質(zhì)，及最優(yōu)資源分配的求解方法、多項式算法，證明了這些問題在多項式時間內(nèi)可以求得最優(yōu)解。 第三章 仿真與分析 3.1 車間調(diào)度仿真 3.2 仿真調(diào)度的原理和特點 3.3 仿真的基本方法 3.4 實例仿真 3.5 本章小結(jié) 車間資源的有限性制約著能否有效利用車間現(xiàn)有資源完成任務(wù) ,以最快的速度響應(yīng)市場需求 ,促使制造型企業(yè)能否贏得市場競爭。調(diào)度任務(wù)是根據(jù)生產(chǎn)目標(biāo)和約束，為每個加工對象確定具體的加工路線、時間、機器和操作等。優(yōu)良的調(diào)度策略對于提高生產(chǎn)系統(tǒng)的最優(yōu)性、提高經(jīng)濟效益都有著極大的作用。 車間生產(chǎn)調(diào)度問題是調(diào)度問題的一個子集?？梢悦枋鰹?:個工件在臺機器上加工 ,一個工件分為道工序 ,每道工序可以在若干臺機器上加工。 在實際的制造企業(yè)車間生產(chǎn)環(huán)境中，更普遍的調(diào)度類型應(yīng)當(dāng)是具有 Job-shop調(diào)度和動態(tài)調(diào)度屬性的混合類型，車間調(diào)度問題主要具有以下幾個特點。（ 1）復(fù)雜性。（ 2）動態(tài)隨機性。（ 3）多目標(biāo)性。 （ 4）多約束性。 制造系統(tǒng)的調(diào)度問題是在制造資源、加工工藝等約束條件下 ,尋求一組控制和決策變量，使得某個目標(biāo)達到或接近最優(yōu)。優(yōu)化理論方法用一組等式或不等式表示這種約束關(guān)系，通過推導(dǎo)和計算確定使目標(biāo)函數(shù)最優(yōu)的決策變量值，具有很好的優(yōu)化效果。但是當(dāng)調(diào)度問題比較復(fù)雜時，數(shù)學(xué)模型可能非常復(fù)雜，計算量大，也可能出現(xiàn)無解的現(xiàn)象。 仿真調(diào)度的基本原理是，建立仿真調(diào)度模型，在仿真調(diào)度決策規(guī)則的引導(dǎo)下，在模型上試探性地經(jīng)歷整個加工過程，記錄該過程中系統(tǒng)的狀態(tài)變化，統(tǒng)計、處理并產(chǎn)生調(diào)度方案和性能數(shù)據(jù)。因此仿真調(diào)度方法實際上是一種實驗性和試探性的方法，不會出現(xiàn)無解的現(xiàn)象。 離散事件系統(tǒng)仿真中仿真進程的推進方法是十分重要的。應(yīng)用任何一種方法都應(yīng)考慮如何選擇下一事件，以便執(zhí)行相應(yīng)的程序模塊來修改系統(tǒng)狀態(tài)，進行各種統(tǒng)計計算。根據(jù)處理的方法不同， 可將離散事件仿真分成三類，（ 1）事件調(diào)度法。（ 2）活動掃描法。（ 3）進程交互法。 第四章 總結(jié)與展望 排序問題起源于制造業(yè)，作為運籌學(xué)的一個分支，發(fā)展非常迅速。近年來，排序問題已發(fā)展成為運籌學(xué)、系統(tǒng)科學(xué)、管理科學(xué)和計算機科學(xué)等多個學(xué)科領(lǐng)域的一個交叉學(xué)科，有著深刻的實際背景和廣闊的應(yīng)用前景。在 20世紀(jì) 80年代以前，對于排序問題的研究主要集中在一些經(jīng)典模型上。近十多年來，出現(xiàn)了許多現(xiàn)代排序問題。這些現(xiàn)代排序間題突破了經(jīng)典模型的基本假設(shè)，具有更廣泛的實際應(yīng)用背景，同時也更為復(fù)雜。隨著各種實際問題的提出，現(xiàn)代排序問題不斷產(chǎn)生。盡管某些