考慮團(tuán)隊(duì)交互學(xué)習(xí)效應(yīng)的單工作組可中斷任務(wù)調(diào)度模型

李 斌，謝乃明

(南京航空航天大學(xué) 經(jīng)濟(jì)與管理學(xué)院，江蘇 南京 211106)

0 引言

在生產(chǎn)制造和項(xiàng)目開發(fā)等領(lǐng)域，受限于技術(shù)成熟度低、工作量大，生產(chǎn)工藝和加工技術(shù)復(fù)雜或者計(jì)算資源有限、信息交換頻率高等因素，任務(wù)調(diào)度廣泛采用以工作組為單元的模式，例如在高端裝備制造領(lǐng)域，航空發(fā)動機(jī)裝配和復(fù)合材料鋪疊常采用工作班組模式應(yīng)對高難度、高負(fù)荷工作；在軟件項(xiàng)目開發(fā)工作上，通過跨部門、跨公司等組建多個臨時項(xiàng)目組共同處理龐大的軟件開發(fā)工作。在工作組層面的調(diào)度研究將有效解決以工作組為單元的任務(wù)調(diào)度模式效率低下的問題。

單工作組調(diào)度問題指具有一個工作組單元，且該單元由多個工人組成的調(diào)度問題，其包括如何在確定的人員結(jié)構(gòu)下合理安排任務(wù)處理順序，并為每個任務(wù)合理分配工人，以提升整個工作組的加工效率。工作組相關(guān)調(diào)度問題已有諸多研究者開展研究，從日本式單元制造模式(Seru Production System)概念和結(jié)構(gòu)[1]，到多技能工人在工作組生產(chǎn)單元中的分配[2]，再到近幾年的可拆分生產(chǎn)單元[3]，但大多針對由多個機(jī)器單元或虛擬單元組建的調(diào)度系統(tǒng)，如SU等[4-5]將工作組調(diào)度問題轉(zhuǎn)化成二維裝箱問題，并建立一系列混合優(yōu)化算法;江煜舟等[6]針對帶有資源沖突的制造單元在線并行調(diào)度問題，將沖突處理機(jī)制與在線并行調(diào)度算法融合并驗(yàn)證算法優(yōu)越性。針對多單元協(xié)同學(xué)習(xí)問題，如張梅等[7]提出多單元協(xié)同學(xué)習(xí)教學(xué)算法，實(shí)現(xiàn)互異單元間的相互學(xué)習(xí);吳旭輝等[8]將Seru制造單元構(gòu)建與Seru制造單元調(diào)度子問題作為兩個子種群利用協(xié)同機(jī)制進(jìn)行協(xié)同進(jìn)化,從而使調(diào)度方案具有更優(yōu)的性能及均衡性。現(xiàn)有多工作組調(diào)度問題的研究多針對機(jī)器單元或虛擬單元，加工中斷、工作能力和學(xué)習(xí)效應(yīng)的特性與以人為核心的單工作組不同，忽略了工人技能水平的個體差異，如KUO等[9]和YANG等[10]都假設(shè)多能工可以在同樣的技能熟練水平下操作所有作業(yè)。然而，受工作時間和學(xué)習(xí)能力的影響，不同工人對同一種工件的技能熟練度和學(xué)習(xí)速度必然存在差異，這種差異會影響不同工人操作同一項(xiàng)作業(yè)的時間，甚至影響產(chǎn)品質(zhì)量。單工作組生產(chǎn)模式仍廣泛應(yīng)用于高端裝備制造領(lǐng)域，一是考慮人才稀缺和培養(yǎng)難度大，二是考慮設(shè)備成本高，沒有足夠的資源供多工作組同時處理任務(wù)。單工作組是多工作組的基礎(chǔ)單元，針對單工作組的研究將進(jìn)一步加深工作組調(diào)度的研究深度。

學(xué)習(xí)效應(yīng)對復(fù)雜系統(tǒng)任務(wù)調(diào)度有不可忽視的影響，尤其是工作組這類以人員為核心調(diào)度資源的生產(chǎn)系統(tǒng)。學(xué)習(xí)效應(yīng)的理論認(rèn)為，生產(chǎn)一個單位任務(wù)所需的時間會隨著不斷增加的生產(chǎn)數(shù)量而逐漸減少，同時由于加工時間的減少，單位生產(chǎn)成本也在下降。BISKUP[11]首先將學(xué)習(xí)效應(yīng)應(yīng)用在排序問題中，并提出基于位置的學(xué)習(xí)效應(yīng);YANG等[12]首次提出依賴完成時間的學(xué)習(xí)效應(yīng);MOSHEIOV等[13]提出基于位置和工人的學(xué)習(xí)效應(yīng);JIANG等[14]提出基于標(biāo)準(zhǔn)加工時間和工人的學(xué)習(xí)效應(yīng)。在以往學(xué)習(xí)效應(yīng)調(diào)度的研究中，學(xué)習(xí)效應(yīng)模型被廣泛應(yīng)用于半導(dǎo)體制造[15]、車間調(diào)度[16]和服務(wù)業(yè)[17]等領(lǐng)域，但大都忽略了加工單元內(nèi)部對外部學(xué)習(xí)能力的影響，在少數(shù)考慮不同學(xué)習(xí)能力個體間相互影響的研究中，王桂娜等[18]基于成組生產(chǎn)的特點(diǎn)，考慮了學(xué)習(xí)效應(yīng)和遺忘效應(yīng)，用3個模型來表達(dá)成組生產(chǎn)中零件實(shí)際加工時間。肖倩喬等[19]考慮了學(xué)習(xí)曲線對生產(chǎn)過程的動態(tài)作用，研究了人機(jī)兩類資源與員工學(xué)習(xí)能力的動態(tài)變化關(guān)系，并給出多目標(biāo)優(yōu)化模型的求解方法;曹磊等[20]針對存在差異性員工的多目標(biāo)柔性作業(yè)車間調(diào)度問題，構(gòu)建了具有學(xué)習(xí)效應(yīng)的調(diào)度模型;李永林等[21]建立了工件相關(guān)學(xué)習(xí)以最大完工時間為目標(biāo)的多機(jī)流水線調(diào)度模型?，F(xiàn)有研究主要集中在受外部變化影響的學(xué)習(xí)效應(yīng)，受團(tuán)隊(duì)結(jié)構(gòu)變化影響的學(xué)習(xí)效應(yīng)研究較少，但一些復(fù)雜系統(tǒng)工作組受人員結(jié)構(gòu)影響較大，研究具有一定的實(shí)際應(yīng)用意義。

綜上所述，盡管已有部分文獻(xiàn)對多工作組和單工作組進(jìn)行了一些研究，但并沒有相關(guān)文獻(xiàn)研究團(tuán)隊(duì)交互學(xué)習(xí)效應(yīng)以及人員加工可中斷因素下的單工作組調(diào)度問題，學(xué)習(xí)效應(yīng)的調(diào)度問題研究中有諸多模型和方法，但往往忽略了個體對整體學(xué)習(xí)效應(yīng)的影響。隨著國家大力推動高端裝備制造業(yè)發(fā)展和傳統(tǒng)產(chǎn)業(yè)優(yōu)化升級，考慮學(xué)習(xí)效應(yīng)的工作組調(diào)度問題無疑會成為智能制造過渡和發(fā)展的重點(diǎn)。本文以文獻(xiàn)[14]提出的基于標(biāo)準(zhǔn)加工時間和工人的學(xué)習(xí)效應(yīng)模型為基礎(chǔ)，考慮工作組實(shí)際調(diào)度過程中的學(xué)習(xí)效應(yīng)現(xiàn)象和人員加工中斷現(xiàn)象，提出一種團(tuán)隊(duì)交互學(xué)習(xí)效應(yīng)的表征形式，構(gòu)建人員加工過程可中斷的單工作組任務(wù)調(diào)度模型，并設(shè)計(jì)基于啟發(fā)式規(guī)則的精英保留遺傳算法。實(shí)驗(yàn)結(jié)果表明，任務(wù)能在工作組中得以科學(xué)分配，實(shí)現(xiàn)工作組內(nèi)部不同技能水平工人的有效利用和調(diào)度目標(biāo)最優(yōu)，通過不同規(guī)模、不同人員結(jié)構(gòu)的算例，對以工作組為生產(chǎn)單元的制造模式進(jìn)行分析。

1 面向單工作組的團(tuán)隊(duì)交互學(xué)習(xí)效應(yīng)

1.1 團(tuán)隊(duì)交互學(xué)習(xí)效應(yīng)定義與表征

工作組是以勞動分工原則為基礎(chǔ)，把具有相同工作目標(biāo)且相互協(xié)作的工人組織起來的任務(wù)調(diào)度單元，基于工作對象和工藝過程完整性的要求，單人無法完成工作任務(wù)，必須由幾個工人共同完成。與生產(chǎn)小組概念不同的是，后者屬于生產(chǎn)行政組織，是一種勞動協(xié)作組織形式，且往往包含多個工作組。工作組模式自主調(diào)整、自主學(xué)習(xí)、組內(nèi)自主分配等特性使其較好地匹配具有低技術(shù)成熟度、高工作量、復(fù)雜加工技術(shù)或有限計(jì)算資源和高信息交換頻率的任務(wù)調(diào)度場景，但是該模式同樣存在一些容易導(dǎo)致調(diào)度困難的問題：工時的不穩(wěn)定性、人員加工可中斷、不同成員間學(xué)習(xí)效應(yīng)的相互干擾。充分分析以上影響因素，可以優(yōu)化工作組單元的調(diào)度方案，加快我國在高端裝備制造、軟件開發(fā)等領(lǐng)域的發(fā)展。

工作組內(nèi)部，不同水平工人間的合作交互產(chǎn)生團(tuán)隊(duì)交互學(xué)習(xí)效應(yīng)。廣義來說，團(tuán)隊(duì)交互學(xué)習(xí)效應(yīng)曲線受其內(nèi)部結(jié)構(gòu)干涉，整體本身只承受外部變量影響和內(nèi)部結(jié)構(gòu)變化的影響。如工作組加工速度受組內(nèi)高水平技能工和低水平技能工分布的交互影響；某動物族群對環(huán)境的適應(yīng)能力受族群內(nèi)成年(健康/經(jīng)驗(yàn)豐富)個體與幼年(患病/經(jīng)驗(yàn)缺乏)個體比例的影響。以只有3人的工作組生產(chǎn)單元為例，工作組整體工作能力及工作組平均生產(chǎn)水平學(xué)習(xí)曲線受外部作用力和內(nèi)部作用力共同影響(如圖1)，其中外部作用力指工件加工難度、加工環(huán)境、時間、調(diào)度順序等環(huán)境因素對生產(chǎn)曲線的影響，以及遞增規(guī)模報(bào)酬對生產(chǎn)曲線的影響，組內(nèi)作用力指工人間的溝通、相互學(xué)習(xí)等對生產(chǎn)曲線的作用。高水平工人提高整體基礎(chǔ)加工工時和學(xué)習(xí)率水平，低水平工人降低整體基礎(chǔ)加工工時和學(xué)習(xí)率水平。

團(tuán)隊(duì)交互學(xué)習(xí)效應(yīng)表征公式和單工作組調(diào)度模型使用的相關(guān)參數(shù)及變量如表1所示。

表1 模型參數(shù)名稱和解釋

構(gòu)建的單工作組調(diào)度模型中，有以下3個決策變量：

為Mh加工工件Jk的總時間，其中f=max{e|aeh·[ykh]≤Ck}；

1.2 人員加工過程可中斷的學(xué)習(xí)效應(yīng)表征

以復(fù)合材料制造鋪疊工序?yàn)槔?，多名工人組成單工作組完成多個零件的鋪疊操作，工作組內(nèi)部存在一定比例的高、低水平工人。由于鋪疊任務(wù)精細(xì)程度高、用眼強(qiáng)度大、操作難度高，常通過多人成組加工、周期性休息等方式保證鋪疊工序的連續(xù)性，緩解工人疲勞，提高加工精度。多人成組加工導(dǎo)致工作組學(xué)習(xí)效應(yīng)的產(chǎn)生，周期性休息導(dǎo)致人員加工過程中斷，類似現(xiàn)象還廣泛存在于飛機(jī)、輪船等大型設(shè)備制造，衛(wèi)星、雷達(dá)等精密儀器裝配環(huán)節(jié)?；诖耍竟?jié)考慮人員加工過程可中斷對單工作組團(tuán)隊(duì)交互學(xué)習(xí)效應(yīng)進(jìn)行表征。

1.2.1 考慮學(xué)習(xí)效應(yīng)的工件加工時間

(1)

(2)

1.2.2 考慮人員加工中斷的工件加工時間

特別地，a[0]=Sk=Ck-1，即a[0]等于工件Jk的開始加工時間，等于第k-1個工件的結(jié)束加工時間,a[f]表示工件完工之前最后一次發(fā)生人員狀態(tài)變動的時刻。

證明根據(jù)生產(chǎn)工件Jk的所有工人的狀態(tài)變動時刻aeh、beh，分加工過程存在中斷和不存在中斷兩種情況進(jìn)行討論。

情況1工件Jk加工過程存在中斷區(qū)間(如圖2)。

…

情況2工件Jk加工過程不存在中斷區(qū)間。

證畢。

(3)

2 考慮團(tuán)隊(duì)交互學(xué)習(xí)效應(yīng)的單工作組調(diào)度模型構(gòu)建

2.1 模型構(gòu)建

2.1.1 背景和假設(shè)

本節(jié)基于定理1構(gòu)建考慮團(tuán)隊(duì)交互學(xué)習(xí)效應(yīng)的單工作組調(diào)度模型并設(shè)計(jì)求解算法，由1.2節(jié)可求得每個工件加工的Pk，Sk，Ck。該模型的建立基于以下假設(shè)：

(1)工人加工過程中斷后，工人的學(xué)習(xí)水平不退化；

(2)任務(wù)加工可由1-n完成，n表示工件的基本需求人數(shù)；

(3)當(dāng)同時刻所有人員處于中斷區(qū)間時，工件加工中斷，此時該中斷與“產(chǎn)品制造期可中斷”一致；

(4)同類工件，即工人的學(xué)習(xí)過程可以在不同工件間遷移和延續(xù)；

(5)單工作組不允許多個工件同時加工，當(dāng)該工件加工完成時，分配到該工件的工人才可以釋放；

(6)工件正在加工時，若該工件尚未完工，則工人不進(jìn)行學(xué)習(xí)時間的更新。

2.1.2 目標(biāo)函數(shù)和約束

minCmax。

(4)

s.t.

(5)

e=1,2,…,θh;k=1,2,…,n;h=1,2,…,l;

(6)

(7)

e=1,2,…,θh;k=1,2,…,n;

(8)

e=1,2,…,θh;k=1,2,…,n;

(9)

f=max{e|aeh·[ykh]≤Ck};

(10)

Ck=Sk+Pk,k=1,2,…,n;

(11)

xkh≤Pk,k=1,2,…,n;h=1,2,…,l;

(12)

Ck-1≤Sk,k=1,2,…,n;

(13)

Si[yih]+Pi[yih]+Pi+1[yi+1,h]+…+

Pj[yj-1,h]≤Sj[yjh],i=1,2,…,n;

j=1,2,…,n;i

(14)

其中：式(4)表示以最小化最大完工時間為目標(biāo)函數(shù)；式(5)限制同一時刻每個工人只能加工一個工件；式(6)限制工人Mh被分配到工件Jk，在工件Jk完工前該工人不可以被分配其他工件；式(7)限制每個工件只能被加工一次，且加工人數(shù)等于工件需求人數(shù)；式(8)限制工件Jk在同一時刻t處于加工狀態(tài)的高水平工人數(shù)不能超過分配的高水平總?cè)藬?shù);式(9)限制工件Jk在同一時刻t處于加工狀態(tài)的低水平工人數(shù)不能超過分配的低水平總?cè)藬?shù)；式(10)定義工件Jk加工時間Pk的計(jì)算公式；式(11)限制完工時間等于開始時間與工件實(shí)際加工時間之和；式(12)限制工人加工工件Jk的總時間不大于工件的實(shí)際加工時間；式(13)限制工件Jk開始加工時間大于上一個工件Jk-1完工時間；式(14)限制同一工人被分配到其他工件進(jìn)行加工時，工人加工該工件的開始時間不小于原工件結(jié)束時間。

因此,該數(shù)學(xué)模型不易求解，本文提出基于啟發(fā)式規(guī)則的精英保留遺傳算法(elitist Genetic Algorithm, e-GA)求解方法。

2.2 基于e-GA的求解方法設(shè)計(jì)

基于2.1節(jié)的模型和復(fù)雜度分析，為保證種群最優(yōu)排序的遺傳，提高大規(guī)模算例求解效率的同時獲得全局最優(yōu)解，本研究結(jié)合啟發(fā)式規(guī)則設(shè)計(jì)e-GA求解該調(diào)度問題。該算法的主要思想是：基于啟發(fā)式規(guī)則進(jìn)行人員分配，識別人員加工過程中斷點(diǎn)并計(jì)算適應(yīng)度值，將種群在進(jìn)化過程中出現(xiàn)的精英個體不進(jìn)行配對和交叉,而直接復(fù)制到下一代中，染色體編碼方式按照工件加工順序編碼。

考慮團(tuán)隊(duì)交互學(xué)習(xí)效應(yīng)的單工作組調(diào)度問題設(shè)計(jì)的啟發(fā)式規(guī)則主要分為人員分配和人員加工中斷點(diǎn)識別兩部分：①快速初始化較優(yōu)種群，針對工人已學(xué)習(xí)時長完成工人和任務(wù)的匹配,并生成一個任務(wù)處理順序;②依據(jù)中斷區(qū)間尋找處于中斷加工狀態(tài)的工人，更新工人中斷點(diǎn)集合?？紤]團(tuán)隊(duì)交互學(xué)習(xí)效應(yīng)的單工作組調(diào)度問題求解困難，該啟發(fā)式規(guī)則與e-GA的精英保留策略相結(jié)合，實(shí)現(xiàn)快速求得最優(yōu)解。

2.2.1 外部啟發(fā)式規(guī)則

外部啟發(fā)式規(guī)則主要分為人員分配和人員加工中斷點(diǎn)識別兩個部分，基本步驟如下：

(1)更新工作組人員總學(xué)習(xí)時長，結(jié)合學(xué)習(xí)水平對工人進(jìn)行分組；

(4)依據(jù)中斷區(qū)間尋找中斷加工的工人，更新中斷點(diǎn)集合，重新計(jì)算理想加工時間，重復(fù)步驟(2)；

當(dāng)count=f=max{e|aeh·[ykh]≤Ck}時，更新所有工人的加工時間，更新中斷區(qū)間列表。

2.2.2 內(nèi)部精英保留策略

基于啟發(fā)式規(guī)則的e-GA算法中精英保留策略的實(shí)現(xiàn)步驟為：

(1)設(shè)到第t代時，群體中a(t)為最優(yōu)個體；

(2)設(shè)A(t+1)為新一代群體，挑選A(t+1)中的最優(yōu)個體；

(3)若A(t+1)中沒有比a(t)優(yōu)的個體，則a(t)加入A(t+1)中作為A(t+1)的第n+1個個體(n為群體大小)。

2.2.3 基于啟發(fā)式規(guī)則的e-GA步驟

將外部啟發(fā)式規(guī)則和內(nèi)部精英保留策略融合到遺傳算法中，該算法的迭代步驟(如圖3)如下：

(1)初始化并生成問題對象，讀取工人基本信息和工件基本信息；

(2)生成初始調(diào)度方案種群，在編碼規(guī)定的范圍內(nèi)隨機(jī)生成具有n個個體的初始種群；

(3)保留精英個體，通過人員分配和人員加工中斷點(diǎn)識別計(jì)算個體適應(yīng)度，保留適應(yīng)度值最好的個體；

(4)產(chǎn)生新種群，通過精英保留進(jìn)行遺傳、交叉、變異產(chǎn)生子代種群，并計(jì)算子代種群個體的適應(yīng)度值；

(5)精英個體更新，若子代最優(yōu)個體比精英個體更優(yōu)，則證明子代種群完成進(jìn)化，此時將父代精英個體替代子代最劣個體，子代最優(yōu)個體成為新的精英個體；

(6)判斷是否達(dá)到終止準(zhǔn)則，若達(dá)到則迭代終止，退出尋優(yōu)，輸出精英個體和調(diào)度信息；否則重復(fù)步驟(4)。

2.2.4 交叉、變異及終止準(zhǔn)則

設(shè)計(jì)“部分匹配交叉”為交叉策略，步驟如下：

(1)確定父代初始種群染色體；

(2)隨機(jī)產(chǎn)生小于父代染色體長度的正整數(shù)；

(3)互換父代染色體中對應(yīng)該長度與位置的染色體片段；

(4)保持被交換的片段不動，在沒有交換的片段中尋找重復(fù)值，然后在父代被換走的部分中找到對應(yīng)位置的元素進(jìn)行替換，以消除替換后染色體中的重復(fù)編碼。

設(shè)計(jì)“逆轉(zhuǎn)變異”為變異策略，步驟如下：

(1)確定父代初始種群染色體；

(2)隨機(jī)生成兩個小于父代染色體長度的正整數(shù)a和b，a

(3)在父代染色體編碼上選擇a和b兩個點(diǎn)作為逆轉(zhuǎn)開始點(diǎn)和逆轉(zhuǎn)結(jié)束點(diǎn)，

(4)將逆轉(zhuǎn)開始點(diǎn)和逆轉(zhuǎn)結(jié)束點(diǎn)之間的基因進(jìn)行逆向排序得到變異后的染色體。

算法終止準(zhǔn)則為：當(dāng)達(dá)到遺傳算法的最大迭代次數(shù)后，算法結(jié)束，輸出當(dāng)前適應(yīng)度值最高的的任務(wù)調(diào)度方案。

3 算例分析

3.1 數(shù)值仿真

某工廠任務(wù)處理過程以工作組為調(diào)度單元，有10人制和20人制兩種規(guī)模的工作組,工人獨(dú)立加工工件的基本人時在[30,80]隨機(jī)分布，高水平工人學(xué)習(xí)率為30%(學(xué)習(xí)因子=-0.3)，低水平工人學(xué)習(xí)率為10%(學(xué)習(xí)因子=-0.1)，由式(2)可知，考慮學(xué)習(xí)效應(yīng)后的加工時間與基本加工時間呈指數(shù)關(guān)系，由于學(xué)習(xí)能力越強(qiáng)的工人加工時間越短，用學(xué)習(xí)因子代替學(xué)習(xí)率以便于單工作組團(tuán)隊(duì)交互學(xué)習(xí)效應(yīng)表征公式的計(jì)算，學(xué)習(xí)因子為負(fù)值表示學(xué)習(xí)效應(yīng)，正值表示退化效應(yīng)。本文主要研究具有學(xué)習(xí)效應(yīng)的工作組調(diào)度問題，因此高水平工人學(xué)習(xí)因子為-0.3，低水平工人學(xué)習(xí)因子為-0.1。每個工人有3個中斷區(qū)間，10人制工作組的中斷區(qū)間在[0,41]內(nèi)以固定步長0.5分布，加工編號為1～10的零件；20人制工作組的中斷區(qū)間在[0,61]內(nèi)以固定步長0.5分布，加工編號為1～20的零件；現(xiàn)有一批共20個同零件族工件Jk，JMk和[Pk]如表2所示。中規(guī)模工作組需保證10個工件的調(diào)度方案最優(yōu)；大規(guī)模工作組需保證20個工件的調(diào)度方案最優(yōu)。

表2 工件基本需求人數(shù)和基本工時

根據(jù)上述參數(shù)設(shè)定和算例數(shù)據(jù)，對考慮團(tuán)隊(duì)交互學(xué)習(xí)效應(yīng)的單工作組可中斷任務(wù)調(diào)度問題進(jìn)行仿真實(shí)驗(yàn)。在小規(guī)模算例驗(yàn)證設(shè)計(jì)的e-GA算法準(zhǔn)確性后，通過測試不同人員結(jié)構(gòu)比例和不同學(xué)習(xí)率水平下最大加工時間的優(yōu)化目標(biāo)，分析高、低水平人員比例和學(xué)習(xí)因子對優(yōu)化目標(biāo)的影響。

3.2 算法性能分析

由于模型非線性，且為混合整數(shù)規(guī)劃模型，加工時間隨分配人員的變化而變化，約束數(shù)量與分配人員對應(yīng)的中斷區(qū)間和總學(xué)習(xí)時長有關(guān)，精確式求解器難以解決該問題，即便是小規(guī)模算例。研究首先驗(yàn)證設(shè)計(jì)的改進(jìn)精英保留遺傳算法(NIND=20；MAXGEN=200/400；XOVR=0.8；Pm=0.2)有效性(NIND為種群規(guī)模；MAXGEN為最大迭代數(shù)；XOVR為交叉概率；Pm為變異概率)，進(jìn)一步在更大規(guī)模算例上與一般遺傳算法、模擬退火算法對比，驗(yàn)證改進(jìn)遺傳算法的優(yōu)勢。其中，遺傳算法(NIND=20；MAXGEN=200/400；XOVR=0.8；Pm=0.2)和模擬退火算法(T_MAX=500,T_MIN=1,IterMax=50/100,RATE=0.9)都采用進(jìn)化方式控制優(yōu)化過程(T_MAX為最大溫度；T_MIN為最小溫度；IterMax為迭代次數(shù)；RATE為降溫速率)，但模擬退火算法是采用單個個體進(jìn)行進(jìn)化的典型算法，局部搜索能力強(qiáng)，全局搜索能力差，容易受到參數(shù)的影響；而遺傳算法是采用種群進(jìn)行進(jìn)化的典型算法，能很好地處理約束，全局優(yōu)化能力較強(qiáng)。

實(shí)驗(yàn)仿真環(huán)境為：Windows 10 64位操作系統(tǒng)，CPU為Intel(R)Core(TM)i5-6300HQ，處理器主頻為2.30 GHz，12 G內(nèi)存，編程環(huán)境為Python 3.7.7。

由表3和表4可以看出，模擬退火算法求解該問題在求解精度和求解效率上均較低，傳統(tǒng)GA與改進(jìn)e-GA在小規(guī)模問題上的求解精度差距不明顯，但隨著問題規(guī)模的增大，求解效率明顯弱于改進(jìn)e-GA。

表3 不同規(guī)模算例下改進(jìn)e-GA、GA、SA性能對比

表4 算法結(jié)果統(tǒng)計(jì)分析

3.3 調(diào)度方案分析

在10個工件、10名工人和20個工件、20名工人兩種情景中設(shè)置11組不同人員結(jié)構(gòu)的算例，人員比例分別為0∶10、1∶9、2∶8、3∶7、4∶6、5∶5、6∶4、7∶3、8∶2、9∶1、10∶0。為提高求解效率，設(shè)計(jì)e-GA算法(NIND=20；MAXGEN=200/400；XOVR=0.8；Pm=0.2)進(jìn)行求解。11組算例均在設(shè)置的迭代次數(shù)內(nèi)收斂。每個最優(yōu)調(diào)度方案的加工順序和加工時間如圖4和圖5所示，圖中scheme1～scheme11高水平工人的比例逐漸提升，最優(yōu)方案的最大完工時間隨高水平工人比例提高逐漸縮短。

進(jìn)一步分析最大完工時間隨人員比例變化的規(guī)律，設(shè)置4組不同學(xué)習(xí)水平(低水平工人學(xué)習(xí)因子：高水平工人學(xué)習(xí)因子)——-0.1:-0.2(學(xué)習(xí)水平1)；-0.1:-0.3(學(xué)習(xí)水平2)；-0.2:-0.3(學(xué)習(xí)水平3)；-0.2:-0.4(學(xué)習(xí)水平4)。由圖6和圖7可以看出，整體上隨著高水平工人占比的提高，最大加工時間的減小速度逐漸放緩，且工人學(xué)習(xí)水平越高，最大完工時間越短；用面積表示學(xué)習(xí)水平提高帶來的工時收益，高水平工人學(xué)習(xí)因子減少0.1大于低水平工人學(xué)習(xí)因子減少0.1帶來的工時收益。從個體來看，學(xué)習(xí)水平2下最大完工時間隨人員比例降低幅度最大，在比例小于5∶5時，學(xué)習(xí)水平2的最大完工時間降低速度最快，學(xué)習(xí)水平3中高、低水平工人學(xué)習(xí)因子差異最小，最大完工時間隨人員比例變化幅度也最小。因此，在工人學(xué)習(xí)能力差異較大的情況下，考慮工時收益和成本，適當(dāng)提高高水平工人占比可以帶來更大的收益。

3.4 工人學(xué)習(xí)均衡率分析

工作組工人學(xué)習(xí)均衡率通過工作組各工人學(xué)習(xí)時間占基本工時比率的方差衡量。該指標(biāo)一方面反映工人負(fù)荷的均衡情況，另一方面可以反映人員結(jié)構(gòu)對調(diào)度方案中工人學(xué)習(xí)進(jìn)度的影響。

為分析高、低水平工人比例對工人學(xué)習(xí)時間均衡率的影響，首先以低水平工人學(xué)習(xí)因子：高水平工人學(xué)習(xí)因子=-0.1∶-0.3為例，觀察10個工件和20個工件總學(xué)習(xí)時間(如圖8和圖9)發(fā)現(xiàn)，比例1∶9下，唯一的高水平工人總學(xué)習(xí)時間最長，比例9∶1下，唯一的低水平工人總學(xué)習(xí)時間最短，隨著高水平工人占比的提高，低水平工人的總學(xué)習(xí)時間逐漸縮短，在比例7∶3下，高低水平工人學(xué)習(xí)時間出現(xiàn)顯著差異。進(jìn)一步分析工人學(xué)習(xí)均衡率，比例0∶10和比例10∶0下，總學(xué)習(xí)時間方差最低，均衡率最高；比例1∶9和比例9∶1下均衡率出現(xiàn)明顯波動。說明當(dāng)人員結(jié)構(gòu)失衡嚴(yán)重時，易導(dǎo)致工作負(fù)荷分配不均。

進(jìn)一步分析人員結(jié)構(gòu)對學(xué)習(xí)均衡率的影響。通過圖10和圖11可以看出，比例0∶10、5∶5和10∶0下，方差最低，均衡率最高；比例1∶9和9∶1下，方差顯著升高，均衡率降低；比例7∶3下，方差出現(xiàn)波動，均衡率水平較低；其他比例下方差雖有波動，但均衡率水平均較高。

3.5 靈敏度分析

靈敏度分析是從定量分析的角度出發(fā)，研究某些因素發(fā)生變化時對目標(biāo)值的影響程度，是一種不確定分析技術(shù)，通常用靈敏度系數(shù)來表示。SCP表示目標(biāo)值C對目標(biāo)因素P的靈敏度系數(shù)；ΔP/P表示目標(biāo)因素P的變化率；ΔC/C表示目標(biāo)因素P發(fā)生ΔP的變化時，目標(biāo)值C發(fā)生ΔC的變化時C相應(yīng)的變化率。SCP的絕對值越大，目標(biāo)值C對因素P的變化越靈敏，反之越不靈敏。計(jì)算公式如下:

(15)

由表5可知，在學(xué)習(xí)水平2和學(xué)習(xí)水平4時，不同置換比例下最大加工時間的靈敏度系數(shù)均大于0.5，表明置換比例屬于較敏感的因素；中規(guī)模算例中低水平工人比率減少10%和40%時，Cmax靈敏度最高；在減少50%至更多時，靈敏度逐漸降低；大規(guī)模算例中靈敏度系數(shù)均較高，當(dāng)置換比例大于50%時，靈敏度水平與中規(guī)?；境制健？紤]增加高水平工人時成本投入也會相應(yīng)提高，可以根據(jù)實(shí)際加工需要確定合適的置換比例：

(1)當(dāng)工期寬松時，選擇低水平工人降低10%～30%，即10%～30%的低水平工人被置換為高水平工人，在提高工作效率的同時，保證人員投入的效用比最高；

(2)當(dāng)工期緊張時，選擇低水平工人降低40%或50%，保證工期準(zhǔn)時完成及人員投入的效用比最高；

(3)當(dāng)?shù)椭脫Q比率下工期不能按時完成，單純置換60%及以上的低水平工人無法顯著縮短工期，犧牲可接受范圍內(nèi)的效用比，置換學(xué)習(xí)水平更高的工人以按時完成工期。

表5 不同學(xué)習(xí)水平下的靈敏度系數(shù)表

“人員加工可中斷”基于實(shí)際生產(chǎn)問題中長時間工作時的強(qiáng)制休息規(guī)則，通過中斷區(qū)間的固定步長表征，作為一固定參數(shù)反映其對工人學(xué)習(xí)進(jìn)程的影響，主要表現(xiàn)為中斷時間越長，對學(xué)習(xí)效應(yīng)的抑制作用越大，即工人操作熟練度退化的可能性越大；中斷時間越長，對工人效率的促進(jìn)作用越強(qiáng)，即工人休息時間越長，工作效率越高。基于假設(shè)(1)：工人加工過程中斷后，工人的學(xué)習(xí)水平不退化，本節(jié)僅考慮“人員加工中斷”對工人效率的促進(jìn)作用。如3.1節(jié)所述，工作組工人的加工中斷區(qū)間在一個閉區(qū)間內(nèi)以固定步長分布，設(shè)固定步長的倒數(shù)為加工時間的促進(jìn)/抑制程度，表征強(qiáng)制休息對工作效率的影響。以中斷區(qū)間長度為目標(biāo)因素，對目標(biāo)值C進(jìn)行靈敏度分析。

由表6可知，當(dāng)目標(biāo)因素變化率大于0.1時，最大加工時間的靈敏度系數(shù)均大于0.5，表明人員加工中斷區(qū)間長度屬于敏感因素。當(dāng)目標(biāo)因素變化率在0.2～0.5之間時，最大加工時間的靈敏度系數(shù)高于平均值，表明在不考慮人員加工中斷造成的學(xué)習(xí)水平退化時，可在該范圍內(nèi)根據(jù)實(shí)際加工需要調(diào)整工人的強(qiáng)制休息時間。

表6 不同人員加工中斷區(qū)間長度下的靈敏度系數(shù)表

續(xù)表6

4 結(jié)束語

本文提出了一種考慮團(tuán)隊(duì)交互學(xué)習(xí)效應(yīng)的單工作組調(diào)度問題，面向該問題構(gòu)建了考慮團(tuán)隊(duì)交互學(xué)習(xí)效應(yīng)和人員加工可中斷的單工作組調(diào)度模型，給出了基于啟發(fā)式規(guī)則的e-GA模型求解方法，最后通過不同規(guī)模的算例仿真演示了所構(gòu)建模型和算法的有效性。主要貢獻(xiàn)總結(jié)如下：

(1)分析和表征了工作組單元中的團(tuán)隊(duì)交互學(xué)習(xí)效應(yīng)，考慮實(shí)際問題中出現(xiàn)的人員加工可中斷現(xiàn)象，實(shí)現(xiàn)單工作組調(diào)度問題工時等相關(guān)數(shù)據(jù)誤差的降低和工作組關(guān)鍵資源的最優(yōu)化匹配。

(2)構(gòu)建了考慮團(tuán)隊(duì)交互學(xué)習(xí)效應(yīng)和人員加工可中斷的單工作組調(diào)度模型和算法，實(shí)現(xiàn)單工作組人員分配和工件調(diào)度的有機(jī)結(jié)合，提高以工作組為加工單元的生產(chǎn)系統(tǒng)加工效率，彌補(bǔ)了過往將工作組視為整體，忽略人與人之間學(xué)習(xí)水平差異的問題。

(3)利用Python實(shí)現(xiàn)基于e-GA的算例仿真，并對比不同規(guī)模的算例結(jié)果驗(yàn)證了模型及算法的有效性，詳細(xì)分析工作組人員結(jié)構(gòu)、人員加工可中斷區(qū)間長度對調(diào)度結(jié)果的影響，為實(shí)際生產(chǎn)中置換比例、工人強(qiáng)制休息時間的確定提供指導(dǎo)。

考慮團(tuán)隊(duì)交互學(xué)習(xí)效應(yīng)的單工作組任務(wù)調(diào)度問題是區(qū)別于其他工作組調(diào)度問題的一類新問題，研究對工作組生產(chǎn)系統(tǒng)做了簡化，對單工作組的研究可以繼續(xù)拓展到具有多工作組、多工位特征的分布式工作組調(diào)度問題。同時，工作組調(diào)度多出現(xiàn)在復(fù)雜任務(wù)處理過程中，生產(chǎn)環(huán)境復(fù)雜，考慮因素多，可結(jié)合交期目標(biāo)、學(xué)習(xí)均衡目標(biāo)、人員費(fèi)用目標(biāo)等對該問題進(jìn)行深入探討。