帶有交貨期和加工時(shí)間可控的單機(jī)排序問(wèn)題答辯稿

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