本文是一篇生產(chǎn)管理論文，本文在考慮到常用的優(yōu)化目標(biāo)的基礎(chǔ)上，著重考慮了影響車間能耗的因素，包括機器的加工能耗、空轉(zhuǎn)能耗、調(diào)整能耗和工件的運輸能耗。建立了以最小化最大完工時間、總延期時間最短、機器總負(fù)荷最小和車間總能耗最低的柔性作業(yè)車間調(diào)度模型。
第 1 章  緒論
1.1  研究背景與意義
1.1.1  研究背景
在當(dāng)今全球化進程進一步加快和科技水平快速發(fā)展的環(huán)境下，各個企業(yè)之間的競爭也越發(fā)激烈，制造型企業(yè)想要得到較好的發(fā)展，一方面需要從生產(chǎn)技術(shù)方面進行突破，另一方面則需從精益生產(chǎn)角度去考慮，例如生產(chǎn)效率的提升，生產(chǎn)成本的降低。尤其在當(dāng)下原材料成本和人工成本都與日俱增的情況下，如何合理的利用現(xiàn)有的有限資源實現(xiàn)綠色和高效的生產(chǎn)成為熱點問題。
在傳統(tǒng)的生產(chǎn)車間中，生產(chǎn)產(chǎn)品所需的原材料和生產(chǎn)方式都較為單一，某一工件的某一工序僅能在確定的機器上進行加工，這種生產(chǎn)方式僅僅能完成特定的生產(chǎn)指標(biāo)，工藝也較為單一且無可選擇性，生產(chǎn)機器也同樣不具備多樣性，在當(dāng)今產(chǎn)品多樣化和顧客需求個性化的背景下，傳統(tǒng)的生產(chǎn)方式已很難滿足市場需求，而具有高靈活性、低風(fēng)險和柔性制造的生產(chǎn)單元更能滿足當(dāng)今需求。隨著柔性制造系統(tǒng)和數(shù)控加工機器等更為先進的生產(chǎn)單元的出現(xiàn)和發(fā)展，實現(xiàn)了單臺機器可以完成多種不同類型加工任務(wù)，同時也增強了生產(chǎn)調(diào)度的靈活性以及企業(yè)的抗風(fēng)險能力。但是也出現(xiàn)了柔性作業(yè)車間的調(diào)度問題，與傳統(tǒng)車間的調(diào)度問題相比具有更高的難度，求解此類問題可進一步提升生產(chǎn)效率和降低成本，所以對柔性作業(yè)車間調(diào)度問題的研究愈來愈受關(guān)注。
柔性車間調(diào)度的一個重要子方向是柔性作業(yè)車間調(diào)度，車間調(diào)度是生產(chǎn)決策的重要體現(xiàn)形式，其主要內(nèi)容是在現(xiàn)有的有限資源約束前提下，對各個加工工序進行合理的資源分配，以達到?jīng)Q策者的預(yù)期優(yōu)化效果。英格索爾的報告曾經(jīng)指出，如果執(zhí)行了一個不良的調(diào)度方案會造成大量的時間浪費，機器在執(zhí)行這個調(diào)度方案時，真正用于工件的加工時間僅僅占方案總體時間的 5%，而生產(chǎn)中的非加工環(huán)節(jié)如搬運、等待等時間占據(jù)了制造總時間的 95%[1]。由此，一個優(yōu)秀的調(diào)度方案可大幅降低生產(chǎn)制造過程中等待和搬運所消耗的時間，如此一方面可減少生產(chǎn)調(diào)度周期的時長，另一方面也可以有效降低在制造過程中消耗的能源。
1.2  國內(nèi)外研究現(xiàn)狀
在世界各地的工廠中都存在任務(wù)分配問題，即如何安排不同類型、不同負(fù)荷的任務(wù)給人和機器，于是出現(xiàn)了調(diào)度員這一職位來解決此類問題。Johnson[7]于 19 世紀(jì)50 年代開始研究車間的調(diào)度問題并取得了一定的成果。在以后一段時間，更多的研究者受到 Johnson 的啟發(fā)并對車間調(diào)度問題進行了更為深入的調(diào)查。在 19 世紀(jì) 70年代，有研究者指出三臺及以上的機器調(diào)度問題屬于 NP 問題。在諸多調(diào)度問題中，車間調(diào)度是非常典型的代表，吸引著更多的研究人員對車間調(diào)度問題進行了更加深入的探索。
當(dāng)前的車間調(diào)度問題大多是指某一工單下的待加工工件，車間擁有一些加工機器，每個機器負(fù)責(zé)加工工件的某一道工序，并且每個工件都需要在兩臺或以上的機器上進行加工[8]。自上世紀(jì)五十年代以來，生產(chǎn)調(diào)度問題在國內(nèi)外研究人員的共同努力下取得了在重大成果，尤其是在生產(chǎn)調(diào)度方法和調(diào)度算法方面的研究。以當(dāng)前的發(fā)展形勢來看，主要的生產(chǎn)調(diào)度算法有優(yōu)化的方法和啟發(fā)式的方法。通過對以上兩類方法的不斷深入研究，調(diào)度的不同分類也逐漸顯現(xiàn)了出來，主要分為單目標(biāo)的調(diào)度、多目標(biāo)的調(diào)度、傳統(tǒng)車間的調(diào)度、柔性車間的調(diào)度等。
柔性作業(yè)車間調(diào)度問題（Flexible Job Shop Scheduling Problem，F(xiàn)JSP）在具備了傳統(tǒng)車間調(diào)度問題特征的前提下，還具備了更為復(fù)雜的約束條件，F(xiàn)JSP 是在傳統(tǒng)車間調(diào)度問題的基礎(chǔ)上進行了更加深入的探索，其更為貼近當(dāng)前大多數(shù)車間的實際情況。隨著對車間調(diào)度的逐步深入研究，現(xiàn)已有大量的關(guān)于車間調(diào)度的研究，近年來FJSP 受到越來越多的關(guān)注，自 1990 年 Bruker 和 Schlies 對兩個工件的 FJSP 問題進行了相關(guān)研究后，有更多研究人員加入到該領(lǐng)域研究，解決此類問題方法逐步分為分步和集成兩種有效方法。分步法由 Brandimarte 率先提出，該方法的思想可總結(jié)為將復(fù)雜問題簡便化，通常來說就是將復(fù)雜的調(diào)度問題進行分解，分解后的問題難度會有所降低，然后可以對分解后的子問題進行求解，再尋得原始問題的解，比如在解決調(diào)度問題時將機器的分配和調(diào)度問題分開考慮如何解決，但這樣解決調(diào)度問題的后果是只能讓部分目標(biāo)達到最優(yōu)，而未從整體最優(yōu)的角度去解決調(diào)度問題，無法達成整體效果最優(yōu)；集成法的思路則是在運算過程中同時考慮這兩個問題，但是當(dāng)問題進一步復(fù)雜在進行大規(guī)模調(diào)度和同時考慮多個目標(biāo)時如何進行合理的編碼和解碼是難點所在。
第 2 章  多目標(biāo)柔性作業(yè)車間調(diào)度相關(guān)理論和求解方法
2.1  車間調(diào)度問題概述及分類
2.1.1  車間調(diào)度問題概述
調(diào)度問題就是在一定時間內(nèi)，對有限的資源進行合理的分配和對項目任務(wù)的排序進行確定，使其達到預(yù)設(shè)或較滿意的結(jié)果。車間調(diào)度問題對于企業(yè)來說愈來愈重要，是企業(yè)管理和生產(chǎn)計劃的關(guān)鍵所在，它可以提升企業(yè)生產(chǎn)效率，降低機器損耗，減少資源浪費，為企業(yè)在相關(guān)行業(yè)的激烈競爭中奠定成功基礎(chǔ)，所以對車間調(diào)度問題進行研究就顯得越來越重要。對于車間調(diào)度問題來說，可以將其做如下描述：有????個包含????道工序的工件需要在????臺機器上完成加工，在符合全部的約束條件情況下，待加工工件的任意工序可以選擇在符合加工要求的機器上進行加工，所有機器在相同的時間段內(nèi)僅可對某工件的一道工序進行加工，所有的工件均需要在上道工序加工完成后進行未加工工序的加工[45]。
2.1.2  車間調(diào)度問題分類
在對調(diào)度問題的研究過程中發(fā)現(xiàn)實際的制造型企業(yè)存在不同的生產(chǎn)方式，因此車間調(diào)度問題也有了不同分類，根據(jù)加工系統(tǒng)特點來劃分，車間調(diào)度問題被分為以下幾種類型：
1)作業(yè)車間調(diào)度問題（Job  Shop  Scheduling  Problem，JSSP）：車間內(nèi)有多臺功能與性能不同的機器，各工件的工序數(shù)不同，工件內(nèi)存在先后次序的約束，工件間則不存在，每道工序在開始加工前需選定加工機器，但不相同的工件加工路線可以是不同的[46]。
2)流水車間調(diào)度問題（Flow Shop Scheduling Problem，F(xiàn)SP）：車間內(nèi)有多臺功能與性能不同的機器，所有待加工工件的工序數(shù)量相同，所有工件的各工序有先后約束關(guān)系，每道工序的加工機器均是確定且唯一的，所有工件的加工工藝流程均相同[47]。
3)并行機車間調(diào)度（Parallel  Machine  Scheduling  Problem，PMP）：車間內(nèi)有多臺功能與性能相同的機器，所有待加工工件僅僅有一道工序，所有工件可以在任何一臺機器上完成加工。
2.2  柔性作業(yè)車間調(diào)度問題
車間調(diào)度是調(diào)度問題的子問題，其從本質(zhì)上來說是解決資源的分配問題，由于其存在諸多約束條件，使得該問題成為典型的組合優(yōu)化難題。
柔性作業(yè)車間問題可描述為，所有待加工工件至少含有兩道及兩道以上工序，工件的工序數(shù)和順序都已知，工件的工序需提前分配好負(fù)責(zé)加工的機器，因為加工時長會受到選擇機器的影響。確定調(diào)度方案的目的是要確定每臺機器所要加工的工序數(shù)以及每道工序在哪臺機器上進行加工，來達到總體性能指標(biāo)最優(yōu)的目的。因此機器的選擇和工序的排序兩個子問題共同構(gòu)成了柔性作業(yè)車間調(diào)度問題。假如在某一調(diào)度周期內(nèi)有????(???? = 1,2, … , ????)個待加工工件在????(???? = 1,2, … , ????)臺機器上進行加工，某一工件工序情況用????????????來表示，????表示工件數(shù)，????表示工序數(shù)。
除此之外，還需滿足以下條件: 1)在調(diào)度周期內(nèi)任何時刻機器都存在單一約束，即相同的時間只能加工一個工件的一個工序； 2)工件在加工時存在不可中斷的約束條件，開始加工直至結(jié)束加工期間不能有中斷； 3)同一工件的所有工序都存在先后關(guān)系； 4)不同的工件間則不存在先后約束關(guān)系； 5)全部工件的加工優(yōu)先級均相同； 6)所有機器都在 0 時刻啟動。
3 個工件在 4 臺機器上進行調(diào)度的 FJSP 如下表 2-1 所示： 第 3 章   中石油 SGZB 機械加工車間調(diào)度模型建立 ........................ 17
3.1   企業(yè)概況 ................................... 17
3.2   機械加工車間生產(chǎn)調(diào)度問題分析 ........................... 18
第 4 章   NSGA-Ⅱ算法的改進和測試 ................................. 25
4.1   NSGA-Ⅱ算法的基本理論 ........................................... 25
4.1.1   NSGA-Ⅱ算法的基本要素 ...................... 25
4.1.2   NSGA-Ⅱ算法的基本流程 .................................... 29
第 5 章   基于改進 NSGA-Ⅱ求解調(diào)度實例 ................................ 45
5.1   中石油 SGZB 中心機械加工車間調(diào)度實例 ............................. 45
5.2   改進 NSGA-Ⅱ?qū)嵗Ｐ颓蠼?.................................... 45
第 5 章  基于改進 NSGA-Ⅱ求解調(diào)度實例
5.1  中石油 SGZB 中心機械加工車間調(diào)度實例
通過對中石油 SGZB 中心機械加工車間調(diào)研得到該車間加工數(shù)據(jù)為方便調(diào)度的實現(xiàn)將生產(chǎn)數(shù)據(jù)進行取整處理。中石油 SGZB 中心機械加工車間主要為內(nèi)焊機和外焊機裝配所需零部件進行加工，共設(shè)有 8 臺加工機器，加工 8 種不同工件，每個工序在不同機器上的加工時間、機器調(diào)整所需能耗如表 5-1 所示： 結(jié)論
本文在傳統(tǒng)的車間調(diào)度算法的基礎(chǔ)上，以實際的車間生產(chǎn)情況為依據(jù)建立了柔性作業(yè)車間調(diào)度模型，針對車間所出現(xiàn)的問題從多個方面進行考慮并優(yōu)化包括最大完工時間、總延期時間、機器總負(fù)荷和車間總能耗，并根據(jù)中石油 SGZB 中心機械加工車間實際生產(chǎn)情況發(fā)現(xiàn)在調(diào)度過程中所存在的一些問題，針對所發(fā)現(xiàn)問題對NSGA-Ⅱ算法進行改進，并用車間實際生產(chǎn)數(shù)據(jù)與改進前的調(diào)度方案作對比，驗證了所改進算法的有效性和可行性，在經(jīng)過改進的算法得到最優(yōu)的 Pareto 解集后再運用層次分析的方法從中選取出最優(yōu)的方案，最后開發(fā)出車間調(diào)度原型系統(tǒng)，為車間的生產(chǎn)調(diào)度提供一定參考，同時也證明了本文的實際應(yīng)用價值。
本文主要工作和成果如下所示：
(1)  考慮多個影響車間能耗的因素
以往對車間調(diào)度問題的研究常常以最短時間為優(yōu)化目標(biāo)，本文在考慮到常用的優(yōu)化目標(biāo)的基礎(chǔ)上，著重考慮了影響車間能耗的因素，包括機器的加工能耗、空轉(zhuǎn)能耗、調(diào)整能耗和工件的運輸能耗。建立了以最小化最大完工時間、總延期時間最短、機器總負(fù)荷最小和車間總能耗最低的柔性作業(yè)車間調(diào)度模型。
(2)   改進 NSGA-Ⅱ算法
對 NSGA-Ⅱ算法做出了改進。改進后的算法采用自適應(yīng)的交叉概率和變異概率可有效地防止算法提前陷入局部最優(yōu)，采用混合交叉方案和混合變異方案和改進精英保留策略可以有效的提高種群多樣性，將以上方法同時用于 NSGA-Ⅱ算法的改進可彌補標(biāo)準(zhǔn) NSGA-Ⅱ算法的缺點。
參考文獻（略）