服裝生產線中基于熟練度的人員調度模型及策略研究

張文豪, 王無雙, 王成群,3, 駱淑云,3

(1.浙江理工大學計算機科學與技術學院, 浙江 杭州 310018;2.浙江理工大學信息科學與工程學院, 浙江 杭州 310018;3.東北大學流程工業綜合自動化國家重點實驗室, 遼寧 沈陽 110004)

0 引言(Introduction)

傳統服裝制造業的生產模式具有大規模生產的能力,隨著近年來消費者對個性化服裝定制需求的不斷增長,服裝企業由大批量的生產模式改為多訂單、小批量的新生產模式。在大部分服裝企業中,生產計劃依然是由管理人員根據經驗制訂,但是這樣的生產計劃制訂方式不僅效率低下,而且難以應對新生產模式中服裝訂單需要插單、重新排單等突發狀況[1]。在新的生產模式下,服裝企業雖然通過機器等工具在生產工序上實現了自動化生產,但是依然有很多工序或機械需要人員操作,而服裝生產企業的員工流動性大、技能差異大等因素也導致生產計劃需要頻繁調整或重新制訂,因此急需探索一種具有人員自動調度功能的調度模型用于實際生產。

本文首先針對因人員技能差異造成的服裝生產調度問題進行建模,以最小化實際總工序時間為優化目標,并考慮員工熟練度、工序生產平衡率等約束條件的影響;通過對多種經典算法性能進行比較分析發現,遺傳算法能夠較好地解決該問題。其次使用服裝廠的實際數據對本文設計的模型進行性能評估,并與遺傳算法(Genetic Algorithm, GA)、貪心算法(Greedy)、粒子群算法(Particle Swarm Optimization, PSO)等經典算法進行了對比。為了進一步評估本文設計的模型在不同問題規模下的通用性,分別在不同規模的工廠調度場景下進行算法的模擬仿真實驗。最后利用生產任務甘特圖對調度流程進行可視化呈現,進一步驗證本文所提方法能夠保證企業平穩有序地生產。

1 研究現狀(Research status)

隨著智能制造的發展,企業的生產逐步向智能化、自動化方向轉變。為了滿足市場上個性化的需求,企業開始由大批量的生產模式轉變為多訂單、小批量的新生產模式。在實際生產中,影響服裝生產效率的因素眾多,如服裝款式差異、加工設備差異、訂單批量差異等,很多學者對不同的影響因素進行了大量研究[2]。針對加工順序、工位分配的差異性,劉鋒等[3]提出了基于深度強化學習的實時動態調度方法,解決了現有服裝生產調度過程中,動態事件自適應及實時響應能力差的問題。該方法在調度目標達成度上稍差于遺傳算法,但大幅減少了決策時間。針對加工順序、加工設備的差異性,謝子昂等[4]提出了一種基于多目標動態調度算法的自適應滾動窗口機制調度模型,并運用非支配遺傳算法對模型進行求解,解決服裝大規模定制生產的自適應性較弱的問題。針對訂單的差異性,李彬彬[5]提出了面向訂單的服裝企業的生產作業計劃的數學模型,利用遺傳算法進行了求解。鄭衛波等[6]建立了企業生產模型和計劃編制的目標函數,同樣采用遺傳算法對問題進行了求解。針對所需服裝數量、鋪布能力和裁剪順序的限制,WONG等[7]提出了雙層調度模型,解決了服裝行業中的混合流水車間和早晚調度問題。針對服裝部件匹配周期的差異性,謝子昂等[8]構建了部件同步生產模型,采用遺傳算法優化了訂單的投產安排,減少服裝部件匹配時間和調動次數,并進行了模擬仿真。針對生產線平衡能力的差異性,張旭靖等[9]建立以最小化平衡損耗率為目標的平衡優化模型,利用遺傳算法解決服裝縫制生產線作業間由不平衡產生的效率損失問題。

針對服裝生產效率的影響因素,目前還沒有學者深入研究服裝生產人員技能差異對生產調度計劃制訂帶來的影響。因此,本文針對服裝生產線中基于熟練度的人員調度影響因素研究了人員調度模型及策略以優化服裝廠生產調度計劃。

2 服裝生產線人員調度模型(Personnel scheduling model of garment production line)

2.1 調度問題描述

服裝企業需要解決的問題是在保證員工合理的工作時間和生產線平衡率的同時,以縮短生產時間為目標,制訂訂單生產調度計劃。在服裝廠生產調度計劃制訂過程中,該調度問題可以被描述為有n個訂單(D1,D2,…,Dn),由一組擁有m名員工(s1,s2,…,sm)的加工小組進行加工,任一訂單Di由加工順序已知的工序Pi={Pij,j∈(1,2,…,ni)}組成,訂單Di的第j道工序可選員工序號集合為Sij?{1,2,…,m},(1≤i≤n,1≤j≤ni),員工sk加工訂單Di的第j道工序的熟練度為Eij={Eijk,k∈(1,2,…,m)}。調度目標是將所有訂單中不同的工序分配給員工,以實現所有訂單實際總工序時間最小化。

2.2 符號定義

訂單Di的第j道工序為Pij;工序Pij的標準加工時間為Tij;工序Pij的實際加工時間為Tijk,其公式如下:

(1)

員工sk的實際加工總時間為Tsk,其公式如下:

(2)

生產計劃的平均工序時間為t,其公式如下:

(3)

平均工序時間t由所有員工的工作時間決定。生產調度過程中希望每名員工的總工作時間都接近平均工序時間以平衡各自的生產進度;平衡率α是平均工序時間t與員工最大實際加工總時間之間的比值,用來評估整個加工過程工序堵塞堆積的情況,其公式如下:

(4)

2.3 調度模型

2.3.1 優化目標

本研究以實際總工序時間T最小化為優化目標,其公式如下:

(5)

2.3.2 約束條件

由于在服裝廠的實際生產過程中,個別員工對整個生產過程中的大多數工序都具有較高的熟練度,如果將這些工序全部分配給這名員工,會導致多個不同部件的工序無法進行并行生產的情況,進而影響整個生產過程的效率,因此服裝廠需要盡可能地平衡每名員工被分配到的工序總時長Tsk。

公式(6)表示為了提高平衡率α,需要約束員工被分配到的最大工序總時長max(Tsk)。公式(7)表示一道工序只能由一名員工進行加工,其中Xijk為工序Pij是否由員工sk進行加工的判別條件,當將工序Pij分配給員工sk進行加工時,Xijk=1,反之為0。公式(8)表示工序加工順序的約束條件,TBijk、TWijk分別為工序Pij由員工sk進行加工的實際開始時間和加工完成后的實際總工序時間。

max(Tsk)≤t(1+β),k∈Sij,β≥0

(6)

(7)

TWijk≤TBi(j+1)k,k∈Sij

(8)

β是設定的抖動率參數,用于約束每名員工的總工作時間。

3 基于熟練度的人員調度策略(Proficiency-based personnel scheduling strategy)

3.1 基于熟練度的人員調度策略構建

傳統的服裝生產調度方式是按前片、后片、袖子、袖口等部件順序生產,所有部件加工完成后,再進行組合工序生產,具體工藝流程如圖1所示。基于熟練度的人員調度策略,首先搜索工藝流程圖中從部件生產開始到結束的所有路徑,比較所有路徑的工序生產標準加工總時間,其次將標準加工總時間最多的路徑作為最佳路徑,并將其他的生產路徑與最佳路徑并行生產,最后根據員工對工序的熟練度進行分配。當在某一時刻,最佳路徑的工序與并行路徑的工序需要同一名員工生產時,則適當調整并行路徑的工序開始時間,保證生產流水線暢通,并減少服裝生產時間。

圖1 工藝流程圖Fig.1 Process flow chart

3.2 基于遺傳算法的人員調度方法

遺傳算法是一種非確定性的擬自然算法,為復雜系統的優化提供了一種新思路,在諸多領域均有很好的應用效果,如函數優化、組合優化、生產調度等[10]。與其他經典優化算法相比,遺傳算法并不是直接對問題本身進行優化,而是通過對問題進行編碼,并且以適應度函數評價解的優劣,避免無法得到問題的解。遺傳算法專注于搜索范圍,以初始種群為搜索對象,能夠同時搜索多個點,并最終提高算法的求解效率。服裝廠人員調度過程中需要同時考慮多個約束條件對調度目標的影響,本文借助遺傳算法良好的全局搜索能力和求解效率,對生產線人員進行調度優化。

3.2.1 染色體編碼

本文構建了一個一維數組,采用基于數組的實數編碼方法,染色體中的基因代表對應工序所安排的員工序號。

3.2.2 遺傳算法設計

基于遺傳算法對生產線人員進行調度優化,算法設計實現過程如下。

(1)生成初始種群:按照上述染色體表示方法,每道工序不選擇熟練度為0的員工,排除不可行解后,隨機生成數組碼,然后構成相應的染色體,形成初始種群。

(2)適應度函數:以實際總工序時間T為目標函數,將其倒數作為適應度函數。

(9)

(3)選擇:選擇優秀的個體傳給下一代。本文采用輪盤賭選擇方法,每個個體被選擇的概率與其適應度值有關,適應度值越大,被選擇的概率越大。

(4)交叉:遍歷一對父系染色體的基因,隨機產生一個概率Pc,如果這個概率大于Pc,則交換對應位置兩個父系的基因。

(5)變異:使用隨機變異的方法。取一個隨機概率,如果隨機概率小于設定的變異概率,隨機選擇一個位于區間[1,n]的基因aj進行變異,從而形成一個新的子代個體。

(6)重復“步驟(2)”至“步驟(5)”,直到滿足算法終止條件,輸出最優結果。

3.3 基于粒子群算法的人員調度方法

粒子群算法初始化為一群隨機粒子(隨機解),然后通過迭代找到最優解。在每一次迭代中,粒子通過跟蹤兩個“極值”更新自己:第一個極值是粒子本身找到的最優解,即個體極值pbest,另一個極值是整個種群找到的最優解,即全局極值gbest。

3.3.1 粒子群算法設計

(1)生成初始種群:每道工序不選擇熟練度為0的員工,排除不可行解后,初始化所有粒子及其速度和位置,并將粒子的歷史最優解pbest設為當前位置,而群體中最優解的粒子作為當前的gbest。

(2)適應度函數:以實際總工序時間為目標函數,將其倒數作為適應度函數。

若粒子當前的適應值比之前記錄的該粒子歷史最優解pbest更好,則更新pbest。

若粒子當前的適應值比之前記錄的全局最優解gbest更好,則更新gbest。

(3)粒子根據如下公式更新自己的速度和新的位置:

v(k+1)=ωv(k)+c1r1(pbest(k)-present(k))+c2r2(gbest(k)-present(k))

(10)

present(k+1)=present(k)+v(k+1)

(11)

其中:v(k)是k時刻的速度,present(k)是k時刻的位置,r1和r2是取值范圍(0,1)的隨機數,ω是慣性權重因子,c1和c2稱為加速因子或學習因子。

3.4 基于貪心算法的人員調度方法

貪心算法是一種只考慮當前對自己最有利的選擇,通過逐步獲得最優解解決最優化問題的一種算法。

3.4.1 貪心算法設計

(1)根據工藝流程對每道工序選擇其熟練度最高的員工,當有多個熟練度相同的員工可以選擇時,隨機選擇其中一名員工,生成初始解。

(2)計算初始解,即每名員工的實際加工總時間,對每道工序根據最大工序時間進行迭代優化。

(3)重新遍歷所有工序,如果當前工序所安排員工的實際加工總時間超出最大工序時間,并且當前工序有其他熟練度較高且實際加工總時間小于最大工序時間的員工可以選擇時,將當前工序分配給實際加工總時間短的員工。

(4)重復以上步驟,直至所有員工的總加工時間滿足最大工序時間,或者達到設定的循環次數時,結束循環,輸出當前的最優結果。

4 實例仿真及性能評估(Example simulation and performance evaluation)

4.1 工廠數據集性能評估

4.1.1 服裝企業背景

本文以杭州某服裝廠為例。為了滿足市場需求,服裝廠的生產模式由原來的大批量生產轉變為多訂單、個性化小批量生產。由于訂單之間存在差異,所以服裝廠每接一個訂單就需要制訂對應的生產計劃。

4.1.2 工藝數據

本文以生產連衣裙為例,需要生產的裙子分為前片、后片、袖子、袖口、襟貼、耳仔、腰帶、配件等部件,每一個部件都需要經過多個工序加工后組合成成衣,生產工藝如圖2所示。一個生產小組的員工人數為19人,所做的服裝有8種部件,其中前片部件有21道工序,后片部件有11道工序,袖子部件有15道工序,袖口部件有5道工序,襟貼部件有10道工序,耳仔部件有5道工序,腰帶部件有7道工序,配件有6道工序,最后將所有部件組合環節又有40道工序,即生產一條連衣裙總共需要120道工序。每名員工對每道工序的熟練度由員工熟練度表(表1)計算得出,表1中熟練度由服裝廠管理人員考慮員工對各種工序的熟練程度、身體狀況等因素按百分制進行量化,在實際計算過程中,將數值轉化為小數帶入模型中計算。每道工序的標準時間由款式工序表(表2)得出。

表1 員工熟練度表

表2 款式工序表

圖2 連衣裙生產工藝流程圖Fig.2 Process flow chart of skirt production

4.1.3 算法參數設置

為兼顧算法收斂速度和解集質量,算法設置種群規模為30,最大迭代次數為500次。遺傳算法變異概率Pm和交叉概率Pc在經驗范圍內選擇,本文設置Pm=0.02、Pc=0.5。

4.2 仿真結果分析

對比遺傳算法、粒子群算法、貪心算法的實驗結果,開展50次實驗,生產一件成衣的實際總工序時間、最大工序時間、算法的運行時間的平均結果如表3所示。此時,完成生產的平均時間為2 909.5 s,與服裝工廠原先的4 814.4 s相比,生產效率提升約39.6%,且遺傳算法明顯優于貪心算法和粒子群算法。

表3 引入抖動率和基于熟練度的人員調度策略的實驗結果

為了得到合適的抖動率,本文分別在抖動率為0～100%的情況下,對實際總工序時間和最大工序時間進行了對比分析,結果如圖3、圖4所示。當設定的抖動率在60%～100%時,抖動率越小,實際總工序時間越長,對應的最大工序時間越短;反之,抖動率越大,實際總工序時間越短,對應的最大工序時間越長。但是,當抖動率小于60%時,在設定的最大迭代次數內,算法可能無法求解出小于設定的抖動率的解,此時輸出優化后的當前最優解,如圖3、圖4中抖動率為0～50%時所示。因此,服裝廠可根據實際情況選擇合適的抖動率,當服裝廠需要生產線的生產時間更短,可以設置較高的抖動率,以獲得更短的實際總工序時間。經過多次實驗得出結論,如圖5所示,當設定抖動率為60%時,實驗結果標準差相對最小,穩定性最高。

圖3 遺傳算法在不同抖動率下的實際總工序時間Fig.3 Actual total process time of GA under different jitter rates

圖4 遺傳算法在不同抖動率下的最大工序時間Fig.4 Maximum process time of GA with different jitter rates

圖5 實際總工序時間與最大工序時間的標準差Fig.5 Standard deviation of actual total process time and maximum process time

研究得出基于熟練度的人員調度策略優化后的調度結果甘特圖(圖6)。從圖6中可以看出,前片和組合工序為生產工藝流程圖中的最佳路徑工序組合,可以將其余的工序與之進行并行生產。當最佳路徑工序組合與并行的工序需要同一員工進行生產時,可以延后并行工序的開始時間,確保生產過程平穩有序。

圖6 基于熟練度的人員調度策略優化后的調度結果甘特圖Fig.6 Gantt chart of scheduling results after optimization of personnel scheduling strategy based on proficiency

4.3 不同規模場景性能評估

4.3.1 工廠調度問題的規模定義

中小規模調度問題規模一般不超過20臺機器、50個工件[11]。在文獻[12]中將大規模生產調度問題分為以下幾種情況:設機器數為M,工件數為J:(1)M>20,J>50;(2)M>20,J≤50時,M×J>1 000;(3)M≤20,J>50時,M×J>1 000。

4.3.2 不同規模場景實驗結果

本文分別對不同規模的數據場景進行驗證和算法對比。為兼顧算法收斂速度和解集質量,算法均設置最大迭代次數為500次,設員工數為S,工序數為P。在相同的抖動率下,50次實驗實際總工序時間、實施策略優化后的實際總工序時間、最大工序時間、運行時間的平均結果如表4所示。實驗結果表明,在部分規模場景下,遺傳算法在實際總工序時間上稍差于粒子群算法,但最大工序時間和運行時間明顯優于其他算法。

表4 不同規模場景下算法對比結果

5 結論(Conclusion)

本文首先針對服裝生產線中現有的人員調度問題進行建模,其次提出了基于熟練度的人員調度策略和基于遺傳算法的人員調度方法對該問題進行求解,最后采用服裝廠實際生產數據對策略方法進行驗證。實驗證明,本文提出的策略與方法能夠有效地解決服裝生產線中的人員調度問題,提高生產線生產效率。此外,為了驗證本文所提出的策略與方法在不同規模場景下的有效性,開展了實驗進行策略的性能評估,實驗結果表明,在部分規模場景下,遺傳算法在實際總工序時間上稍差于粒子群算法,但最大工序時間和運行時間明顯優于其他算法。