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