孫 薇，于 洋，唐加福，殷 勇，Kaku Ikou

（1.遼寧大學(xué) 商學(xué)院，遼寧 沈陽 110013；2.東北大學(xué) 系統(tǒng)工程研究所，遼寧 沈陽 110819；3.東北財(cái)經(jīng)大學(xué) 管理科學(xué)與工程學(xué)院，遼寧 大連 116025；4.日本山形大學(xué)，山形 日本 990-8560；5.日本東京城市大學(xué)，橫濱 日本 224-8551）

1 問題的提出

以流水線（如福特汽車）為代表的傳統(tǒng)生產(chǎn)模式，為大規(guī)模生產(chǎn)提供了高效的方法，但在面對(duì)當(dāng)今產(chǎn)品生命周期短、類型不固定、批次多、批量小的需求時(shí)，傳統(tǒng)的流水線生產(chǎn)因其靈活性低、投資高等特點(diǎn)而表現(xiàn)出一系列問題［1-2］。企業(yè)為了在這種多批次、小批量環(huán)境下競爭和生存，采用了許多方法，流水線向單元轉(zhuǎn)化（line-cell conversion）就是其中之一。目前，這種創(chuàng)新的生產(chǎn)方式已被廣泛應(yīng)用于日本的電子工業(yè)［1，3］。流水線向單元轉(zhuǎn)化的實(shí)質(zhì)是，將傳統(tǒng)的流水線轉(zhuǎn)化成包含多個(gè)單元的生產(chǎn)系統(tǒng)，如圖1所示。

由于單元系統(tǒng)比流水線更具柔性和靈活性，往往能獲得比流水線更高的生產(chǎn)效率。例如，索尼公司采用流水線向單元轉(zhuǎn)化后，其幸田分廠的產(chǎn)品流通時(shí)間縮減了53%，從而使其平均生產(chǎn)效率高于豐田公司。另外，通過流水線向單元轉(zhuǎn)化還能獲得其他收益，如：①佳能公司和索尼公司分別減少了72 000m2和710 000m2的工作空間［5］；②索尼公司減少了35 976個(gè)工人，大約為總勞力的25%；③佳能公司在2003年節(jié)約了550 億日元的成本［6］。

正因?yàn)檫@些優(yōu)點(diǎn)，許多學(xué)者對(duì)流水線向單元轉(zhuǎn)化的問題進(jìn)行了深入研究。Kaku等［7］最早提出了評(píng)價(jià)轉(zhuǎn)化后單元系統(tǒng)效率的方法，并分析了如何進(jìn)行流水線向單元轉(zhuǎn)化能獲得最高的效率，他最早將這個(gè)決策問題定義為流水線向單元轉(zhuǎn)化問題。隨后，Kaku等［8］采用一個(gè)多目標(biāo)模型（即同時(shí)考慮產(chǎn)品流通時(shí)間最小和總勞動(dòng)時(shí)間最?。┓治隽嗽诤畏N情況下企業(yè)更應(yīng)該將流水線轉(zhuǎn)化成單元系統(tǒng)。文獻(xiàn)［4］利用多目標(biāo)優(yōu)化算法［9］和全因子實(shí)驗(yàn)，更精確地分析了企業(yè)在何種情況下應(yīng)該采用單元生產(chǎn)方式。文獻(xiàn)［10］提出了求解多目標(biāo)模型的精確算法和啟發(fā)式算法。另外，文獻(xiàn)［11］針對(duì)減人化的流水線向單元轉(zhuǎn)化問題，分析了該模型可行解空間的復(fù)雜度，證明了該問題是NP-hard，并提出了精確算法。

多能工和工人的合理組織是佳能式單元生產(chǎn)取得高效率和柔性的關(guān)鍵。通常認(rèn)為，單元生產(chǎn)的效率比不上流水生產(chǎn)線的效率，多能工能使單元效率不低于流水生產(chǎn)線。通過在生產(chǎn)現(xiàn)場的實(shí)際觀察發(fā)現(xiàn)，當(dāng)工人稍微多加工幾個(gè)工序時(shí)，工序的平均生產(chǎn)時(shí)間不變，而當(dāng)多加工的工序超過一定限制時(shí)，工序的平均生產(chǎn)時(shí)間將變長，如式（1）所示。這就說明：當(dāng)不超過加工上限時(shí)，工人在單元中的效率不會(huì)低于流水生產(chǎn)線［4］。工人的合理組織能夠獲得更多的柔性，并且提高生產(chǎn)的平衡性：在單元中，可以根據(jù)工人工作的能力進(jìn)行合理的組織，使得相似工作能力的工人分配在一個(gè)單元中，從而使該單元的生產(chǎn)平衡性較好［4］。另外，根據(jù)生產(chǎn)批次的情況，重新進(jìn)行人員的合理組織，從而通過這種柔性化的管理提高生產(chǎn)系統(tǒng)的生產(chǎn)效率。

流水線向單元轉(zhuǎn)化的目的是增加生產(chǎn)效率（通常為產(chǎn)品的流通時(shí)間），而目前的研究都是基于Kaku提出的多目標(biāo)模型（即同時(shí)考慮產(chǎn)品流通時(shí)間最小和總勞動(dòng)時(shí)間最小），例如，文獻(xiàn)［9］針對(duì)產(chǎn)品流通時(shí)間最小和總勞動(dòng)時(shí)間最小的多目標(biāo)模型，提出了求解精確解的窮舉算法和基于非支配排序遺傳算法（Non-dominated Sorting Genetic Algorithm，NSGA-Ⅱ）的元啟發(fā)式算法。然而，Deb等［12］指出求解多目標(biāo)Pareto 解集的復(fù)雜度為O（MN2），其中：M為目標(biāo)個(gè)數(shù)，N是可行解數(shù)，獲得的結(jié)果是擁有多個(gè)Pareto解的集合。而單目標(biāo)算法卻是在N個(gè)可行解中尋找目標(biāo)最好的那個(gè)優(yōu)化解，這說明單目標(biāo)的求解復(fù)雜度遠(yuǎn)低于多目標(biāo)。多目標(biāo)向單目標(biāo)轉(zhuǎn)化的原則應(yīng)該是：去掉不重要的目標(biāo)或?qū)⑵滢D(zhuǎn)成約束條件，繼續(xù)保留相對(duì)重要的目標(biāo)。鑒于產(chǎn)品流通時(shí)間的重要性（即代表著生產(chǎn)效率），本文把相對(duì)不重要的總勞動(dòng)時(shí)間轉(zhuǎn)化為約束條件，將多目標(biāo)模型改造成最小產(chǎn)品流通時(shí)間的單目標(biāo)模型，以降低求解復(fù)雜度。

2 以提高生產(chǎn)率的流水線向單元轉(zhuǎn)換的數(shù)學(xué)模型

2.1 假設(shè)條件

本文的基本假設(shè)條件如下：

（1）有N個(gè)產(chǎn)品類型，M個(gè)產(chǎn)品批次（每個(gè)批次只有一種產(chǎn)品類型），且批次大小已知；

（2）在流水線生產(chǎn)方式中，每個(gè)工人只執(zhí)行一個(gè)工序，工人數(shù)（W）與工序數(shù)相等；

（3）在單元中，每個(gè)工人能執(zhí)行單元的所有工序［4］；

（4）不同單元中的工人數(shù)可以不同，但最少1人、最多W人；

（5）單元中的工序和流水線的工序一致；

（6）一個(gè)產(chǎn)品批次只能在一個(gè)單元中完成，不考慮拆分。

2.2 索引集

本文使用的索引如下：

i為工人的索引集（i=1，2，…，W），W為工人總數(shù)；

j為單元序號(hào)的索引集（j=1，2，…，J）；

n為產(chǎn)品型號(hào)的索引集（n=1，2，…，N）；

m為產(chǎn)品批次的索引集（m=1，2，…，M）；

k為產(chǎn)品批次在一個(gè)單元中加工順序的索引集（k=1，2，…，M）。

2.3 參數(shù)

參數(shù)如下：

Vmn為二進(jìn)制變量，Vmn=1表示批次m的產(chǎn)品類型是n，否則為0；

Bm為批次m的大?。?/p>

Tn為產(chǎn)品類型n在流水線的平衡時(shí)間；

SLn為在流水線中加工產(chǎn)品類型n的準(zhǔn)備時(shí)間；

SCPn為在單元中加工產(chǎn)品類型n的準(zhǔn)備時(shí)間；

βni為工人i加工產(chǎn)品類型n的技術(shù)系數(shù)，值越小表示能力越高；

ηi為工人i在單元中有效操作工序個(gè)數(shù)的上界，當(dāng)工人在單元中操作工序的個(gè)數(shù)超過這個(gè)上界時(shí)，其工序加工時(shí)間將變長；

εi為多能工系數(shù)；當(dāng)工人i加工的工序數(shù)超過ηi時(shí)，其工序加工時(shí)間會(huì)變長，邊長部分的系數(shù)為εi（w-ηi），如式（1）所示。

2.4 變量

變量如下：

Ci為工人i在單元中操作多個(gè)工序的能力系數(shù)，

TCm為批次m的一個(gè)產(chǎn)品在單元中一個(gè)工序的加工時(shí)間，等于單元中所有工人對(duì)批次m加工時(shí)間的平均值，

SCm為批次m在單元中的準(zhǔn)備時(shí)間，如果批次m與單元中上一批次的產(chǎn)品類型相同，則其準(zhǔn)備時(shí)間為0；否則為SCPnVmn，如式（3）所示：

FCm為批次m在單元中的流通時(shí)間，與批次大小、TCm、工序個(gè)數(shù)和單元中的工人個(gè)數(shù)相關(guān)，如式（4）所示：

FCBm為批次m在單元中的開始時(shí)間，等于該單元中前序批次流通時(shí)間和準(zhǔn)備時(shí)間的總和，如式（5）所示：

2.5 決策變量

決策變量如下：

Xij表示工人i是否已被分配到單元j。如果工人i分配到了單元j，則Xij=1；否則Xij=0。

Zmjk表示批次m是否被分配到單元j中并被第k個(gè)生產(chǎn)。如果是，則Zmjk=1；否則Zmjk=0。

2.6 單元系統(tǒng)的產(chǎn)品流通時(shí)間和總勞動(dòng)時(shí)間

單元系統(tǒng)的產(chǎn)品流通時(shí)間TTPT＿CS和總勞動(dòng)時(shí)間TLH＿CS表示如下：

其中：式（6）描述了單元系統(tǒng)的產(chǎn)品流通時(shí)間為最后一個(gè)被完成批次的完工時(shí)間；式（7）描述了單元系統(tǒng)的總勞動(dòng)時(shí)間為單元中所有工人勞動(dòng)時(shí)間的總和。

由式（1）～式（7）可知，在參數(shù)給定的情況下，單元系統(tǒng)的產(chǎn)品流通時(shí)間和總勞動(dòng)時(shí)間受決策變量Xij和Zmjk決定。

2.7 以提高生產(chǎn)率的流水線向單元轉(zhuǎn)化模型

其中：式（8）表示的模型目標(biāo)是轉(zhuǎn)化后單元系統(tǒng)的產(chǎn)品流通時(shí)間（TTPT）最小；式（9）表示勞動(dòng)時(shí)間約束，即單元系統(tǒng)的總（或平均）勞動(dòng)時(shí)間不能超過流水線TLH＿L；式（10）表示每個(gè)單元至少包含1個(gè)工人、至多包含W個(gè)工人；式（11）表示批次m只能被一個(gè)單元加工，即不考慮拆分；式（12）保證了如果批次m被加工，則加工它的單元至少有一個(gè)工人。

上述模型中，Xij決策的部分稱為單元構(gòu)造，Zmjk決策的部分稱為單元裝載。文獻(xiàn)［4］證明了單元構(gòu)造是NP-hard問題；文獻(xiàn)［5］證明了在不給定調(diào)度規(guī)則的情況下單元裝載也是NP-hard問題。因此，在不給定調(diào)度規(guī)則的情況下，流水線向單元轉(zhuǎn)化問題是一個(gè)包含了兩個(gè)NP-hard 問題的復(fù)雜問題。為了簡化，文獻(xiàn)［4，7-8，10-11］采用工業(yè)界常用的先到先服務(wù)（First Come First Service，F(xiàn)CFS）規(guī)則進(jìn)行批次到單元的裝載。但即使采用FCFS規(guī)則，流水線向單元轉(zhuǎn)化問題仍然是NP-hard問題，因?yàn)槠渲械膯卧獦?gòu)造是NP-hard問題，所以文獻(xiàn)［4］提出基于NSGA-II的多目標(biāo)優(yōu)化算法。

本文單目標(biāo)模型的復(fù)雜度雖然比多目標(biāo)低，較易求解，但仍然是NP-hard問題，因此提出了一個(gè)基于變鄰域搜索的優(yōu)化算法，以求解其大規(guī)模問題。

3 以提高生產(chǎn)率的流水線向單元轉(zhuǎn)化的變鄰域搜索

變鄰域搜索算法自1997年提出以來，成為國內(nèi)外研究的熱點(diǎn)，它具有思想簡單、容易實(shí)現(xiàn)等優(yōu)點(diǎn)，已成功應(yīng)用于許多著名的組合優(yōu)化問題［13］。針對(duì)本文的以提高生產(chǎn)率的流水線向單元轉(zhuǎn)化模型的特點(diǎn)，提出了求解其大規(guī)模實(shí)例的變鄰域搜索算法。

3.1 解的表示

在表示單元構(gòu)造方面，文獻(xiàn)［4］提出了一個(gè)有效的方法：對(duì)于一個(gè)有n個(gè)工人的流水線，用長度為2n-1的順序向量表示，其中：1-n表示對(duì)應(yīng)的工人號(hào)，（n＋1）-（2n-1）表示分隔符，另外向量首尾各有一個(gè)分隔符。鑒于該方法簡單（是順序編碼）有效（能表示出所有的單元構(gòu)造情況，而且不會(huì)產(chǎn)生不可行解），將其作為單元構(gòu)造的解表示方法。對(duì)于一個(gè)有6個(gè)工人的流水線，考慮以下兩個(gè)解：

解1：1 7 2 8 3 9 4 10 5 11 6；

解2：1 3 8 7 6 4 5 9 10 11 2。

在解1中，7，8，9，10和11表示分隔符。因此，有6個(gè)單元被構(gòu)造，也就是工人1在單元1中，工人2在單元2中，依次類推。解2表示：工人1和3在單元1中；工人6，4和5在單元2中；工人2在單元3中。為了簡單，解1 和解2 還可以分別表示成：｛｛1｝，｛2｝，｛3｝，｛4｝，｛5｝，｛6｝｝和｛｛1，3｝，｛6，4，5｝，｛2｝｝。將表示單元構(gòu)造的解代入模型的目標(biāo)函數(shù)中（式（8）），采用FCFS規(guī)則，即可求得其TTPT值。這里的FCFS規(guī)則是指［4］：到達(dá)的批次先被分配給有最小序號(hào)的空單元，如果沒有空單元存在，則批次分配給有最早完成時(shí)間的單元，因此在給定單元構(gòu)造的結(jié)果時(shí)，在采用FCFS 規(guī)則下，該解的TTPT值是一定的。例如：當(dāng)解｛｛1，3｝，｛6，4，5｝，｛2｝｝，4個(gè)批次采用FCFS規(guī)則時(shí)，其調(diào)度結(jié)果為：批次1，2和3分別分配給單元1，2和3，而批次4分配給單元1，2和3中最早完工的。更詳細(xì)的FCFS的描述和調(diào)度結(jié)果圖示，請(qǐng)參見文獻(xiàn)［4］。

變鄰域搜索算法的基本思想是，構(gòu)造一個(gè)以上的鄰域結(jié)構(gòu)，并在鄰域搜索過程中通過系統(tǒng)地改變鄰域結(jié)構(gòu)來尋找優(yōu)化解。因此，根據(jù)流水線向單元轉(zhuǎn)化的特點(diǎn)，即在FCFS 調(diào)度規(guī)則下，TTPT只與單元構(gòu)造有關(guān)（證明參見文獻(xiàn)［9］）。而單元構(gòu)造又分為單元順序和工人安排。因此，兩個(gè)鄰域結(jié)構(gòu)被提出，即針對(duì)單元順序的鄰域結(jié)構(gòu)和針對(duì)工人安排的鄰域結(jié)構(gòu)。

3.2 針對(duì)單元順序的鄰域結(jié)構(gòu)

文獻(xiàn)［9］證明了在FCFS規(guī)則下，單元排序會(huì)對(duì)產(chǎn)品流通時(shí)間產(chǎn)生影響，因此設(shè)計(jì)了一個(gè)針對(duì)單元順序的鄰域結(jié)構(gòu)。

定義1 對(duì)于一個(gè)解，其單元順序鄰域?yàn)槿我粏卧c其他單元交換產(chǎn)生的新解。

由3.1節(jié)中解的表示方法可知，無論如何交換單元，產(chǎn)生的新解一定也是可行解。

例如，針對(duì)解2，有3個(gè)單元排序的鄰域，即：

鄰域1：｛｛6，4，5｝，｛1，3｝，｛2｝｝；

鄰域2：｛｛2｝，｛6，4，5｝，｛1，3｝｝；

鄰域3：｛｛1，3｝，｛2｝，｛6，4，5｝｝。

這3個(gè)鄰域分別表示單元1 和2 交換、單元1和3交換、單元2和3交換，且它們都是可行解。

但是單元順序鄰域只改變了單元的排序，沒有改變單元中的工人。而根據(jù)式（2）可知，單元中安排的工人不同會(huì)影響到加工時(shí)間并最終影響到TTPT，由此設(shè)計(jì)了一個(gè)針對(duì)工人安排的鄰域結(jié)構(gòu)。

3.3 針對(duì)工人安排的鄰域結(jié)構(gòu)

最簡單的辦法是交換解中兩個(gè)不相同的元素。然而，根據(jù)3.1節(jié)中解的定義可知，解向量中（n-1）／2個(gè)元素是分隔符，因此如果交換的兩個(gè)元素是分隔符，則生成的鄰域解與原解一致。另外，根據(jù)式（2）可知，如果交換的兩個(gè)元素是工人并在一個(gè)單元中，則生成的鄰域也與原解一致。因此，本文使用下述方法［10］。

定義2 對(duì)于一個(gè)給定的解，其工人安排鄰域?yàn)椋涸谠摻庵校我槐硎竟と说脑嘏c不在其所在單元的任何元素進(jìn)行交換生成的新解。

例如，對(duì)于解2：工人1和3分別能與除3和1外的任意元素進(jìn)行交換；工人6，4和5分別能與除4和5，6和5，6和4外的任意元素進(jìn)行交換；工人2能與任意元素進(jìn)行交換，生成新的鄰域解。

根據(jù)3.1節(jié)中解的表示方法也可知，通過工人安排的鄰域結(jié)構(gòu)產(chǎn)生的新解一定也是可行解。

3.4 求解以提高生產(chǎn)效率的流水線向單元轉(zhuǎn)化的變鄰域搜索算法

變鄰域搜索算法的基本思想是局域搜索和改變鄰域。其中：局域搜索是指在一個(gè)鄰域結(jié)構(gòu)內(nèi)搜索局部最優(yōu)解；改變鄰域是當(dāng)局部搜索陷入局部最優(yōu)時(shí)，通過改變鄰域結(jié)構(gòu)跳出局部最優(yōu)解，尋找最優(yōu)解。

因此，基于上述單元順序和工人安排這兩個(gè)領(lǐng)域結(jié)構(gòu)，本文提出的以提高生產(chǎn)效率的流水線向單元轉(zhuǎn)化的變鄰域搜索算法流程可描述為：

輸入：W（工人數(shù)），｜S｜（初始解個(gè)數(shù)），maxIter（最大循環(huán)次數(shù)），m＿w（工人安排鄰域結(jié)構(gòu)中解Si生成的鄰域個(gè)數(shù)），maxIter＿w（工人安排鄰域結(jié)構(gòu)下解的TTPT不改變的最大次數(shù)），m＿c（單元順序鄰域結(jié)構(gòu)中解Si生成的鄰域個(gè)數(shù)），maxIter＿c（單元順序鄰域結(jié)構(gòu)下解的TTPT不改變的最大次數(shù)）。

輸出：滿足TLH約束并能減少TTPT的有效解。

步驟1 初始化。根據(jù)3.1節(jié)的內(nèi)容，隨機(jī)生成｜S｜個(gè)初始解；設(shè)置計(jì)數(shù)器counter=0。

步驟2 While（counter＜maxIter）do。

步驟3 在工人安排的鄰域結(jié)構(gòu)內(nèi)進(jìn)行局部搜索。

步驟4 在單元順序的鄰域結(jié)構(gòu)內(nèi)進(jìn)行局部搜索。

步驟5counter=counter＋1。

步驟6 輸出滿足不增加TLH并能減少TTPT的有效解。

步驟3和步驟4是基于Si分別采用工人安排鄰域結(jié)構(gòu)和單元順序鄰域結(jié)構(gòu)搜索優(yōu)化解的描述，而步驟3和步驟4的相互轉(zhuǎn)變體現(xiàn)了變鄰域思想。在步驟3和步驟4的搜索機(jī)制中，上一個(gè)局部搜索的結(jié)果作為下一個(gè)局部搜索的初始解。

在步驟（4.2.1）中，m＿r應(yīng)盡量小于單元個(gè)數(shù)，否則Si將生成單元順序的所有鄰域，這樣會(huì)導(dǎo)致單元順序領(lǐng)域結(jié)構(gòu)下的鄰域搜索的快速收斂。步驟（3.2.2）和步驟（4.2.2）保證了生成的鄰域滿足TLH約束。

基于步驟6的結(jié)果，可以探索如何進(jìn)行單元構(gòu)造以有效提高生產(chǎn)效率，如4.4節(jié)所述。

4 計(jì)算實(shí)驗(yàn)

采用C＃語言實(shí)現(xiàn)提出的變鄰域搜索算法，所有的實(shí)驗(yàn)在配備992 MB 內(nèi)存和雙核Intel 3.0 GHz的Windows XP 操作系統(tǒng)上執(zhí)行。算法的參數(shù)為：｜S｜=5，maxIter=30，m＿w=10，maxIter＿w=10，m＿c=3，maxIter＿c=5。

4.1 測(cè)試實(shí)例

實(shí)驗(yàn)用的具體參數(shù)和實(shí)例數(shù)據(jù)如表1～表5所示。表1給出了實(shí)驗(yàn)參數(shù)，其中：N（50，5）表示正態(tài)分布的均值μ=50，方差σ=5。因此，多能工系數(shù)（εi）符合N（0.2，0.05）的正態(tài)分布，其詳細(xì)數(shù)據(jù)如表2所示。表3給出了工人技術(shù)系數(shù)（βni）的分布情況，詳細(xì)數(shù)據(jù)如表4所示，表4中的值小，表明工人i加工產(chǎn)品n的能力越好，即式（2）的值越小。表5給出了產(chǎn)品批次的詳細(xì)數(shù)據(jù)。

對(duì)于有W個(gè)工人的實(shí)例，使用的數(shù)據(jù)為：表1的全部數(shù)據(jù)、表2中前W列的數(shù)據(jù)、表4中前W行的數(shù)據(jù)和表5中的全部數(shù)據(jù)。

表1 實(shí)驗(yàn)參數(shù)

表2 多能工系數(shù)（εi）的具體值

表3 工人技術(shù)系數(shù)（βni）的分布情況

表4 工人技術(shù)系數(shù)（βni）的具體值

表5 產(chǎn)品批次數(shù)據(jù)的具體值

4.2 變鄰域搜索算法與窮舉算法的性能比較

本文提出的變鄰域搜索算法與文獻(xiàn)［9］求解多目標(biāo)模型的窮舉算法的比較結(jié)果如表6所示，其中變鄰域的TTPT為計(jì)算5次的最優(yōu)解，計(jì)算時(shí)間指5次的平均時(shí)間。窮舉算法只能求解到工人數(shù)是9的實(shí)例。

從表6中可以看出，針對(duì)6～9個(gè)工人的實(shí)例，所提出的變鄰域搜索算法求得的最小TTPT與窮舉算法求得的最小TTPT一致。然而，提出的變鄰域搜索算法的計(jì)算時(shí)間卻遠(yuǎn)遠(yuǎn)好于窮舉算法，如圖2

表6 變鄰域搜索算法與窮舉算法的比較

所示。圖2中，窮舉算法的計(jì)算時(shí)間隨工人數(shù)的增加而急速增加，而提出的變鄰域搜索算法的計(jì)算時(shí)間基本保持在一個(gè)數(shù)量級(jí)。表6 中流水線的TTPT通過下式計(jì)算

式中：SLm表示批次m在生產(chǎn)線上的準(zhǔn)備時(shí)間，Zmk是決策變量，批次m在流水生產(chǎn)線的第k個(gè)生產(chǎn)時(shí)Zmk=1，否則Zmk=0，進(jìn)而

Tmi表示流水生產(chǎn)線上工人i生產(chǎn)批次m的工作時(shí)間表示流水生產(chǎn)線生產(chǎn)批次m的瓶頸時(shí)間，即最大工作時(shí)間。

4.3 大規(guī)模實(shí)例的計(jì)算結(jié)果

針對(duì)10個(gè)工人的實(shí)例，利用提出的變鄰域搜索算法求解5 次，獲得了17 個(gè)滿足TLH約束且TTPT值小于流水線的解，其中，前5 個(gè)解如表7所示。解｛｛7，10，4｝，｛6，9｝，｛5，2，1，3，8｝｝是最優(yōu)的，因?yàn)槠銽TPT最小且遠(yuǎn)小于流水線的3 680，并且TLH也遠(yuǎn)遠(yuǎn)小于流水線的36 180。

表7 工人數(shù)為10的實(shí)例中滿足TLH 約束且TTPT 得到改進(jìn)的前5個(gè)滿意解

4.4 討論

基于實(shí)驗(yàn)結(jié)果，可以得出以下結(jié)論：

（1）流水線向單元轉(zhuǎn)化有時(shí)能夠有效降低產(chǎn)品流通時(shí)間，同時(shí)工人的勞動(dòng)時(shí)間沒有增加。

從表6中可以看到，通過流水線向單元的轉(zhuǎn)化，能有效提高生產(chǎn)效率且勞動(dòng)時(shí)間不增加。如：對(duì)于工人數(shù)從6～9的所有實(shí)例，生產(chǎn)效率都有較大的改進(jìn)，其中，最大的改進(jìn)為17.6%=（3 608-2 974）／3 608×100%，即工人數(shù)為9的實(shí)例；而最小的改進(jìn)幅度也達(dá)到了13%=（3 394-2 954）／3 394×100%，即工人數(shù)為6的實(shí)例。

（2）工人數(shù)越大，TTPT改進(jìn)的空間越大。

從表6 可看出：隨著工人數(shù)從6 增加到9，TTPT改進(jìn)的改進(jìn)幅度也增大，即13%，14.6%，15.9%和17.6%。而工人數(shù)為10 時(shí)，TTPT改進(jìn)的幅度更是達(dá)到了19.0%=（3 680-2 980）／3 680×100%。這是因?yàn)楣と藬?shù)越大、流水線的平衡能力可能越差，此時(shí)采用單元系統(tǒng)安排工人，可以有效地提高平衡能力，進(jìn)而降低TTPT。

（3）在單元構(gòu)造階段，應(yīng)該將生產(chǎn)能力相似的工人安排在同一個(gè)單元中。

在表7的4個(gè)解中，工人9和10都被安排在同一個(gè)單元中，通過分析發(fā)現(xiàn)，工人9和10的技術(shù)系數(shù)相近（參見表4）。另外，工人3和5也都在4個(gè)解中被安排在一個(gè)單元，分析表4的數(shù)據(jù)也發(fā)現(xiàn)工人3和5的技術(shù)系數(shù)相近。這是因?yàn)楫?dāng)所有工人的能力都相同時(shí)，流水線的平衡達(dá)到了最佳狀態(tài)。而工人能力差距越大，流水線的平衡越不好。此時(shí)將相似能力的工人安排在一個(gè)單元中，能使單元的平衡較好。因此，通過流水線向單元轉(zhuǎn)化能有效地提高生產(chǎn)效率。

與成組技術(shù)相比，這是一個(gè)很有意思的結(jié)論，因?yàn)樵诔山M技術(shù)中，通常是將相似的機(jī)器安排在一個(gè)單元中。

（4）為了降低TTPT，在單元構(gòu)造階段應(yīng)該構(gòu)造少數(shù)幾個(gè)單元。

從表7可以看出，前5個(gè)解的單元個(gè)數(shù)都不多（理論上，最多可以有10個(gè)單元被構(gòu)造）。其中，解1和2更是達(dá)到了只有3個(gè)單元。而解3、4和5也只有5個(gè)單元。

這是因?yàn)閱卧到y(tǒng)中的TTPT值不但與工人安排有關(guān)，還與單元間的TPT平衡有關(guān)，如式（6）。式（6）表明單元系統(tǒng)的TTPT也等于最后一個(gè)加工完批次的單元的完工時(shí)間。這就說明：為了降低TTPT值，構(gòu)造的單元系統(tǒng)應(yīng)該能使批次很容易地在單元中進(jìn)行流通時(shí)間的平衡，此時(shí)單元個(gè)數(shù)往往是能被批次數(shù)整除且值小的數(shù)。例如，表7中都是3或5個(gè)單元，單元個(gè)數(shù)小，且能被30個(gè)批次整除，這樣容易在單元間進(jìn)行流通時(shí)間的平衡。

5 結(jié)束語

本文研究了在不增加勞動(dòng)時(shí)間的前提下，通過流水線向單元轉(zhuǎn)化來提高生產(chǎn)效率，即降低產(chǎn)品流通時(shí)間的問題。本文的貢獻(xiàn)如下：①建立了將勞動(dòng)時(shí)間作為約束條件而只考慮最小化產(chǎn)品流通時(shí)間的單目標(biāo)模型，以降低流水線向單元轉(zhuǎn)化的多目標(biāo)模型復(fù)雜度；②針對(duì)該流水線向單元轉(zhuǎn)化單目標(biāo)模型的特點(diǎn)，提出了基于變鄰域搜索的算法，以求解大規(guī)模實(shí)例；③基于大量的實(shí)例計(jì)算，證明了流水線向單元轉(zhuǎn)化可以在不增加勞動(dòng)時(shí)間的前提下有效地提高生產(chǎn)效率，并給出了如何進(jìn)行單元構(gòu)造以提高生產(chǎn)效率的建議。仍有很多關(guān)于流水線向單元轉(zhuǎn)化的問題急需研究，如：考慮非全能工情形的流水線向單元轉(zhuǎn)化，產(chǎn)品有不同工序集的流水線向單元轉(zhuǎn)化，以及分割式單元的單元系統(tǒng)構(gòu)造和調(diào)度方法研究等。

［1］LIU Chenguang，STECKE E K，LIAN Jie，et al.Reconfiguration of assembly systems：from conveyor assembly line to serus［J］.Journal of Manufacturing Systems，2012，31（3）：312-325.

［2］YU Yang，TANG Jiafu，GONG Jun.Multi-objective optimization model of line-cell conversion towards reducing workers［J］.Journal of Northeastern University：Natural Science，2013，34（1）：17-20（in Chinese）.［于 洋，唐加福，宮 俊.通過生產(chǎn)線向單元轉(zhuǎn)化而減人的多目標(biāo)優(yōu)化模型［J］.東北大學(xué)學(xué)報(bào)：自然科學(xué)，2013，34（1）：17-20.］

［3］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.

［4］YU Yang，GONG Jun，TANG Jiafu，et al.How to do 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.

［5］STECKE K E，YIN Y，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）：105-118.

［6］YIN Y，STECKE K E，KAKU I.The evolution of seru production systems throughout Canon［J］.Operations Management Education Review，2008，2：27-40.

［7］KAKU I，GONG Jun，TANG Jiafu，et al.A mathematical model for converting conveyor assembly line to cellular manufacturing［J］.International Journal of Industrial Engineering and Management Science，2008，7（2）：160-170.

［8］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.

［9］YU Yang，TANG Jiafu，SUN Wei，et al.Mathematical analysis and solutions for multi-objective line-cell conversion problem［J］.European Journal of Operational Research，2014，236（2）：774-786.

［10］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，26（4）：316-326.

［11］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.

［12］DEB K，PRATAP A，AGARWAL S，et al.A fast and elitist multi-objective genetic algorithm：NSGA-II［J］.IEEE Transactions on Evolutionary Computation，2002，6（2）：182-197.

［13］DONG Jianping，SU Chun，LI Jun.Discrete particle swarm optimization algorithms for assembly line balancing problems of type I［J］.Computer Integrated Manufacturing Systems，2012，18（5）：1021-1030（in Chinese）.［竇建平，蘇 春，李俊.求解第Ⅰ類裝配線平衡問題的離散粒子群優(yōu)化算法［J］.計(jì)算機(jī)集成制造系統(tǒng)，2012，18（5）：1021-1030.］