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

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

0 引言(Introduction)

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

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

1 研究現(xiàn)狀(Research status)

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

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

2 服裝生產(chǎn)線人員調(diào)度模型(Personnel scheduling model of garment production line)

2.1 調(diào)度問題描述

服裝企業(yè)需要解決的問題是在保證員工合理的工作時間和生產(chǎn)線平衡率的同時,以縮短生產(chǎn)時間為目標,制訂訂單生產(chǎn)調(diào)度計劃。在服裝廠生產(chǎn)調(diào)度計劃制訂過程中,該調(diào)度問題可以被描述為有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)}。調(diào)度目標是將所有訂單中不同的工序分配給員工,以實現(xiàn)所有訂單實際總工序時間最小化。

2.2 符號定義

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

(1)

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

(2)

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

(3)

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

(4)

2.3 調(diào)度模型

2.3.1 優(yōu)化目標

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

(5)

2.3.2 約束條件

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

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

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

3.1 基于熟練度的人員調(diào)度策略構(gòu)建

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

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

3.2 基于遺傳算法的人員調(diào)度方法

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

3.2.1 染色體編碼

本文構(gòu)建了一個一維數(shù)組,采用基于數(shù)組的實數(shù)編碼方法,染色體中的基因代表對應(yīng)工序所安排的員工序號。

3.2.2 遺傳算法設(shè)計

基于遺傳算法對生產(chǎn)線人員進行調(diào)度優(yōu)化,算法設(shè)計實現(xiàn)過程如下。

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

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

(9)

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

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

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

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

3.3 基于粒子群算法的人員調(diào)度方法

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

3.3.1 粒子群算法設(shè)計

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

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

若粒子當前的適應(yīng)值比之前記錄的該粒子歷史最優(yōu)解pbest更好,則更新pbest。

若粒子當前的適應(yīng)值比之前記錄的全局最優(yōu)解gbest更好,則更新gbest。

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

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)的隨機數(shù),ω是慣性權(quán)重因子,c1和c2稱為加速因子或?qū)W習因子。

3.4 基于貪心算法的人員調(diào)度方法

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

3.4.1 貪心算法設(shè)計

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

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

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

(4)重復(fù)以上步驟,直至所有員工的總加工時間滿足最大工序時間,或者達到設(shè)定的循環(huán)次數(shù)時,結(jié)束循環(huán),輸出當前的最優(yōu)結(jié)果。

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

4.1 工廠數(shù)據(jù)集性能評估

4.1.1 服裝企業(yè)背景

本文以杭州某服裝廠為例。為了滿足市場需求,服裝廠的生產(chǎn)模式由原來的大批量生產(chǎn)轉(zhuǎn)變?yōu)槎嘤唵?、個性化小批量生產(chǎn)。由于訂單之間存在差異,所以服裝廠每接一個訂單就需要制訂對應(yīng)的生產(chǎn)計劃。

4.1.2 工藝數(shù)據(jù)

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

表1 員工熟練度表

表2 款式工序表

圖2 連衣裙生產(chǎn)工藝流程圖Fig.2 Process flow chart of skirt production

4.1.3 算法參數(shù)設(shè)置

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

4.2 仿真結(jié)果分析

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

表3 引入抖動率和基于熟練度的人員調(diào)度策略的實驗結(jié)果

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

圖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

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

圖6 基于熟練度的人員調(diào)度策略優(yōu)化后的調(diào)度結(jié)果甘特圖Fig.6 Gantt chart of scheduling results after optimization of personnel scheduling strategy based on proficiency

4.3 不同規(guī)模場景性能評估

4.3.1 工廠調(diào)度問題的規(guī)模定義

中小規(guī)模調(diào)度問題規(guī)模一般不超過20臺機器、50個工件[11]。在文獻[12]中將大規(guī)模生產(chǎn)調(diào)度問題分為以下幾種情況:設(shè)機器數(shù)為M,工件數(shù)為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 不同規(guī)模場景實驗結(jié)果

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

表4 不同規(guī)模場景下算法對比結(jié)果

5 結(jié)論(Conclusion)

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