面向快速響應的賽汝生產系統構建模型與方法

湛榮鑫 李冬妮 馬濤 李俊杰 吳延昭 殷勇

自1980 年代以來,電子信息產業蓬勃發展,產品生命周期顯著縮短,電子產品目前的平均生命周期僅為6 個月[1].因此,面對更為多樣化的產品種類需求、更短的產品生命周期要求以及由此帶來的市場環境波動性和不確定性[2?4],傳統的生產系統如流水線或豐田制造系統難以獲得很好的表現,亟需一種具有優異快速響應能力的新型生產系統[5].Seru是日式生產單元,由Seru 構成的賽汝生產系統(Seru production system,SPS)作為一種新興的生產模式廣泛應用于日本的電子制造行業.與傳統生產系統相比,SPS 最突出的優勢在于其應對不確定市場需求的快速響應能力,而之所以可以實現快速響應,主要原因就是Seru 在物理結構上是可重構而不是固定的,并由此可以帶來諸如降低成本、縮短生產時間、縮短生產準備周期、縮短勞動時間等方面的顯著收益[2,6?14].

目前,已有很多學者圍繞SPS 構建問題展開研究,這類研究大多將SPS 構建分成了兩個階段,分別是Seru 構建和Seru 調度.Seru 構建大多分為兩類模型,一類是研究如何將現有流水線拆分為若干個Seru;另一類是給定若干數量的Seru,主要考慮工人的分配問題[15].Seru 調度決策如何將產品批次分配到已構建好的Seru 中去[16?21].例如,Liu等[22]研究了在SPS 中多能工的培訓和分配問題,建立了最小化總培訓成本和平衡多能工之間勞動時間的多目標問題模型.Liu等[23]考慮了優化經濟和環境指標的SPS 構建模型.Lian等[24]提出了考慮Seru 內部和Seru 間多能工勞動力平衡分配的SPS構建模型.

已有研究大多有一個共同的假設: 一旦Seru構建完成,就不再會發生變化.然而,SPS 應該具備隨著生產需求變化動態進行Seru 構建和拆除的能力.此外,相關研究還大多假定工人都是全能工(即具有一個或多個產品所需要的所有工序的加工能力).實際中,工人很難全部被培訓為全能工且存在技能水平上的差異.另一方面,純粹由全能工構成的SPS 也不一定是最優的[25?26].因此,在考慮工人具有不同的技能組合和技能水平的情況下,如何組織工人構建SPS 是一個重要的研究問題.

基于以上考慮,本文考慮如下的SPS 場景并設計了兩階段的SPS 構建模型,分為Seru 構建(Seru configuration,SC)和Seru 調度(Seru scheduling,SS).當新訂單到來時,有恰當數量的Seru 被構建并完成分配給各自的生產任務.當每個Seru 完成其生產任務時立刻拆解.因此,整個SPS 可以動態調整其自身結構,調整的對象包括Seru 的數目、分配給Seru 的工人以及每個工人負責的工序等.具體而言,兩階段描述如下.1) Seru 構建階段: 在同一生產周期內,所有的工人具有同樣的初始剩余工作時間.工人具有不同的技能組合以及在不同的工序上具有不同的技能水平,不同的工人在相同的工序上也具有不同的技能水平.首先在不超過每個工人工作時間上限的約束下,為訂單找出一個可行的工人?工序分配方案,并在依照這個分配方案,考慮每個Seru 工人之間的配合從而構建Seru.在本階段提出了工人?工序映射模型和優化Seru 內部工人工作時間平衡的工人?Seru 分配模型;2) Seru 調度階段: 一個工人在Seru 構建階段中可能會被分配參與多個Seru 的生產任務,而任一工人同一時刻只能參與一個Seru 的生產,因此Seru 間存在調度問題,基于此提出了最小化SPS 最大完工時間(Makespan)的Seru 調度模型.

本文的主要貢獻如下: 1)考慮了工人并非全部是全能工的SPS 構建問題,即工人具有不同的技能組合和技能水平;2)本文提出的SPS 模型是動態可重構的,考慮了Seru 從構建到拆解的全生命周期.本文其余部分組織如下: 第1 節介紹了問題模型和數學模型,第2 節給出了每個階段的模型性質分析、相應的精確/近似算法以及算法分析,第3 節介紹了實驗設計、實驗結果以及分析,第4 節給出了本文結論.

1 問題模型

本文抽象出的問題模型包含兩個階段: Seru 構建和Seru 調度,基于此兩階段問題抽象出問題模型.

1.1 問題假設

本文研究的SPS 構建問題假設描述如下:

1) SPS 內工人總數是確定的,所有的工人都是多能工,且存在技能組合和技能水平上的差異.所有工人在同一生產周期內具有同樣的初始剩余工作時間.

2)一個訂單中只包含一個產品類型,訂單的信息(產品類型和需求量)只有在到來時才能被獲知.

3)一個Seru 只生產一種產品類型,一種產品類型可以被SPS 中的多個Seru 生產.

4)一個工人可以被分配到多個Seru 中去.

1.2 符號列表

與本文問題相關的符號變量定義如下所示.

1) 索引

w工人索引(w=1,···,W).

i工序索引(i=1,···,I).

c產品類型索引(c=1,···,C).

d訂單索引(d=1,···,D).

sSeru 索引(s=1,···,S).

p可供構建Seru 的場地索引(p=1,···,P).

2) 系統變量

Ow工人w能夠加工的工序集合.

td訂單d的到來時間.

nd訂單d的需求量.

Id生產訂單d的所需工序集合.

Wd訂單d到來時,當前空閑可以參與加工的工人集合.

Sd完成訂單d所構建的Seru 集合.

ptsSerus從構建到拆解的存在時間.

ctsSerus完成生產任務拆解的時刻.

3) 決策變量

1.3 圖表模型及約束條件

本節對SC 問題和SS 問題分別建模并給出約束條件.

1) 對SC 問題的工人?工序映射步驟建模,這是一個約束滿足問題,其模型描述如下.

其中,式(1)表示對于任一訂單d,其所需的任一工序i的數量應與該SPS 中所有能加工該工序的工人實際執行工序i的數量相等;式(2)確保分配給任一工人的工作量不會超過該工人初始剩余工作時間;式(3) 表示參與任一訂單d生產的任一工人w所參與加工的工序種類不能超過限制.

2) 對SC 問題的工人?Seru 分配步驟建模,其模型描述如下.

定義Ed為加工某一產品類型包含所有可能的加工路徑的圖,并結合費用流圖的基本定義,為Ed在第一道工序前設置虛擬始點,在最后一道工序后設置虛擬終點.如圖1 所示,訂單1 需要2 道工序,分別是工序1 和工序2,工人1 和工人2 能夠加工工序1,工人3 和工人4 能夠加工工序2.則所有代表加工路徑的虛線、所有工人節點、始點和終點共同構成E1.

圖1 訂單1 的潛在加工路徑E1Fig.1 Potential processing paths E1 for order 1

對于任一訂單d:

需滿足如下約束:

其中,式(4)為該階段的目標函數,表示通過選擇不同的工人構建Seru 從而最小化訂單d的所有兩兩相鄰工序之間的單位加工時間之差的絕對值;式(5)和式(6)表示為訂單d所構建SPS 的生產量應與訂單d的需求量一致;式(7)和式(8)表示工人w1和w2共同生產訂單d且工人w1參與的是工序i1生產任務,工人w2參與的是工序i2生產任務,工序i1與工序i2是相鄰工序,此時他們的共同生產任務量不能超過第一階段時所決策出的生產任務量和;式(9)表示產出量必須大于等于0.

對SS 問題建模,其模型描述為

需滿足如下約束:

其中,式(10)為該階段的目標函數,表示最小化該SPS 中Seru 的最大完工時間;式(11)計算的是任一Serus完成其生產任務的最早時刻;式(12)保證需要同一工人參與生產的兩個不同Seru 在同一時刻不能同時存在;式(13)保證在任一時刻,一塊場地上只能存在一個Seru.

2 模型分析及算法

本節給出SC 問題和SS 問題相關模型性質分析及算法.

對于SC 問題來說,其中涉及到工人?工序映射建立和工人?Seru 分配兩個步驟.本節對于這兩個步驟分別進行了模型性質分析并給出了精確算法來求解.

定理1.工人?工序映射問題是NP 難的.

證明.本文將經典的NP 難問題——劃分問題(Partition problem,PP)[27]歸約到建立工人?工序映射問題,從而證明建立工人?工序映射問題也是NP 難問題.

劃分問題描述如下: 有一個有限集合U,該集合中每個元素u有一個權重h(u),決策目標是希望找到一個U的子集U′使得

對于任一劃分問題的實例,考慮構建如下建立工人?工序映射問題的實例: 目前只有一個訂單d到來,其產品類型需要兩道工序i1和i2來生產.SPS中共有|U|個工人可以參與加工,且每個工人均有能力加工工序i1和i2. 任一工人w在這兩道工序上的單位加工時間為 1 /h(u).對于任一工人來說,參與的工序種類限制=1且初始剩余工作時間為1.訂單d的需求量為此時,顯然當構建的建立工人?工序映射問題的實例能夠求解時,對應的劃分問題實例也能得到求解.

由此,建立工人?工序映射是NP 難的. □

定理2.工人?Seru 分配問題可以被多項式時間內求解.

證明.工人?Seru 分配問題模型與最小費用流問題模型是一樣的,如圖1 所示.最小費用問題是一個可以被多項式時間內求解的經典問題,因此工人?Seru 分配問題也可以被多項式時間內求解.□

推論1.SC 問題是NP 難的.

證明.由定理1 和定理2 可知,SC 問題是NP難的. □

算法 1.SC 算法

步驟 1.初始化每道工序上的工人?工序映射列表,將所有可以加工該道工序的工人放入對應列表中,產品生產量設置為0,設置為0.

步驟 2.工人排序: 對于每道工序,按照單位加工時間非減的順序對列表進行排序.

步驟 3.依次檢驗每道工序,若工人?工序映射列表為空,返回False;否則將該工序任務分配給工人?工序映射列表中首個工人,并扣除該工人剩余加工時間,數值為該工人在該道工序上的單位加工時間,對應增加1.

步驟 4.檢測至最后一道工序后,產品生產量增加1,若產品生產量小于該訂單產品需求量,返回步驟 3;否則,記錄并輸出.

步驟 5.利用網絡單純型法計算工人?Seru 分配,記錄并輸出

對于SC 算法,其流程中最復雜的算法循環需要先對訂單需求量nd進行1 次循環,再對工人數量W進行嵌套的3 次循環,因此SC 算法的時間復雜度為 O (ndW3).

目前已有很多多項式時間算法或求解器可以對最小費用流問題進行求解,網絡單純形法是其中一個常用的算法.因此,SC 算法的步驟 5 采用這一算法對工人?Seru 分配問題進行求解,使用版本為Python 庫中NetworkX 內置的網絡單純型法.算法較為經典,因此細節不再贅述.

定理3.Seru 調度問題是NP 難的.

證明.本文將已被證明是NP 難問題的并行多機調度問題(Parallel machine scheduling,PMS)歸約到提出的Seru 調度問題.

并行多機調度問題描述如下: 對于給定的一系列任務J={1,···,j,···},任一任務j∈J有相應的到來時間rt(j)、處理時間pt(j)、完工時間ft(j).這些任務可以在M臺機器上加工且不允許搶占.決策目標是找出一個調度方案使得最大完工時間最小.

任一并行多機調度問題實例等同于如下Seru調度問題實例:

令td=rt(j),pts=pt(j),cts=ft(j),顯然當Seru 調度問題的實例可以被求解時,對應的并行多機調度問題實例也可以被求解.因此,Seru 調度問題是NP 難的. □

針對這一NP 難的Seru 調度問題,本文提出了近似算法如下:

算法2.SS 算法

步驟 1.初始化: 將所有待調度Seru 放入未調度列表,將已調度列表設置為空,將時刻設置為0.

步驟 2.當未調度列表不為空時,按照pts非增原則對未調度列表中Seru 進行排序;否則,跳至步驟 6.

步驟 3.若存在n個空閑場地,則將未調度列表中前n位的Seru 從未調度列表移動至已調度列表.

步驟 4.對新放入已調度列表中的n個Seru 進行檢測,若與其他任一已調度列表中Seru 存在工人占用,則將其重新移動至未調度列表.完成對n個Seru 的檢測和操作后,將時刻增加1.

步驟 5.如果有新的Seru 需要被調度,則添加其至未調度列表,檢測并移除已調度列表中所有完成加工任務的Seru,返回步驟 2.

步驟 6.停止,輸出結果.

對于SS 算法,其流程中最復雜的算法循環需要對Seru 的數目S進行2 次循環,因此SS 算法的時間復雜度為 O (S2).

定理4.SS 算法的近似比為3.

證明.首先,定義最優Makespan為,定義為SS算法得出的生產過程中由于工人占用所造成的Seru 之間非并行的等待時間之和.對于所有已構建的Seru 來說,有3 個非常簡單的下界:

由此,得證Seru 調度算法的近似比為3. □

3 實驗與分析

為了檢驗SPS 的性能表現,本文進行了多組實驗,波動市場采用不同的參數組合來模擬.仿真實驗采用Python 語言實現,運行在3.10 GHz Core i5-2400 CPU,4 GB RAM 的PC 機上.共有3750組用例被測試.以下分別介紹實驗設計、算例展示、實驗結果和相關分析.

3.1 實驗設計

本文中,通過對多樣的產品類型和波動變化的需求量兩個維度來對波動市場進行描述.具體來說,每種產品的生產需要多道工序,因此設置了不同復雜程度的產品類型組合以不同的級別表示來區分,分別為1,3,5,7,9.每個級別表示該測試用例下到來的多個訂單所包含的不同產品類型數量上限.每個測試用例實際生成的產品類型數量采用范圍為從1 到該級別數值的均勻分布來生成.每個訂單的需求量服從截斷正態分布,平均值μ以及波動系數cf=σ/μ用于體現市場波動.μ設置為: 10,20,30,40,50,cf設置為: 0.1,0.3,0.5,0.7,0.9.對于上述波動市場的參數設置如表1 所示.

表1 波動市場的參數描述Table 1 Parameters of volatile markets

工人的技能設置采用Chaining strategy 的方式來設置[28].本實驗的其余參數設定如表2 所示.

表2 算例的其余參數描述Table 2 Parameters of test problems

因此,共有5 (產品類型級別)×5 (μ)×5 (cf)=125 組不同參數組合產生,依據中心極限定理[29],每個參數組合下產生30 個算例,因此共有3750 個算例被測試.

3.2 算例展示

為了更清晰地展示模型性質,本節選取一個簡單的包含5 個工人的SPS 構建算例來展示.其中,所有工人的初始剩余加工時間均為200,工人在不同工序上的單位加工時間如表3 所示,該生產周期內的訂單信息如表4 所示,工人在不同工序上的加工優先次序為單位加工時間短的工人排列在前.

表3 工人在不同工序上的單位加工時間Table 3 Processing time of each worker on different operations

表4 訂單信息Table 4 The information of orders

具體地,在該算例中共會有2 個訂單到來,訂單1 會在時刻0 到來,加工該類型產品需要工序1和工序2 工兩道工序,其需求量為15,訂單2 會在時刻40 到來,加工該類型產品需要工序3,工序4,工序5 三道工序.訂單的詳細信息在該訂單到來時刻才會被工廠獲知.通過第1 階段算法計算可以很容易得出該算例下工人在不同工序上的加工優先次序,如在加工工序1 時,共有工人1 和工人2 可以參與加工,選擇優先順序為優先選擇工人2,其次選擇工人1.

在決策訂單1 的生產任務分配時,工序1 和工序2 均會優先分配給工人2,而工人2 的生產能力不足以完成整個訂單1 的生產,因此需要構建多個Seru 來共同完成訂單1 的生產.同理,對于生產訂單2 的生產,可根據第1 階段和第2 階段的算法計算得出所構建Seru 具體信息如表5 所示.具體來說,為生產訂單1 構建Seru 1 和Seru 2,其中Seru 1 為只有工人2 參與加工的單人物臺,Seru 2 為工人1 和工人3 共同配合加工,工人1 負責工序1,工人3 負責工序2.Seru 1 產出產品11 件,存在時長為198.Seru 2 產出產品4 件,存在時長為58.為生產訂單2 構建Seru 3 和Seru 4,其中Seru 3 有工人3,、工人4、工人5 參與加工,工人3 負責工序3,工人4 負責工序4,工人5 負責工序5.Seru 4 有工人4 和工人5 參與加工,工人4 負責工序3 和工序4,工人5 負責工序5.Seru 3 產出產品9 件,存在時長為125.Seru 4 產出產品2 件,存在時長為48.

表5 為生產3 個訂單所構建的Seru 展示Table 5 Serus that are configured for orders

經第3 階段算法計算,4 個Seru 的調度結果如圖2 所示.Seru 1 和Seru 2 不存在工人占用,可以并行構建.訂單2 在時刻40 到來,此時Seru 1 和Seru 2 仍未完成各自生產任務,Seru 2 和Seru 3 均需工人3 參與加工,因此此時Seru 3 不能被構建,先行構建Seru 4.在時刻58,工人完成Seru 2 的生產任務被釋放,而Seru 3 和Seru 4 之間有共同需要工人4 和工人5 參與加工,因此Seru 3 仍不能被構建,需等待Seru 4 加工完畢.直到時刻88,Seru 3 可以被構建.

圖2 為訂單1 和2 所構建的4 個Seru 甘特圖Fig.2 Gantt chart for 4 Serus

這個算例展示了Seru 間可能頻繁發生的并行構建與工人占用,由此可觀察到SPS 具備根據市場變化靈活調整其結構的能力.

3.3 實驗結果與分析

本節給出了4 組不同實驗的結果展示與分析,分別是: 1) 波動市場環境下,不同的產品類型參數設置對SPS 中Seru 數目、工人利用率、訂單完成時間的影響;2)波動市場環境下,不同的產品需求量設置對SPS 中Seru 數目、工人利用率的影響;3) 波動市場環境下,不同的市場波動系數設置對工人利用率的影響.

3.3.1 產品類型參數設置的影響

圖3 展示了隨著產品類型級別上升,SPS 所構建的Seru 平均數目的變化情況.如圖3 所示,當產品類型級別從1 升至9,Seru 平均數目從2.48 上升到了10.62,且整體呈上升趨勢.圖4 展示了隨著產品類型級別上升,工人平均利用率的變化情況.如圖3 所示,隨著產品類型級別從1 升至9,工人利用率在79.20%和85.14%之間波動,基本趨于穩定.圖3 和圖4 體現了SPS 在應對同一生產周期內到來的產品類型多樣的訂單時,為了高效完成生產任務(如維持較高的工人利用率),可以通過構建和拆解不同數量、結構的Seru 從而動態調整系統整體結構來應對不同的市場環境.這也是SPS 可以快速響應多種不同類型訂單的重要原因.

圖3 Seru 數目隨產品類型級別變化趨勢Fig.3 The number of Serus versus product types

圖4 工人利用率隨產品類型級別變化趨勢Fig.4 The utilization of workers versus product types

圖5 展示了Makespan 隨著產品類型級別上升的變化情況.可以看到,隨著產品類型級別從1 升至9,Makespan 呈整體下降趨勢,從2445 下降到了2022.這是一個較為反常的現象,因為隨著產品需求種類變多(即產品類型級別上升),一般而言會需要更長的完工時間.通過跟蹤實驗細節發現,對于產品類型級別較低的測試用例,需要的工序較為單一,從而使得參與加工的工人較為固定,生成的Seru 由于互相之間工人的占用,很難并行構建,因此需要的完工時間較長.而當產品類型級別提高后,產品類型增多,工序種類數目上升,可以參與加工的工人數量也隨之上升,這導致了更多的Seru 可以被構建且互相之間發生工人占用情況的概率下降,因此SPS 整體并行性得到了提高,從而獲得了更短的Makespan.

圖5 訂單最大完工時間隨產品類型級別變化趨勢Fig.5 The makespan versus product types

3.3.2 產品需求量設置的影響

圖6 展示了SPS 所構建的Seru 平均數目隨著訂單需求量均值μ上升的變化情況.在圖6 中,隨著訂單需求量均值μ從10 升至50,Seru 平均數目從10.18 上升到了14.50.圖7 展示了工人平均利用率隨著訂單需求量均值μ上升的變化情況.如圖7所示,工人利用率穩定保持在77.16%附近.圖6 和圖7 相結合體現出,當市場需求上升時,SPS的工人平均利用率仍能保持在穩定的較高水平.

圖6 Seru 數目隨訂單需求量變化趨勢Fig.6 The number of Serus versus product volumes

圖7 工人利用率隨訂單需求量變化趨勢Fig.7 The utilization of workers versus product types

3.3.3 市場波動系數設置的影響

圖8 展示了工人平均利用率隨著市場波動系數cf上升的變化情況.從圖8 可以看出,隨著cf從0.1升至0.9,工人平均利用率保持在80.61%附近.這一結果體現了隨著市場的逐步惡化(市場從穩定到劇烈波動),SPS 可以保持較高的工人平均利用率.

圖8 工人利用率隨市場波動變化趨勢Fig.8 The utilization of workers versus cf levels

以上實驗結果驗證了面對產品類型多樣且產品需求變化大的典型波動市場環境,SPS 具有穩定高效的性能表現,其可重構性使其具有了良好的響應能力.另一方面,在不同參數的設置下,工人利用率始終維持在較高水平,實驗結果從側面驗證了所提出模型的有效性.

4 結束語

本文針對波動市場環境下SPS 構建問題,從實際情況出發,考慮了系統中工人是多能工且具有不同的技能組合和技能水平的情況,提出了一種SPS三階段構建模型與相應方法.構建出的SPS 具有較強的重構能力和良好的響應能力.具體來說,首先,針對當前到來訂單中產品的每道工序,為其分配有足夠生產能力(具備相應技能和足夠的工作時間)的工人;其次,安排不同的工人之間配合來生成Seru,使得工人之間的配合最為平衡,最大化工人利用率;最后,考慮不同Seru 間的工人占用問題,對Seru 進行調度,最小化加權完工時間.在對模型性質分析的基礎上,本文提出了相應的精確算法、在線調度算法對模型進行求解.實驗結果驗證了所構建SPS 的優良性能.

本文所提出的SPS 構建模型和方法具有較強的現實意義.圍繞這一研究方向,在今后的工作中,會從以下幾個方面進行更深入的探索: 1)考慮更大規模、更為復雜的波動市場環境下SPS 構建問題,設計高效的智能優化算法求解;2)對于生產系統來說,重要的優化指標有很多,比如最大化工人利用率、最小化成本、最小化庫存、最小化完工時間等等,考慮建立SPS 構建問題的多目標決策模型及設計相應的多目標優化算法.