【文章內(nèi)容簡介】 標(biāo)上達(dá)到所需要的理想點。本文研究的是車間調(diào)度問題，空間和時間上存在某種約束，而要求某些目標(biāo)達(dá)到最優(yōu)化效果，例如最小完工時間、最小拖期懲罰、最小費用等等，車間調(diào)度問題一般屬于NP難問題，他要滿足非常復(fù)雜的約束條件，來進行組合優(yōu)化。 車間調(diào)度問題的特點在實際生產(chǎn)中，車間調(diào)度問題會面臨很復(fù)雜的情況，比如訂單的動態(tài)產(chǎn)生，機器加工故障，人為的隨機控制等等，這都是我們所要解決的問題。所以車間調(diào)度有以下的幾個特點[14]：（1）復(fù)雜性車間調(diào)度問題一般都屬于NP難的復(fù)雜問題，其原因主要有：生產(chǎn)因素的復(fù)雜性，工件、機器、工人等都是相互影響的個體，有其要考慮的非常眾多的因素，比如工件要考慮他的加工時間，交貨時間，庫存大小等因素，而機器要考慮加工能力，維護，故障等因素，如果再加入動態(tài)調(diào)度，那問題將更加復(fù)雜；調(diào)度問題的復(fù)雜性，隨著他的發(fā)展，已經(jīng)從單目標(biāo)向多目標(biāo)轉(zhuǎn)換，而每多一個目標(biāo)，其計算量就有可能是指數(shù)級別的增長，常規(guī)的方法即使能取得最優(yōu)解，計算時間也是我們所不可估量的。（2）動態(tài)性生產(chǎn)過程中，有很多隨機的突發(fā)的因素，比如有不可延遲的急需訂單到達(dá)（包括軍需、應(yīng)急物資等）、機器的故障和修理、工人操作失誤等等，都需要我們對調(diào)度方案進行調(diào)整，這也從一方面增加了調(diào)度問題的復(fù)雜性。（3）多目標(biāo)單目標(biāo)的調(diào)度問題已經(jīng)不適合現(xiàn)在的實際調(diào)度問題了，傳統(tǒng)的加工時間最小化問題往往是要犧牲其他一些利益的，比如超過交貨期而影響企業(yè)業(yè)務(wù)，過早生產(chǎn)產(chǎn)生庫存費用，趕時間導(dǎo)致生產(chǎn)成本增加，機器生產(chǎn)能力不同導(dǎo)致機器空閑浪費資源等等。目前基于多目標(biāo)優(yōu)化的調(diào)度問題層出不窮，不僅要求完工時間小，經(jīng)常設(shè)計的目標(biāo)問題還包括：最小拖期懲罰，最小生產(chǎn)費用，最大化設(shè)備利用率等，雖然這些目標(biāo)會存在沖突，但是對于現(xiàn)如今的調(diào)度問題不可避免。（4）多約束這是調(diào)度問題產(chǎn)生的很大一個動力，正是因為生產(chǎn)過程中存在大量的約束，調(diào)度問題才有實際意義。一般調(diào)度問題考慮的因素包括：機器的生產(chǎn)能力，緩存（可以考慮為庫存）的大小約束，工件的加工順序，運輸工具的能力約束，訂單的交貨約束等。 平行機的調(diào)度問題簡介 最經(jīng)典的調(diào)度問題可以描述為：有m（，……，）臺機器和n（，……，）個工件，每個工件對應(yīng)的加工時間t（，……，）。機器和工件隨時都可以加工，但是每個工件只可以在一個機器上加工，而且中間不能夠停止，目標(biāo)就是最小化完工時間。機器通?？梢苑譃閮纱箢悾浩叫袡C和串聯(lián)機。由以上經(jīng)典問題的模型可知，一個工件只需要在m臺機器中的任何一臺上加工，不間斷一次就可以完成任務(wù)。但是如果在串聯(lián)機上加工，則必須在每臺機器上都加工一次才可以完成任務(wù)。 目前平行機的種類主要有以下幾種： 同型平行機（identical parallel machines），即所有的機器加工速度一樣。 同類平行機（uniform parallel machines），即機器雖然有不同的加工速度，但是各個機器的加工速度之間有著相同的比例關(guān)系。 不同類平行機（unrelated parallel machines），即機器的加工速度既不一樣，各個機器的加工速度之間也沒有比例關(guān)系。 串聯(lián)機也可以分為三類： 流水作業(yè)（flow shop），即每個工件都要以各自特定的同樣的順序在機器上加工。 自由作業(yè)（open shop），即工件的加工次序可以任意。 異序作業(yè)（job shop），即每個工件以各自特定的順序在機器上加工。 本文結(jié)合文[6]提出的單目標(biāo)生產(chǎn)調(diào)度模型和文[15]提出的模型上再進行改進，提出在供應(yīng)鏈環(huán)境下的同型平行機的多目標(biāo)生產(chǎn)調(diào)度模型。 多目標(biāo)優(yōu)化問題的基本概念從多目標(biāo)優(yōu)化問題的出現(xiàn)到現(xiàn)在，他的發(fā)展迅速，成為了最優(yōu)化問題的一個重要分支。簡單的說就是在約束條件下，多個數(shù)值目標(biāo)同時優(yōu)化的問題。以在一組約束條件下，最小化多目標(biāo)問題為例，多目標(biāo)優(yōu)化問題（Multiobjective Optimization Problem ，MOP）可以描述為下面的形式[12]：式中：為帶有p個決策變量的向量，組成決策空間；為帶有m個目標(biāo)函數(shù)的向量，組成目標(biāo)空間；為n個不等式約束函數(shù)，由它們形成了可行解區(qū)域。在1896年，也第一次出現(xiàn)了pareto最優(yōu)的概念[12]。從此，學(xué)者們便逐步開始了對多目標(biāo)優(yōu)化問題的研究。從20世紀(jì)50年代開始，多目標(biāo)優(yōu)化方法層出不窮，Kulm，Arrow，Karlin，Chame，Polak，Kceney，Klingcr和Geoffrion等都做出了相應(yīng)的貢獻(xiàn)，出現(xiàn)了加權(quán)和法、目標(biāo)規(guī)范法、ε約束法等基于權(quán)重的多目標(biāo)優(yōu)化算法。 供應(yīng)鏈環(huán)境下并行機生產(chǎn)調(diào)度模型 模型的變量描述 假設(shè)制造商H有m臺平行機機器，為，……，n個工件，為，……，可以記為N＝｛1，2，……，n｝，每一個工件都有不同的加工時間，可以記為T＝｛，……，｝，每一個工件完成后都會在制造企業(yè)產(chǎn)生一個庫存量，記為S＝｛，……，｝，在制造商就會產(chǎn)生一個庫存費用，直到工件被運走，制造商的庫存能力有限，上限為。而在下游有一個第三方物流商，從制造商將工件運至到交給最后的客戶，也會有一個庫存費用。車輛的運輸能力有限，設(shè)為a，從制造商到達(dá)物流商的時間為常數(shù)。用表示工件n在機器m上的開工時刻，表示工件n在機器m上的完工時刻，將時刻從小到大順序依次賦給，i＝｛1，2，……，n｝。表示時刻制造商的庫存量。 數(shù)學(xué)符號表表示工件n的加工時間表示工件n到達(dá)物流商的時間表示工件n的庫存量取1表示工件n在機器m上加工取0表示工件n不在機器m上加工車輛從制造商到物流商的運輸時間，可以認(rèn)為是常數(shù)表示工件n在機器m上的開工時刻表示工件n在機器m上的完工時刻w第一件工件開始加工到最后一批工件運送至下流物流商然后車輛返回制造商的總時間表示制造商工件n的交貨期表示物流商工件n的交貨期 數(shù)學(xué)模型 對于加工有如下的假設(shè)： （1）工件的加工時間是預(yù)知固定的。 （2）工件必須被連續(xù)加工，不允許中斷。 （3）每臺機器同一時間只能加工一個工件。 （4）在零時刻，每個工件都允許被加工。 （5）同一臺機器上兩個工件的加工，可以沒有間隔，即便有間隔，也被 考慮到工件的加工時間之內(nèi)。 （6）直到工件加工完才產(chǎn)生庫存。 （7）庫存能力有限。 （8）運輸能力有限，必須在運輸能力范圍之內(nèi)運輸。 （9）假設(shè)每個工件的庫存量肯定小于運輸能力，在車輛返回制造商前， 物流商的庫存要小于b。 （10）不同的工件雖然可以同一批次運輸，但是同一批工件不能被分開運 輸 根據(jù)模型的描述，建立以下數(shù)學(xué)模型： （2. 1） （2. 2） （2. 3） （2. 4） . （2. 5） （2. 6） （2. 7） （2. 8） （2. 9） 其中表示制造商提前完工的懲罰系數(shù)（這個系數(shù)可以理解為制造商單位天數(shù)的庫存費用），表示制造商延期交貨的懲罰系數(shù)，表示物流商提前到貨的懲罰系數(shù)（這個系數(shù)可以理解為物流商單位天數(shù)的庫存費用），表示物流商延期交貨的懲罰系數(shù)， 表示運輸次數(shù)，當(dāng)庫存量超出上限時，要及時的運輸，但是要保證在運輸能力之內(nèi)。 ，。約束條件中，而且同一時間，一個工件只能在一個機器上生產(chǎn)，一臺機器只能生產(chǎn)一個工件。該類問題可以用五參數(shù)法[21]法表示： 式中表示生產(chǎn)階段有多臺平行機，且目的地只有一個，表示運輸能力有限，上限為a，表示不同的訂單產(chǎn)品可以在同一批次運送，表示目標(biāo)函數(shù)。 本章小節(jié) 本章首先介紹了供應(yīng)鏈和供應(yīng)鏈協(xié)同的相關(guān)概念，接著介紹了車間調(diào)度以及多目標(biāo)優(yōu)化的基本理論，并在其中著重介紹第三方物流和平行機調(diào)度概念，并且以此為背景來提出生產(chǎn)調(diào)度模型：基于供應(yīng)鏈環(huán)境的多目標(biāo)平行機生產(chǎn)調(diào)度模型。 第三章 多目標(biāo)調(diào)度問題的求解 多目標(biāo)優(yōu)化算法簡介 傳統(tǒng)多目標(biāo)優(yōu)化算法簡介很多傳統(tǒng)的多目標(biāo)優(yōu)化算法沒有太多的多目標(biāo)概念，只是經(jīng)過數(shù)學(xué)改良，又轉(zhuǎn)換成了單目標(biāo)優(yōu)化算法，采用比較成熟的單目標(biāo)優(yōu)化算法來求解，比如，分層序列法，評價函數(shù)法，目標(biāo)規(guī)劃方法等等。傳統(tǒng)多目標(biāo)優(yōu)化算法中有很多經(jīng)典算法，比如：加權(quán)求和法：該方法就是將多目標(biāo)問題中的各個目標(biāo)函數(shù)增加權(quán)重，即在各個目標(biāo)函數(shù)上再乘以權(quán)重系數(shù)，轉(zhuǎn)化為單目標(biāo)問題來求解。優(yōu)點：這種方法將多目標(biāo)問題轉(zhuǎn)化為單目標(biāo)問題，將問題簡化，在Pareto最優(yōu)前端為凸的問題中，可以確定得到Pareto最優(yōu)解。缺點：關(guān)鍵是權(quán)重的選取，而且在搜索空間非凸時，很難求得Pareto最優(yōu)解。ε約束法：該方法是將目標(biāo)中的某個目標(biāo)作為優(yōu)化目標(biāo)，而將其他目標(biāo)函數(shù)約束住來求解的優(yōu)化方法。優(yōu)點：該方法可以找到不同的Pareto最優(yōu)解。缺點：約束選中目標(biāo)外的其他目標(biāo)的參數(shù)非常困難，有可能導(dǎo)致沒有可行解或者其他目標(biāo)的約束不起作用。等式約束法：該方法與ε約束法類似，也是從多目標(biāo)優(yōu)化問題中選取其中一個目標(biāo)函數(shù)進行優(yōu)化，而約束其他目標(biāo)函數(shù)。優(yōu)點：只要選取合適的其他目標(biāo)的約束參數(shù)，也可以獲得不同的Pareto最優(yōu)解。缺點：很多等式約束問題都不存在可行解，而且即使存在可行解，也不一定是Pareto最優(yōu)解。最小—最大法：這種方法起源于博弈論，是通過最小化各個目標(biāo)函數(shù)值與預(yù)設(shè)的目標(biāo)之間的最大偏移量來求得多目標(biāo)最優(yōu)解的方法，當(dāng)初設(shè)計的初衷是為求解有沖突的目標(biāo)函數(shù)。 調(diào)度規(guī)則、組合規(guī)則與啟發(fā)式算法 （1）調(diào)度規(guī)則與組合規(guī)則 在傳統(tǒng)的生產(chǎn)調(diào)度領(lǐng)域和組合優(yōu)化領(lǐng)域存在大量成熟的調(diào)度規(guī)則或組合調(diào)度規(guī)則。基于現(xiàn)有的規(guī)則和實際生產(chǎn)環(huán)境中的經(jīng)驗知識，設(shè)計針對供應(yīng)鏈環(huán)境生產(chǎn)調(diào)度問題的的調(diào)度規(guī)則或組合調(diào)度規(guī)則，同時分析各類規(guī)則的原理及其對系統(tǒng)性能的影響。這種方法一般求解效率較高、針對性強且有助于分析調(diào)度問題的本質(zhì)和優(yōu)化機理，也可用來構(gòu)造智能算法的初始解，但它同時也存在設(shè)計難度大、擴展性低的缺點。（2）啟發(fā)式算法 供應(yīng)鏈下生產(chǎn)調(diào)度問題大多屬于NP難問題，而由于制造業(yè)的生產(chǎn)調(diào)度問題規(guī)模一般比較龐大，所以設(shè)計啟發(fā)式算法成為求解該類問題的主流?；诟鞣N調(diào)度規(guī)則和實際生產(chǎn)環(huán)境的經(jīng)驗知識，設(shè)計供應(yīng)鏈下生產(chǎn)調(diào)度問題的啟發(fā)式算法，并在可以已知精確解的小規(guī)模問題中驗證啟發(fā)式算法的有效性，同時也可以將啟發(fā)式算法的結(jié)果作為其它算法（比如多目標(biāo)智能算法）的初始解。此種方法的優(yōu)劣性質(zhì)和規(guī)則相似。 多目標(biāo)智能算法供應(yīng)鏈下的生產(chǎn)調(diào)度問題大多為約束類多目標(biāo)問題，若想求解該類問題的Pareto解集，傳統(tǒng)的多目標(biāo)算法或啟發(fā)式算法通常難以勝任，尤其對于問題規(guī)模較大的制造業(yè)來說。而基于Pareto解的多目標(biāo)遺傳算法和多目標(biāo)粒子群算法已經(jīng)被驗證可以比較好的解決此類問題。（1）基于Pareto解的多目標(biāo)遺傳算法（進化算法）遺傳算法（GeneticAlgorithms）是基于生物進化理論的原理發(fā)展起來的一種廣為應(yīng)用的、高效的隨機搜索與優(yōu)化的方法。其主要特點是群體搜索策略和群體中個體之間的信息交換，搜索不依賴于梯度信息。遺傳算法是解決搜索問題的一種通用算法，對于各種通用問題都可以使用。搜索算法的共同特征為：①首先組成一組候選解（隨機生成或由其它算法產(chǎn)生）；②依據(jù)某些適應(yīng)性條件測算這些候選解的適應(yīng)度；③根據(jù)適應(yīng)度保留某些候選解，放棄其他候選解；④對保留的候選解進行某些操作，生成新的候選解。在遺傳算法中，上述幾個特征以一種特殊的方式組合在一起：基于染色體群的并行搜索，帶有猜測性質(zhì)的選擇操作、交換操作和變異操作。 其在解決多目標(biāo)問題上也有良好的方法，即基于Pareto解的遺傳算法，我們在保留子代的時候采用“支配解”的方式，在選擇兩個基因比較適應(yīng)度的時候，若A完全優(yōu)于B時，我們稱A支配B，其中B為支配解，若A不被任何其他解（向量）支配，則稱A為非支配解，我們通過遺傳、交叉、變異等操作得到的一系列非支配解即為我們所需要的Pareto最優(yōu)解集，其中最終的最優(yōu)解我們讓決策者根據(jù)自己的偏好程度來篩選。（2）多目標(biāo)粒子群算法粒子群優(yōu)化(Particle Swarm Optimization，PSO) 算法是近年來發(fā)展起來的一種新的進化算法。它和遺傳算法相似,它也是從隨機解出發(fā),通過迭代尋找最優(yōu)解,它也是通過適應(yīng)度來評價解的品質(zhì)，但是它比遺傳算法規(guī)則更為簡單,它沒有遺傳算法的“交叉”和“變異”操作。它通過追隨當(dāng)前搜索到的最優(yōu)值來尋找全局最優(yōu)。在PSO中，每個優(yōu)化問題的解都是搜索空間中的一只鳥，（粒子群算法最初就是根據(jù)飛鳥覓食而得到的）我們稱之為“粒子”。所有的粒子都有一個由被優(yōu)化的函數(shù)決定的適應(yīng)值(fitness value)，每個粒子還有一個速度決定他們飛翔的方向和距離，然后粒子們就追隨當(dāng)前的最優(yōu)粒子在解空間中搜索。PSO 初始化為一群隨機粒子(隨機解)，然后通過迭代找到最優(yōu)解。在每一次迭代中，粒子通過跟蹤兩個極值來更新自己。第一個就是