考慮需求波動(dòng)的單元裝配系統(tǒng)構(gòu)建問(wèn)題的多目標(biāo)模型

王 曄，唐加福，趙林度

(1.東北財(cái)經(jīng)大學(xué)管理科學(xué)與工程學(xué)院，遼寧 大連 116025；2.東南大學(xué)經(jīng)濟(jì)管理學(xué)院， 江蘇 南京 210096)

1 引言

在全球經(jīng)濟(jì)一體化的過(guò)程中，制造業(yè)的發(fā)展扮演著不可或缺的角色。根據(jù)德勤公司的2016年全球制造業(yè)競(jìng)爭(zhēng)指數(shù)調(diào)查的結(jié)果顯示，制造業(yè)對(duì)全球的經(jīng)濟(jì)發(fā)展都起到了關(guān)鍵帶動(dòng)作用，包括基礎(chǔ)設(shè)施提升、增加就業(yè)崗位、對(duì)全民GDP以及人均GDP的貢獻(xiàn)率等[1]。隨著人工智能和高新技術(shù)與民用產(chǎn)品的結(jié)合，當(dāng)今市場(chǎng)呈現(xiàn)對(duì)產(chǎn)品智能化、多樣化的更高需求。在市場(chǎng)需求的變化下，生產(chǎn)制造企業(yè)在應(yīng)對(duì)多品種、小批量且生命周期短的產(chǎn)品生產(chǎn)過(guò)程中面臨巨大的考驗(yàn)，并不斷探索應(yīng)對(duì)方式。例如通過(guò)供應(yīng)商和制造商之間的訂單分配[2]，平衡生產(chǎn)和庫(kù)存[3-4]以及協(xié)調(diào)制造商和銷售商[5]等方式實(shí)現(xiàn)總體利潤(rùn)最大化，與此同時(shí)，制造企業(yè)內(nèi)部生產(chǎn)流程的優(yōu)化也是提升企業(yè)整體競(jìng)爭(zhēng)力的重要環(huán)節(jié)。

日本制造企業(yè)在20世紀(jì)80年代的經(jīng)濟(jì)大發(fā)展時(shí)期由于需求的迅速增長(zhǎng)，引進(jìn)了大批的生產(chǎn)線設(shè)備進(jìn)行大規(guī)模生產(chǎn)。然而，90年代經(jīng)濟(jì)泡沫破滅的連鎖反應(yīng)導(dǎo)致日本制造業(yè)面臨前所未有的挑戰(zhàn)。由于市場(chǎng)對(duì)產(chǎn)品的需求轉(zhuǎn)變，原有的流水線生產(chǎn)方式明顯無(wú)法應(yīng)對(duì)高技術(shù)附加值、生命周期短等特點(diǎn)的產(chǎn)品生產(chǎn)，日本式單元制造模式應(yīng)運(yùn)而生[6-8]。日本式單元制造系統(tǒng)(Seru production system)是由以佳能、索尼等日本電子裝配業(yè)公司的不斷探索實(shí)踐中總結(jié)出來(lái)的一種先進(jìn)生產(chǎn)組織方式。它融合了西方傳統(tǒng)單元制造、日本精益生產(chǎn)和敏捷制造等生產(chǎn)模式的特點(diǎn)，兼?zhèn)淞魉€的高效性、傳統(tǒng)單元制造的靈活性以及精益生產(chǎn)的低成本，以應(yīng)對(duì)多品種、中小批量，特別是變批量的生產(chǎn)方式[7-10]。Seru是日語(yǔ)中英文單詞cell的發(fā)音，源于西方傳統(tǒng)單元制造(Cellular manufacturing)中的cell一詞。Seru是指為完成一個(gè)或多個(gè)產(chǎn)品的組裝，由一個(gè)或多個(gè)員工和一些設(shè)備組成的一個(gè)裝配單元，主要實(shí)現(xiàn)形式為以裝配單元取代原有的傳送帶，即流水線裝配向單元裝配的轉(zhuǎn)換[9]。

有關(guān)日本式單元裝配系統(tǒng)的研究由日本的企業(yè)界和學(xué)者最先總結(jié)歸納[11-12]，并得到了各國(guó)學(xué)者的廣泛關(guān)注[7-10]，其中日本式單元構(gòu)建研究成為研究的重點(diǎn)[13-21]。Kaku等[13]最先提出以最小化總產(chǎn)出時(shí)間和總加工時(shí)間為目標(biāo)，構(gòu)建流水線裝配和單元裝配混合系統(tǒng)的多目標(biāo)優(yōu)化模型，以數(shù)值仿真的方法驗(yàn)證模型的有效性并分析了產(chǎn)品種類、批次數(shù)量、批次大小以及任務(wù)規(guī)模對(duì)目標(biāo)函數(shù)的影響。Liu Chenguang等[16]考慮由流水線裝配向單元裝配系統(tǒng)轉(zhuǎn)換過(guò)程中的工人培訓(xùn)成本，以最小化培訓(xùn)成本和加工周期為目標(biāo)進(jìn)行單元系統(tǒng)的構(gòu)建。Yu Yang等[17-21]對(duì)流水線裝配向純單元裝配系統(tǒng)轉(zhuǎn)換的問(wèn)題進(jìn)行研究，以最小化總加工時(shí)間和最小化工人加工時(shí)間以及以減人為目標(biāo)建模。以上研究的一個(gè)共同點(diǎn)是，針對(duì)(每天)特定的生產(chǎn)任務(wù)(包括產(chǎn)品種類和數(shù)量)，在流水線向單元裝配轉(zhuǎn)化的生產(chǎn)場(chǎng)景下，給出相應(yīng)的單元裝配系統(tǒng)(混合單元裝配線或純單元裝配線)以及生產(chǎn)調(diào)度方案。這種單元裝配系統(tǒng)的好處是，柔性好，針對(duì)任何不同的生產(chǎn)任務(wù)(需求)，產(chǎn)品種類和批量大小，均能適應(yīng)的裝配單元系統(tǒng)；然而，該系統(tǒng)的缺點(diǎn)是，由于現(xiàn)實(shí)需求的波動(dòng)(包括產(chǎn)品種類和批量大小)和不穩(wěn)定，制造企業(yè)需要頻繁進(jìn)行生產(chǎn)系統(tǒng)的構(gòu)建，這樣不僅造成資源閑置和浪費(fèi)(如新添置工作平臺(tái)、輔助性的移動(dòng)設(shè)施和工具等)，而且單元內(nèi)部的人員頻繁調(diào)整，合作不穩(wěn)定，生產(chǎn)效率受到相應(yīng)影響。另外，在實(shí)際的制造企業(yè)中，頻繁調(diào)整生產(chǎn)線也不容易被接受。Yu Yang等[17-21]雖然提出生產(chǎn)任務(wù)的批次種類和批次大小按照相應(yīng)規(guī)律隨機(jī)生成，但在優(yōu)化的過(guò)程仍是按照已知的任務(wù)進(jìn)行。利用現(xiàn)有的研究成果進(jìn)行單元系統(tǒng)的構(gòu)建會(huì)產(chǎn)生較高的單元系統(tǒng)重構(gòu)成本以及工人頻繁變動(dòng)引起的工人滿意度下降、管理成本過(guò)高等問(wèn)題。因此，在既要保證系統(tǒng)柔性，同時(shí)兼顧效率和穩(wěn)定性，考慮面向一定周期的單元裝配系統(tǒng)的構(gòu)建具有十分重要的現(xiàn)實(shí)意義，不僅豐富和發(fā)展單元系統(tǒng)構(gòu)建的理論，而且也為生產(chǎn)管理者提供更為貼近現(xiàn)實(shí)生產(chǎn)環(huán)境的單元構(gòu)建方法。

針對(duì)這一不足，本文的主要貢獻(xiàn)是討論需求波動(dòng)情境下的流水線裝配向單元裝配系統(tǒng)的轉(zhuǎn)換問(wèn)題?？偧庸ぶ芷?Make span)的大小直接關(guān)系到產(chǎn)品的交貨期，通過(guò)縮小總加工周期可以直接提升企業(yè)在動(dòng)態(tài)多樣化的市場(chǎng)上的競(jìng)爭(zhēng)力。因此本文為避免由于需求波動(dòng)引起的單元系統(tǒng)重構(gòu)成本，通過(guò)建立考慮需求波動(dòng)的流水裝配向單元裝配系統(tǒng)轉(zhuǎn)換方案，決策需要構(gòu)建的裝配單元的數(shù)量、工人與裝配單元之間的分配方式以及產(chǎn)品批次向單元的分配方法，構(gòu)建需求波動(dòng)情境下最小化總加工周期的期望和方差的單元構(gòu)建多目標(biāo)優(yōu)化模型。其中最小化總加工時(shí)間的期望值和方差值分別是為了使系統(tǒng)能在需求波動(dòng)的場(chǎng)景下具備較好的期望性能和較為穩(wěn)定的表現(xiàn)。任務(wù)確定型的流水線裝配向單元裝配系統(tǒng)轉(zhuǎn)換問(wèn)題已在文獻(xiàn)[18]中被證明為NP-hard問(wèn)題，不存在多項(xiàng)式時(shí)間內(nèi)求得最優(yōu)解的精確優(yōu)化算法。本問(wèn)題由于考慮了需求的波動(dòng)性而比原問(wèn)題更為復(fù)雜，因此需采用有效的啟發(fā)式優(yōu)化算法對(duì)問(wèn)題進(jìn)行求解。NSGA-II(Non-dominatedsorting genetic algorithms)算法作為求解多目標(biāo)優(yōu)化問(wèn)題的啟發(fā)式算法在收斂速度和解的多樣性方面均表現(xiàn)出較好的性能，是目前綜合性能較好且應(yīng)用較為廣泛的多目標(biāo)優(yōu)化算法。本文針對(duì)模型的特點(diǎn)采用基于NSGA-II的算法對(duì)本問(wèn)題進(jìn)行求解，并通過(guò)數(shù)值實(shí)驗(yàn)說(shuō)明模型和方法的運(yùn)用規(guī)則和相關(guān)性質(zhì)。

2 問(wèn)題描述與模型建立

2.1 問(wèn)題描述

Stecke等[9]提出日本式單元裝配系統(tǒng)中的單元(Seru)按照理想程度被分為分割式單元(DivisionalSeru)、巡回式單元(RotatingSeru)以及單人單元(Yatai)，其中最理想的狀態(tài)為單人單元，即每名工人獨(dú)立組成一個(gè)單元，可以直接通過(guò)增減單元的數(shù)量來(lái)應(yīng)對(duì)產(chǎn)品需求的變化。但在實(shí)際企業(yè)的應(yīng)用過(guò)程中，由于考慮到構(gòu)建單元的成本及工人在工作中的互相交流等問(wèn)題，多采用分割式單元和巡回式單元。

圖1 流水線裝配向單元裝配轉(zhuǎn)化(8名工人)

本文采用巡回式單元作為構(gòu)建單元裝配系統(tǒng)的基本單位，即分配到單元內(nèi)的每一名工人獨(dú)立完成所有類型產(chǎn)品所有工序的裝配。當(dāng)多名工人分配到同一個(gè)巡回式單元內(nèi)時(shí)，員工各自按順序完成所分配產(chǎn)品的全部工序，因此巡回式單元也被稱為逐兔式單元。由8名工人組成的流水裝配線轉(zhuǎn)換成巡回式單元系統(tǒng)的轉(zhuǎn)換方式如圖1所示，原流水線上完成第2、4和8號(hào)工序的工人被分配到單元2中。

本文考慮在一個(gè)需求波動(dòng)的環(huán)境下存在S種需求場(chǎng)景，第s種場(chǎng)景出現(xiàn)的概率為ps，∑ps=1。每種場(chǎng)景下的需求均為N種產(chǎn)品的不同批次組合，每種場(chǎng)景會(huì)有M個(gè)批次且每個(gè)批次只有一種產(chǎn)品類型。在此生產(chǎn)環(huán)境下，設(shè)計(jì)由W個(gè)工人組成的流水裝配線向純單元裝配轉(zhuǎn)換的構(gòu)建方案。在生產(chǎn)系統(tǒng)中所有工人均為多能工，即可以獨(dú)立完成任何一種產(chǎn)品類型的全部裝配操作且全部分配到各個(gè)單元中。流水線裝配的節(jié)拍時(shí)間T、完成第n種產(chǎn)品的各工序l的標(biāo)準(zhǔn)加工時(shí)間Tnl(Tnl≤T)以及工序的先后關(guān)系已知。單個(gè)批次的產(chǎn)品全部分配到同一個(gè)單元內(nèi)進(jìn)行加工且批次不拆分。由于工人全部為多能工，每個(gè)單元都具備完整加工任何類型產(chǎn)品的能力，因此不存在產(chǎn)品的單元間移動(dòng)。系統(tǒng)中的基本單位均為巡回式單元，分配到每個(gè)單元內(nèi)的工人數(shù)可以不同。通過(guò)決策構(gòu)建單元的數(shù)量、每個(gè)單元內(nèi)分配的工人數(shù)量以及每種場(chǎng)景下各批次與單元的分配方案，構(gòu)建最小化總加工周期的期望和方差多目標(biāo)優(yōu)化模型?？偧庸ぶ芷谄谕底钚』梢詼p小生產(chǎn)的期望交貨期，在需求波動(dòng)環(huán)境下提升企業(yè)的競(jìng)爭(zhēng)能力；最小化加工周期的方差保證了在需求變動(dòng)的環(huán)境下系統(tǒng)的穩(wěn)定性，不會(huì)因?yàn)樾枨蟮牟▌?dòng)而造成加工周期的變動(dòng)幅度過(guò)大。每種場(chǎng)景下的批次之間均采用先到先服務(wù)(FCFS, First come first service )的調(diào)度方式，按照批次順序依次分配到第一個(gè)空閑的單元當(dāng)中，如果沒(méi)有空閑的單元就分配到預(yù)計(jì)最先完成加工的單元中。由8個(gè)批次組成的生產(chǎn)任務(wù)分配到三個(gè)單元中的FCFS調(diào)度方案如圖2所示，矩形條內(nèi)的數(shù)字代表批次到達(dá)的順序，矩形條的長(zhǎng)度代表該批次的加工時(shí)間。

圖2 FCFS調(diào)度方式實(shí)例

2.2 模型建立

模型參數(shù)：

L為原有流水線上的工作站即工序的數(shù)量，每個(gè)工序由一名工人進(jìn)行操作，總工人數(shù)為W，l為工序的索引號(hào)，i為工人的索引號(hào)，i=1,2,…,W，l=1,2,…,L，W=L；

N為生產(chǎn)任務(wù)中產(chǎn)品的種類數(shù)，n為產(chǎn)品類型的索引號(hào)，n=1,2,…,N；

M為每種情境下的批次的個(gè)數(shù)，m為批次順序的索引號(hào)，m=1,2,…,M；

Vmns=1表示在情境s下的第m個(gè)批次的產(chǎn)品類型為n，否則Vmns=0；

Bms為在情境s下的第m個(gè)批次的產(chǎn)品數(shù)量；

Tnl為第n類產(chǎn)品的第l個(gè)工序的標(biāo)準(zhǔn)加工時(shí)間；

γil表示工人i對(duì)工序l的操作熟練程度；

Stn為第n類產(chǎn)品在單元內(nèi)的生產(chǎn)準(zhǔn)備時(shí)間；

SLn為第n類產(chǎn)品在流水線上的生產(chǎn)準(zhǔn)備時(shí)間；

決策變量：

J為構(gòu)建單元的數(shù)量，1≤J≤W；

Xij為工人分配方案的0-1決策變量，工人i分配到單元j中，Xij=1，否則Xij=0，i=1,2,…,W；j=1,2,…,J；

Zmjks為s情境批次與單元分配方案的0-1決策變量，在情境s下第m個(gè)批次以第k個(gè)順序被分配到單元j中則Zmjks=1，否則Zmjks=0，m=1,2,…,M，j=1,2,…,J，s=1,2,…,S，k≤M。

本文研究的流水線裝配向單元裝配的轉(zhuǎn)換問(wèn)題中，工人原有的工作為流水線上的某一道工序。對(duì)于原有L個(gè)工序和W個(gè)工人的流水線向單元裝配轉(zhuǎn)換問(wèn)題，在培養(yǎng)流水線單序工人成為全能工的過(guò)程中，由于工人學(xué)習(xí)能力和自身工作經(jīng)驗(yàn)等原因，工人i對(duì)工序l的熟練程度是不同的，以γil≥1表示。γil越接近1時(shí)工人i對(duì)工序l的操作熟練程度越高，反之γil的值越大表示工人對(duì)該工序的熟練程度越低。因此工人i完成第n類產(chǎn)品第l個(gè)工序的加工時(shí)間為Tnl*γil。在情境s下第m個(gè)批次中的單個(gè)產(chǎn)品在所分配的單元j中的操作時(shí)間TTms如式(1)所示，第m個(gè)批次全部產(chǎn)品完成加工的時(shí)間TF如式(2)所示。

(1)

(2)

對(duì)于每類產(chǎn)品在進(jìn)行生產(chǎn)之前都需要進(jìn)行生產(chǎn)環(huán)境的重設(shè)置，產(chǎn)生生產(chǎn)準(zhǔn)備時(shí)間。生產(chǎn)過(guò)程中，每個(gè)單元生產(chǎn)產(chǎn)品的前后兩批次產(chǎn)品類別不同時(shí)便會(huì)產(chǎn)生生產(chǎn)準(zhǔn)備時(shí)間，當(dāng)前后加工的兩個(gè)批次為相同產(chǎn)品類型時(shí)則準(zhǔn)備時(shí)間為0，在情境s下第m批次的生產(chǎn)準(zhǔn)備時(shí)間TSms如式(3)。第m批次的開(kāi)始加工時(shí)間TBms為上一個(gè)批次完成的時(shí)間，如果第m批次為所分配單元的第一個(gè)進(jìn)行加工的批次，則開(kāi)始時(shí)間TBms為0，具體表達(dá)如式(4)所示。在此基礎(chǔ)上，情境s下的總加工時(shí)間Make span以該單元裝配系統(tǒng)中最后一個(gè)完成生產(chǎn)任務(wù)的單元總完成時(shí)間表示，表達(dá)式如式(5)所示。

{(j,k)Zmjks=1,?j,k}

(3)

(4)

(5)

考慮需求波動(dòng)的流水線裝配向單元裝配系統(tǒng)轉(zhuǎn)化最小化Make span均值和方差的多目標(biāo)模型為：

(6)

(7)

(8)

(9)

(10)

(11)

(12)

m=2,3,…,M,?s

(13)

1≤J≤W

(14)

Xij,Zmjks∈{0,1},?i,j,k,s

(15)

目標(biāo)函數(shù)式(6)表示最小化各種可能情境下的總加工周期的期望值；目標(biāo)函數(shù)式(7)表示最小化各種可能情境下的總加工周期的方差；約束式(8)表示每名工人只能被分配到一個(gè)單元內(nèi)；約束式(9)(10)表示分配到任一單元內(nèi)的工人數(shù)不超過(guò)原有流水線上的總?cè)藬?shù)，且所有工人都分配到了單元系統(tǒng)當(dāng)中；約束式(11)表示在任一情境下的每個(gè)批次都會(huì)被分配也只能被分配到一個(gè)單元中，且不能被拆分；約束式(12)表示所有的批次都不會(huì)被分配到?jīng)]有工人的單元內(nèi)；約束式(13)表示任一情境下的各個(gè)批次都要按序進(jìn)行分配，保證FCFS的調(diào)度規(guī)則；式(14),(15)是決策變量的取值范圍約束。

3 算法設(shè)計(jì)

本文提出的流水線裝配向單元裝配轉(zhuǎn)化問(wèn)題的模型屬于多目標(biāo)優(yōu)化問(wèn)題。考慮一個(gè)簡(jiǎn)單的情景，當(dāng)s=1時(shí)，本問(wèn)題轉(zhuǎn)換為確定性任務(wù)的日本式單元構(gòu)建問(wèn)題，該問(wèn)題在Yu Yang等[18]中已經(jīng)證明為NP-hard問(wèn)題。因?yàn)楸締?wèn)題中s≥1，復(fù)雜程度更高，所以本問(wèn)題也是NP-hard問(wèn)題，不存在多項(xiàng)式時(shí)間內(nèi)求得最優(yōu)解的精確算法。對(duì)于多目標(biāo)問(wèn)題的求解，一般使用加權(quán)重的方式將多目標(biāo)問(wèn)題轉(zhuǎn)化為單目標(biāo)問(wèn)題進(jìn)行優(yōu)化求解，但權(quán)重方法本身存在求解的劣勢(shì)[22]。首先多目標(biāo)之間存在相互制約，如何確定加權(quán)系數(shù)對(duì)問(wèn)題最終的求解存在較大的影響。其次，由于多目標(biāo)的帕累托最優(yōu)集存在多個(gè)最優(yōu)解，運(yùn)用簡(jiǎn)單加權(quán)重的方式只能求得單個(gè)最優(yōu)解而無(wú)法求得全部最優(yōu)集[22]。針對(duì)這一問(wèn)題，多目標(biāo)啟發(fā)式算法成為解決多目標(biāo)優(yōu)化問(wèn)題的主要方法[23-25]，如多目標(biāo)差異演化算法(Multi-objective differential evolution，MODE)[23],帕累托獲取演化策略(Pareto archived evolution strategy，PAES)[24]，NSGA-II[25]等。在這些多目標(biāo)優(yōu)化算法中，NSGA-II算法的應(yīng)用較為廣泛并且在各類問(wèn)題中都表現(xiàn)了很好的準(zhǔn)確性和高效性[18, 25]，特別是對(duì)多目標(biāo)帕累托前沿的獲取。因此本文根據(jù)所研究問(wèn)題的特征，選擇使用基于NSGA-II的優(yōu)化算法進(jìn)行求解。

NSGA-II算法是在遺傳算法的基礎(chǔ)上引入了非支配排序和擁擠距離來(lái)評(píng)價(jià)多目標(biāo)優(yōu)化解的優(yōu)劣，在求解的收斂速度和解的多樣性保留方面均表現(xiàn)出較好的性能，是目前綜合性能較好且應(yīng)用較為廣泛的多目標(biāo)優(yōu)化算法。NSGA-II延續(xù)了GA算法在種群的交叉遺傳變異以及子代種群的產(chǎn)生方面的思路，但是在具體的個(gè)體優(yōu)劣的評(píng)價(jià)和適應(yīng)度的計(jì)算方面卻有很大的區(qū)別。本文的目標(biāo)函數(shù)有兩個(gè)，分別為：總加工周期的期望和方差。在基于NSGA-II的優(yōu)化算法中運(yùn)用非支配排序和擁擠距離評(píng)價(jià)解的適應(yīng)值，并進(jìn)行解的選擇。在兩個(gè)解的對(duì)比中，若其中一個(gè)解的兩個(gè)目標(biāo)函數(shù)值均優(yōu)于第二個(gè)解或第一個(gè)解的一個(gè)目標(biāo)值優(yōu)于第二個(gè)解而另一個(gè)目標(biāo)值相等時(shí)，稱第一個(gè)解占優(yōu)于第二個(gè)解，或稱第一個(gè)解支配第二個(gè)解。對(duì)所有的解進(jìn)行非支配排序，占優(yōu)級(jí)別越高的解具有更小的級(jí)別編碼。當(dāng)非支配級(jí)別相同時(shí)，為了保證種群中最優(yōu)解的差異性，更好的解指的是在兩個(gè)解當(dāng)中，擁擠距離較大的一個(gè)解。擁擠距離是指在解空間中，兩個(gè)解之間的歐氏距離。結(jié)合多目標(biāo)解的評(píng)價(jià)機(jī)制的同時(shí)，運(yùn)用GA來(lái)進(jìn)行每一代種群的選擇、交叉和變異等操作，最終選定最優(yōu)解的組合。結(jié)合本問(wèn)題的特征，在染色體編碼、交叉與變異算子的選擇和操作方法上都進(jìn)行了相應(yīng)的調(diào)整。

3.1 染色體編碼

本文目的為求工人組成單元系統(tǒng)的構(gòu)建方案，因此每條染色體以工人和單元的對(duì)應(yīng)關(guān)系為描述對(duì)象，采用順序編碼的方式進(jìn)行編碼。對(duì)于W個(gè)工人的流水線向單元轉(zhuǎn)換的問(wèn)題中，采用1到2W-1的數(shù)字來(lái)編碼，小于等于W的數(shù)字代表工人，大于W的數(shù)字代表分割數(shù)，以此編碼表示工人與單元的對(duì)應(yīng)關(guān)系。例如染色體“7264513”表示一個(gè)由4名工人的流水線裝配向單元裝配轉(zhuǎn)化問(wèn)題中的一個(gè)構(gòu)建方案。其中大于4的數(shù)字代表分隔符號(hào)，小于等于4的數(shù)字代表待分配工人的編號(hào)，該染色體表示系統(tǒng)共分割為3個(gè)單元，工人2分配到第一個(gè)單元，工人4分配到第二個(gè)單元，工人1和工人3分配到第三個(gè)單元。

3.2 交叉與變異

為了適應(yīng)本文的編碼方式，確保交叉運(yùn)算后染色體的可行性，本文選擇了Davis[26]提出的兩點(diǎn)順序交叉法進(jìn)行交叉運(yùn)算。例如染色體1“7264513”和染色體2“3142657”進(jìn)行交叉運(yùn)算，采用兩點(diǎn)順序交叉法得到的運(yùn)算結(jié)果為子染色體1“1 2 |6 4 5 |7 3”和子染色體2“7 5 |4 2 6| 1 3”，具體交叉運(yùn)算的步驟參考Davis[26]。運(yùn)用該交叉方式可以滿足染色體的可行性，免去對(duì)染色體調(diào)整所產(chǎn)生的運(yùn)算復(fù)雜性。

在變異運(yùn)算中，針對(duì)本問(wèn)題的特征采取隨機(jī)選擇兩點(diǎn)元素互換的方式進(jìn)行。例如染色體“3142657”進(jìn)行變異運(yùn)算，將在染色體中選擇隨機(jī)的兩點(diǎn)進(jìn)行，變異結(jié)果為“3642157”。通過(guò)兩點(diǎn)互換的變異操作可以更改原有單元構(gòu)建方案中工人的分配方式或者構(gòu)建單元的數(shù)量。該變異方式可以在保證個(gè)體可行性的同時(shí)豐富解的多樣性。

3.3 精英保留策略

每一次迭代根據(jù)規(guī)模為N的父代種群Pi生成與父代種群規(guī)模一致的子代種群Qi，將Pi和Qi合并。由于問(wèn)題特殊性，編碼規(guī)則的特征會(huì)導(dǎo)致不同染色體編碼得到同樣的解碼結(jié)果，例如“7264513”和“6 2 5 4 7 31”兩個(gè)個(gè)體的編碼不同，但解碼結(jié)果是一樣的。為了避免優(yōu)化進(jìn)入局部最優(yōu)解，首先將并集進(jìn)行重復(fù)性剔除，即剔除解碼相同的個(gè)體。在此基礎(chǔ)上，運(yùn)用錦標(biāo)賽法對(duì)全部個(gè)體進(jìn)行非支配排序，按照種群內(nèi)個(gè)體的優(yōu)劣程度選擇最優(yōu)的N個(gè)個(gè)體作為新一代的父代種群Pi+1。

3.4 算法步驟

基于Deb等[25]提出的NSGA-II算法，針對(duì)本文研究問(wèn)題的特點(diǎn)，運(yùn)用的算法步驟如下：

步驟1：隨機(jī)生成規(guī)模為N的初始種群P0；

步驟2：將種群內(nèi)的個(gè)體解碼并計(jì)算每個(gè)個(gè)體的各分目標(biāo)的目標(biāo)值和適應(yīng)值；

步驟3：對(duì)種群內(nèi)的個(gè)體進(jìn)行非支配排序和擁擠距離的計(jì)算，并按優(yōu)劣程度排列個(gè)體；

步驟4：通過(guò)交叉和變異等操作進(jìn)行GA的運(yùn)算，生成規(guī)模為N的后代種群Q0；

步驟5：將P0和Q0合并為規(guī)模為2N的種群P0∪Q0；

步驟6：對(duì)P0∪Q0進(jìn)行解碼重復(fù)個(gè)體的剔除操作；

步驟7：將種群內(nèi)的個(gè)體解碼并計(jì)算每個(gè)個(gè)體的各分目標(biāo)的目標(biāo)值和適應(yīng)值；

步驟8：對(duì)種群內(nèi)的個(gè)體進(jìn)行非支配排序和擁擠距離的計(jì)算，并按優(yōu)劣程度排列個(gè)體；

步驟9：按序選擇最優(yōu)的N個(gè)個(gè)體作為新的父代種群P1；

步驟10：重復(fù)步驟4到步驟9，直至到達(dá)最大迭代次數(shù)；

步驟11：輸出最終非支配排序解。

4 數(shù)值檢驗(yàn)分析

4.1 基本算例

上述算法用MATLAB語(yǔ)言編程實(shí)現(xiàn)，并在Intel(R) Core i5內(nèi)存8G的計(jì)算機(jī)上進(jìn)行了大量的數(shù)據(jù)檢驗(yàn)計(jì)算，取得了較好的效果。下文給出一個(gè)具體的算例來(lái)說(shuō)明模型和算法的應(yīng)用?；谇拔奶岢龅目紤]需求波動(dòng)的流水單元轉(zhuǎn)換模型，本文以Yu Yang等[18]提出的Benchmark數(shù)據(jù)為例，來(lái)驗(yàn)證本文提出的模型和算法的效果。由于Yu Yang等[18]的研究沒(méi)有考慮需求波動(dòng)的因素，本文在原問(wèn)題的基礎(chǔ)上，對(duì)參數(shù)進(jìn)行擴(kuò)充來(lái)適應(yīng)動(dòng)態(tài)需求場(chǎng)景下的單元系統(tǒng)構(gòu)建問(wèn)題。在本文中，假設(shè)有5種可能出現(xiàn)的場(chǎng)景，各種場(chǎng)景出現(xiàn)的概率和為1。在一條由6道工序組成的流水線上有6名工人完成5種不同產(chǎn)品的裝配。針對(duì)每個(gè)可能出現(xiàn)的場(chǎng)景隨機(jī)生成25個(gè)批次的生產(chǎn)任務(wù)，每個(gè)批次內(nèi)由單一種類的10件產(chǎn)品組成，產(chǎn)品種類隨機(jī)生成，具體數(shù)據(jù)如表1所示。表1中的每一列代表可能出現(xiàn)的場(chǎng)景中批次的信息(產(chǎn)品編號(hào))以及可能出現(xiàn)的概率，例如第1列表示場(chǎng)景1中第一個(gè)批次是產(chǎn)品類型5，第二個(gè)批次是產(chǎn)品類型3，以此類推。最后一行代表5個(gè)場(chǎng)景發(fā)生的概率分別為0.1，0.4，0.2，0.1，0.2。流水線裝配的一個(gè)顯著特點(diǎn)是各工序的操作時(shí)間小于等于流水線的節(jié)拍時(shí)間，假設(shè)原流水線的節(jié)拍時(shí)間為1.8分鐘，而第n類產(chǎn)品的第l個(gè)工序的操作時(shí)間Tnl在區(qū)間[1.4,1.8]上隨機(jī)產(chǎn)生，如表2所示。表中每一行代表不同產(chǎn)品類型，每一列代表產(chǎn)品加工的工序，例如表中第2行第3列表示第2類產(chǎn)品第3個(gè)工序的標(biāo)準(zhǔn)加工時(shí)間為1.6分鐘。由于先前的工作經(jīng)驗(yàn)等原因，不同的工人對(duì)每道工序的熟練程度γil不同，γil≥1表示工人i對(duì)工序l的熟練程度。γil越接近1時(shí)工人i對(duì)工序l的操作熟練程度越高，反之γil的值越大表示工人對(duì)該工序的熟練程度越低。具體數(shù)值如表3所示，例如第1行的第4列代表工人1對(duì)工序4的熟練程度為1.05，因此如果由工人i操作第n類產(chǎn)品的工序l時(shí)裝配時(shí)間為Tnl*γil。當(dāng)單元生產(chǎn)的前后兩個(gè)批次為不同種產(chǎn)品時(shí)會(huì)產(chǎn)生生產(chǎn)準(zhǔn)備時(shí)間，由于產(chǎn)品類型的不同，準(zhǔn)備時(shí)間不完全一致，具體如表4所示，每行為該類產(chǎn)品在單元內(nèi)和在流水線上的生產(chǎn)準(zhǔn)備時(shí)間。

表1 各場(chǎng)景的產(chǎn)品組合和概率

表2 產(chǎn)品在流水線上各工序的操作時(shí)間Tnl(min)

表3 工人對(duì)各工序的熟練程度γil

表4 產(chǎn)品生產(chǎn)準(zhǔn)備時(shí)間(min)

4.2 基本算例的Pareto 解

運(yùn)用本文提出的算法，種群規(guī)模為100，交叉概率為0.8，變異概率為0.2，迭代次數(shù)60次。求得由6名工人組成的流水線裝配向單元裝配系統(tǒng)的轉(zhuǎn)化，考慮需求波動(dòng)的因素所構(gòu)建的單元系統(tǒng)有7個(gè)帕累托集，如表5和圖3所示。運(yùn)用NSGA-II算法求得的結(jié)果與枚舉法求得的最優(yōu)解相一致，證明算法的有效性。表中結(jié)果均為帕累托最優(yōu)集并按照總加工周期的期望值從小到大排列，從表中計(jì)算結(jié)果可知，總加工周期的期望值較低時(shí)將同時(shí)具有較高的方差值，即期望值的更優(yōu)是以波動(dòng)性更大為代價(jià)的。決策者可以根據(jù)對(duì)總加工周期的偏好選擇適合自己的方案進(jìn)行單元系統(tǒng)的構(gòu)建。若決策者更關(guān)注期望值的降低則選擇方案一，若決策者更希望減少場(chǎng)景波動(dòng)時(shí)的變動(dòng)則選擇方案五，即方差較小的方案。

表5 由6名工人構(gòu)成的流水線向單元轉(zhuǎn)化的帕累托集

圖3 由6人流水線向單元轉(zhuǎn)化的帕累托集

當(dāng)使用流水線裝配方式進(jìn)行生產(chǎn)時(shí)，總加工時(shí)間由節(jié)拍時(shí)間決定。根據(jù)流水線裝配時(shí)間以及換產(chǎn)時(shí)間，在可能發(fā)生的五種場(chǎng)景下，流水線的總加工時(shí)間分別為687.3min；642min；709.7min；698.3min；654.5min，期望值為668.2min。對(duì)比運(yùn)用日本式單元制造的方式，總加工時(shí)間的帕累托前沿中最大的期望值只有488.9min。這也證明了運(yùn)用日本式單元裝配系統(tǒng)進(jìn)行該情境下的生產(chǎn)可以減少總加工時(shí)間、提升企業(yè)的生產(chǎn)效率。對(duì)于大規(guī)模算例采用多次運(yùn)行算法的方式求得帕累托集，本實(shí)驗(yàn)對(duì)10人，15人和20人的日本式單元構(gòu)建問(wèn)題進(jìn)行求解，由于篇幅有限不一一列舉，10名工人流水線向單元轉(zhuǎn)化構(gòu)建方案帕累托集如圖4和表6所示。

圖4 10名工人流水線向單元轉(zhuǎn)化結(jié)果的帕累托集

4.3 與任務(wù)已知型單元構(gòu)建方法的比較分析

不考慮需求的波動(dòng)，面對(duì)不同的需求場(chǎng)景時(shí)采用任務(wù)已知情境下的單元構(gòu)建方法，構(gòu)建的單元方案結(jié)果如表7所示。由結(jié)果可見(jiàn)，雖然在各場(chǎng)景下的最優(yōu)方案獲得了更短的加工時(shí)間，但是每種場(chǎng)景的最優(yōu)情況構(gòu)建方案中所構(gòu)建的單元數(shù)量以及工人的分配組合各不相同。例如在構(gòu)建生產(chǎn)系統(tǒng)時(shí)為了滿足場(chǎng)景1的最優(yōu)結(jié)果需要構(gòu)建5個(gè)單元，而其他場(chǎng)景出現(xiàn)時(shí)因?yàn)樗鑶卧臄?shù)量減少出現(xiàn)有單元空閑的情況，導(dǎo)致生產(chǎn)設(shè)備浪費(fèi)的問(wèn)題。與此同時(shí)，當(dāng)需求波動(dòng)時(shí)工人需要頻繁轉(zhuǎn)換工作所在的單元，且工作的伙伴也在變化。

為進(jìn)一步分析在生產(chǎn)實(shí)踐中各因素對(duì)構(gòu)建方案的影響，在6名工人單元構(gòu)建問(wèn)題的基本實(shí)驗(yàn)基礎(chǔ)上通過(guò)增加批次大小為5和2的實(shí)驗(yàn)，驗(yàn)證批次大小對(duì)單元構(gòu)建方案的影響。實(shí)驗(yàn)結(jié)果如圖4所示，在其他參數(shù)不變的條件下，隨著批次大小的增加總加工周期的期望和方差均呈現(xiàn)減小的趨勢(shì)，也就是說(shuō)當(dāng)批次大小增加時(shí)，單元系統(tǒng)的期望加工時(shí)間和穩(wěn)定性得到提升。企業(yè)在進(jìn)行生產(chǎn)調(diào)度的設(shè)計(jì)過(guò)程中，可以通過(guò)更改批次容量的方式提升生產(chǎn)系統(tǒng)的效率。

表7 各場(chǎng)景下的最優(yōu)構(gòu)建方案

圖5 批次大小對(duì)總加工周期的影響

5 結(jié)語(yǔ)

本文根據(jù)日本式單元制造問(wèn)題的特點(diǎn)，研究需求波動(dòng)情境下的流水線裝配向單元裝配的轉(zhuǎn)換問(wèn)題，以最小化總加工周期的期望和方差為目標(biāo)函數(shù)，構(gòu)建考慮需求波動(dòng)的單元裝配系統(tǒng)構(gòu)建問(wèn)題的多目標(biāo)模型，決策構(gòu)建的單元系統(tǒng)中單元的數(shù)量以及工人與單元對(duì)應(yīng)關(guān)系的分配方案，以期通過(guò)構(gòu)建穩(wěn)定的單元裝配系統(tǒng)應(yīng)對(duì)波動(dòng)的市場(chǎng)需求。根據(jù)問(wèn)題的特征設(shè)計(jì)了針對(duì)大規(guī)模問(wèn)題基于NSGA-II的啟發(fā)式算法，并在小規(guī)模案例中與枚舉法的結(jié)果對(duì)比驗(yàn)證了算法對(duì)模型求解的有效性。在大規(guī)模問(wèn)題的求解問(wèn)題中，采用了多次運(yùn)行算法的方法進(jìn)行求解，并得到較好的結(jié)果。通過(guò)對(duì)比任務(wù)確定型單元構(gòu)建方法在應(yīng)對(duì)需求波動(dòng)環(huán)境時(shí)存在的不足分析本研究的重要性，并分析了生產(chǎn)批次大小對(duì)系統(tǒng)性能的影響。

參考文獻(xiàn)：

[1] DTTL. 2016 Global Manufacturing Competitiveness Index[EB/OL]. [2016-8-1]. http://www2.deloitte.com/global/en/pages/manufacturing/articles/global-manufacturing-competitiveness-index.html.

[2] 徐輝, 侯建明. 需求不確定條件下的制造商訂單分配模型[J]. 中國(guó)管理科學(xué), 2016，24(3):80-88.

[3] 李稚, 譚德慶. 愛(ài)爾朗型按訂單裝配系統(tǒng)最優(yōu)生產(chǎn)——庫(kù)存控制策略研究[J]. 中國(guó)管理科學(xué), 2016,24(6):61-69.

[4] 李群霞, 馬風(fēng)才, 張群. 供應(yīng)鏈提前期供需聯(lián)合優(yōu)化庫(kù)存模型研究[J]. 中國(guó)管理科學(xué), 2015，23(4):117-122.

[5] 葉濤鋒, 達(dá)慶利, 徐宣國(guó). 需求與提前期不確定下的生產(chǎn)—銷售協(xié)調(diào)[J]. 中國(guó)管理科學(xué), 2016，24(10):133-140.

[6] 曹惺璧. 佳能細(xì)胞式生產(chǎn)方式[J]. 北大商業(yè)評(píng)論, 2010，(8):132-137.

[7] Yin Yong, Kaku I, Stecke K E. The evolution of seru production systems throughout canon[J]. Operations Management Education Review, 2008,(2):27-40.

[8] 劉晨光, 廉潔, 李文娟, 等. 日本式單元化生產(chǎn)——生產(chǎn)方式在日本的最新發(fā)展形態(tài)[J]. 管理評(píng)論, 2010,22(5):93-103.

[9] Stecke K E, Yin Yong, Kaku I, et al. Seru:The organizational extension of JIT for a super-talent factory[J]. International Journal of Strategic Decision Sciences, 2012,3(1):106-119.

[10] Villa A, Taurino T. From JIT to Seru, for a production as lean as possible[M]//AguilarMartin J J, YagueFabra J A. Procedia Engineering. AMSTERDAM: ELSEVIER SCIENCE BV, 2013:956-965.

[11] Isa K, Tsuyoshi T. Cell production and workplace innovation in Japan: toward a new model for Japanese manufacturing?[J]. Industrial Relations, 2002,41(4):548-578.

[12] Sakazume Y. Is Japanese cell manufacturing a new system?: a comparative study between Japanese cell manufacturing and cellular manufacturing[J]. Journal of Japan Industrial Management Association, 2005,55(6):341-349.

[13] Kaku I, Gong Jun, Tang Jiafu, et al. Modeling and numerical analysis of line-cell conversion problems[J]. International Journal of Production Research, 2009,47(8):2055-2078.

[14] Kaku I, Murase Y, Yin Yong. A study on human tasks related performances of converting conveyor assembly line to cellular manufacturing[J]. European Journal of Industrial Engineering, 2008,2(1):17-34.

[15] Liu Chenguang, Li Wenjuan, Lian Jie, et al. Reconfiguration of assembly systems: From conveyor assembly line to serus[J]. Journal of Manufacturing Systems, 2012,31(3):312-325.

[16] Liu Chenguang, Yang Na, Li Wenjuan, et al. Training and assignment of multi-skilled workers for implementing seru production systems[J]. The International Journal of Advanced Manufacturing Technology, 2013,69(5-8):937-959.

[17] Yu Yang, Gong Jun, Tang Jiafu, et al. How to carry out assembly line-cell conversion? A discussion based on factor analysis of system performance improvements[J]. International Journal of Production Research, 2012,50(18):5259-5280.

[18] Yu Yang, Tang Jiafu, Gong Jun, et al. Mathematical analysis and solutions for multi-objective line-cell conversion problem[J]. European Journal of Operational Research, 2014,236(2):774-786.

[19] Yu Yang, Tang Jiafu, Sun Wei, et al. Reducing worker(s) by converting assembly line into a pure cell system[J]. International Journal of Production Economics, 2013,145(2):799-806.

[20] Yu Yang, Tang Jiafu, Sun Wei, et al. Combining local search into non-dominated sorting for multi-objective line-cell conversion problem[J]. International Journal of Computer Integrated Manufacturing, 2013,4(26):316-326.

[21] 于洋, 唐加福, 宮俊. 通過(guò)生產(chǎn)線向單元轉(zhuǎn)化而減人的多目標(biāo)優(yōu)化模型[J]. 東北大學(xué)學(xué)報(bào)(自然科學(xué)版), 2013,34(1):17-20.

[22] Srinivas N, Deb K. Muiltiobjectiveoptimization using nondominated sorting in genetic algorithms[M]. Cambridge, Massachusetts: MIT Press, 1994.

[23] Ali M, Siarry P, Pant M. An efficient differential evolution based algorithm for solving multi-objective optimization problems[J]. European Journal of Operational Research, 2012,217(2):404-416.

[24] Knowles J, Corne D. The Pareto archived evolution strategy: A new baseline algorithm for pareto multiobjective optimisation[C]//Evolutionary Computation, 1999. CEC 99. Proceedings of the 1999 Congress on, Washington, DC, USA, July 6-9, 1999.

[25] Deb K, Pratap A, Agarwal S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002,6(2):182-197.

[26] Davis L. Applying adaptive algorithms to epistatic domains[C]//In Proceedings of International Joint Conference on Artificial Intelligence, Los Angeles, USA: 1985.