作業車間調度理論及其優化方法研究（簡體書）

第1章　導 論
1.1　概 述
隨著我國從粗放型生產向集約型生產的轉變,最近幾年,生產調度問題在國內的研究得到了前所未有的重視.所謂調度,就是為了實現某一目的而對共同使用的資源實行時間分配[1,2].它是一個決策的過程,其目的是優化一個或多個目標.調度問題來源于不同的領域,如醫院護理、生產計劃、計算機設計、軍隊作戰、交通運輸、后勤及通信等.一個組織中的資源和任務會呈現多種形式.車間里的機器、機場的跑道、建筑場所的工作團隊、計算環境中的處理單元都可以看成資源.任務則可能是生產過程中的操作、機場飛機的起飛和著陸、建筑項目的各個階段、計算機程序的執行等.每個任務可能有某種優先級水平、最早可能開始的時間和工期.目標也會呈現出多種形式.一個目標可能是最小化最后一項任務的完成時間,而另一個目標可能是最小化超過工期才完成的任務數量.
生產調度是實現制造業運籌、管理與優化技術的核心.它是在時間上對一組可用的制造資源,即機器進行加工任務的安排,將工件分配至相應的機器上,確定各機器上加工操作的加工次序和開工時間,使得某一性能指標最優.在執行這些加工任務時需要滿足某些物理約束,如工件的加工順序約束、機器加工能力限制等.同時也要滿足某些非物理約束,如工件到達時間約束、客戶交貨期限需求等.因此,生產調度問題可表述為在一些等式或不等式約束構成的離散解空間中,尋找目標函數值的最優解.它是一類重要的組合優化問題,運籌學稱之為排序問題[3,4].除少數特殊問題,大部分生產調度問題的計算復雜度為NPGhard,存在優化求解的困難[5].有效的調度優化算法能使現代商業領域增加產出、減少周轉時間、減少庫存,最終減少生產費用、增加利潤和提升客戶滿意度.因此,調度優化算法性能的好壞對這些行業的高效運作有重要影響,其研究也具有重要的理論意義和實用價值.
1.2　調度問題的描述
生產調度問題是在可用機器資源上對工件進行時間安排,使得某一或某些調度優化準則最優.因此,機器、工件和優化準則是生產調度問題的三個基本要素.Graham等在1979年提出生產調度問題分類和描述的三參數表述法[6,7],即一個調度問題用三元組α|β|γ來描述,其中,α域描述機器環境,它只包含單
一的一項;β 域提供加工特征和約束的細節,可能不包含任何一項,也可能包含
多個選項;γ域描述調度的優化目標,通常情況下只包含一項.
(1)參數域α表示機器加工環境,主要的機器環境描述如下.單機(1),即singlemachine.單機情況是所有機器環境中最簡單的一種情況,也是所有復雜機器環境中的一種特殊情況.
并行同速機(Pm),即identicalmachinesinparal
el,是指m臺具有相同加工速度的同型號并行機.工作j需要單一操作,可能在m個機器的任何一臺上加工,也可能在屬于某個給定子集的任何一臺機器上進行加工.如果不允許工作j僅簡單地在一臺機器上加工,而必須在屬于某個特定子集Mj 的一臺機器上加工,那么Mj 就出現在β 域中.
并行異速機(Qm),即machinesinparal
elwithdif
erentspe
ds,是指m臺具有不同加工速度的機器.機器i的速度記作vi.假設工作j所有的加工都在機器i上進行,那么工作j在機器i上耗費的時間pij ＝pj/vi.如果所有的機器具有相同的速度,即對所有的i有vi＝1及pij ＝pj ,那么這種環境和并行同速機環境相同.
并行無關聯異速機(Rm),即unrelatedmachinesinparal
el,是指m臺隨工作不同加工速度也不同的異速機.這種環境是并行異速機環境的一般化.機器i的加工工作j的速度記作vij .假設工作j所有的加工都在機器i上進行,那么工作j在機器i上耗費的時間pij ＝pj/vij .如果機器的速度獨立于工作,即對所有的工作j有vij ＝vi,那么這種環境和并行異速機環境相同.
流水作業車間(Fm),即flowshop.有m臺串聯機,每項工作必須按相同的工藝路徑依次在每臺機器上加工一次.如果機器前工件隊列按先進先出(is
frtinfirstout,FIFO)規則依次通過機器,該流水作業車間稱為排列流水作業車間(permutationflowshop),在參數域β 中包含排列(prmu).
柔性流水作業車間(FFc),即flexibleflowshop.它是流水作業車間和并行機環境的綜合和一般化,即c個串聯的加工中心,工件按相同的工藝路徑依次在每個加工中心上加工一次,每個加工中心有一組同型并行機.
作業車間(Jm),即jobshop.在有m臺機器的加工車間里,每項工作都有預先確定的加工路徑,每項工作最多訪問一臺機器一次.如果每項工作可以在同一機器上加工多次,此時在參數域β 中包含再循環(.
recrc)
柔性作業車間(FJc),即flexiblejobshop,柔性作業車間是作業車間和并行機環境的綜合和一般化.代替m臺機器的是c個加工中心,每個加工中心有許多并行同速機.每項工作按各自給定的工藝路徑通過車間,工作j只需要在每個工作中心的一臺機器上加工,而每臺機器都可以完成該工作.如果一項工作需
第1章　導 論.3.
要在它經過車間的加工路徑上訪問一個工作中心多次,那么在參數域β 中包含recrc.開放車間(Om),即openshop,開放車間有m臺機器,其中工件可按任意路徑在每臺機器上加工一次.
(2)參數域β 表示加工約束和特定的限制,可能包含多個選項.下面給出參數域β 中一些主要的約束描述.
到達時間ri,即releasedates.如果這個符號出現在β 域中,表示工件i不能在到達時間ri之前開始加工.如果ri沒有出現在β 域中,則工作j的加工可以在任何時間開始.與到達時間不同,工作的工期不在該域中規定.目標函數的類型給出了是否有工期的要求.
順序決定的準備時間sjk,即sequencedependentsetuptimes.sjk表示工作j和工作k之間的準備時間,該時間長短與工作的加工順序有關.如果工作k是第一個,則s0k表示工作k的準備時間;如果工作j是最后一個,則sj0表示工作j之后的清理時間.如果工作j和工作k之間的準備時間依賴于機器,那么將包含下標i,即sijk.如果β 域中沒有出現sjk,所有的準備時間都假設為零或者與順序無關,這時,準備時間包含在加工時間中.
搶占(prmp),即pre
mption.它表示一個工件若在一臺機器上開始加工,在它完工之前可以允許停止加工此工件,而加工另一工件.被搶占的工件已經進行的加工不會丟失,當它重新返回到機器上時,只需要加工剩下的操作.當允許搶占時,prmp出現在β 域中;當prmp不在β 域中時,不允許搶占.
排列(prmu),即permutaion.該約束可能出現在flowshop環境,它表示flowshop上所有機器上工件的加工順序相同.重入(e
nr),即rtat
rte
nrn.重入情況一般出現在作業車間調度環境或柔
性作業車間調度環境,它表示一臺機器在同一機器或加工中心上加工多次.
優先約束(prec),即precedenceconstraints.它可能出現在單機或并行機環境中,在一項工作開始加工前,另一項工作必須先完成.有幾種優先約束的特殊形式,即如果每項工作最多有一個前驅,最多有一個后繼,該約束稱為鏈式;如果每項工作最多有一個后繼,該約束稱為入樹;如果每項工作最多包含一個前驅,那么該約束稱為出樹.如果β 域中沒有出現prec,則不受優先限制.
故障(brkdwn),即breakdowns.機器故障意味著機器不能連續使用.例如,在并行機環境中,在任何時間點,可用機器的數量是時間的函數.
機器適用限制Mj ,即machineeligibilityrestrictions.當加工環境是m臺并行機器的時候,符號Mj 會出現在β 域中,當Mj 出現時,意味著并不是所有m臺機器都有能力加工工作j.集合Mj 表示可以加工幾個工作j的機器集合.如果β 域中不包含Mj ,則工作j可以在任何一臺機器上加工.
有了上述定義,下面列舉出常用的最小化優化目標函數.最大完成時間(制造期Cm).制造期(makespan)定義為max(C1,C2,.,Cn),它和最后一項離開系統的工a作完成時間相等.最小化制造期意味著最高效率x地利用機器.最大延遲Lmax,定義為max(L1,L2,.,Ln),它度量違反工期的最壞情況.
加權完成時間和∑wjCj .n項工作完成時間的加權給出了一個調度引起的持有或庫存成本指標.完成時間和在文獻中通常被稱為流水時間,加權完成時間和則稱為加權流水時間.
折扣加權完成時間和∑wj(1-e-rCj ).這是一個比前一個更一般的成本函數,此時成本以每單位時間r的比率產生折扣,0＜r＜1.也就是說,如果工作j沒有在時間t內完成,則在[t]時間段產生的附加成本為wj-rtdt.
t,t+dre如果工作j在時間t內完成,則在[0,t]產生的總成本是wj(1-e-rt).r的值通常接近于零.
加權滯后和∑wjTj .這給出了由工作滯后完成所引起的成本指標,它也是一個比加權完成時間和更一般的成本函數.該性能指標可用于評價不同重要程度客戶交貨需求的滿意度.加權滯后工作數量∑wjUj .這是實際生活中常用的優化目標,在這種優化目標下,顯然先加工重要程度高的工作可以得到較好的性能指標.有了α|β|γ三元組表示方法,我們可以用Fm|pij ＝pj |∑wjCj 來表
示一個有m臺機器的流水車間.工作j在所有m臺機器上的加工時間相同且等于pj .目標是找出n項工作通過系統的順序,使得加權完成時間總和最小化.FJc|rj,sijk |∑wjTj 指的是有c個加工中心的柔性加工車間.工作具有不同的提交日期,且受制于與機器相關的、由加工順序決定的準備時間,沒有再循環.因此,一項工作最多訪問一個加工中心一次.目標是最小化加權滯后時間的
總和.這個特殊的問題在實際生活中有很多應用.Jm‖Cmax表示有m臺機器的
作業車間的調度問題,沒有再循環.因此,一項工作最多訪問一臺機器一次.目
標是最小化制造時間.它是本書研究的主要問題類型.
當然,還有很多沒有在這個框架中描述的調度模型[8G10].例如,一個更一般的柔性作業車間,它的每個加工中心由許多加工速度與工作相關的并行異速機器組成.當一項工作在通過系統的加工路線上的機器組時,它可以在任何一臺機器上加工,但它的加工時間取決于加工它的那臺機器.人們也可以定義一個作業車間和開放車間的混合模型.有些工作的加工路線是固定的,而其他工作的路線是自由的.還有許多這里沒有提到的調度特征,這些特征包括循環調度、人員調度、資源約束調度、成批調度.但是有了α|β|γ三元組表示方法作為基本語言,調度問題的描述趨于規范化和簡潔化,極大地方便了我們對復雜問題的理解和交流.
區別于旅行商、四著色等NPGhard問題,車間調度問題具有以下特點[11G15]:
(1)多重約束性.在通常情況下,工件的處理受到嚴格的工藝路線約束,各道工序的先后關系不能顛倒.同時,由于設備的處理能力有限,工件必須按照順序在機床上處理.
(2)離散性.車間生產系統是個典型的離散系統,其中,工件的加工發生在不同的時間和資源上,并且任務的到達、訂單的更改、設備的增添和故障等都是離散事件.因此,我們可以利用數學規劃、離散系統建模與仿真的方式,通過排序理論研究車間調度問題.
(3)計算復雜性.車間中的工件、機床、操作人員、物料傳送系統和緩沖區之間相互影響、相互制約.工件的加工除上述雙重約束外,還要考慮操作人員的熟練程度、刀具數量、系統緩沖能力和各類動態事件的影響.在這些條件的綜合影響下,車間調度實質上是一個在若干等式和不等式約束下的組合優化問題,從計算時間復雜度看,它是一個NPGhard問題,隨著調度問題規模的增大,問題可行解的數量呈指數級增加,因而求解非常困難.
(4)隨機性.車間調度中有很多隨機和不確定的因素.例如,工件到達時間的不確定性,實際工件的加工時間也有一定的隨機性,以及系統中常有突發事件,如新任務到達、緊急任務插入、交貨期改變、訂單被取消、設備發生故障等.
(5)多目標.車間生產中,針對不同的加工任務,相應地有其特定的調度目標,而且這些目標之間往往是有沖突的.例如,生產周期最小化、設備總負荷最小化等.如何使車間調度系統適應不同的任務類型和規模,一直是車間調度中面臨的難題.
1.3　調度問題及解的分類
根據研究的側重點不同,車間調度問題有多種分類方式.
1. 資源約束種類和數量
單資源車間調度(singleresourceconstrained),即只有一種資源制約著車間的生產能力.在絕大多數的相關科技文獻中,單資源一般指車間生產環境中,機床設備的數量不能同時滿足所有可加工工序立即被加工的要求.