PCB組裝車間多目標分批調(diào)度模型

王愛豪++孔珍珠

摘要：文章建立了印制電路板（PCB）組裝車間分批優(yōu)化調(diào)度數(shù)學(xué)模型，基于企業(yè)訂單式生產(chǎn)方式（MTO）特點，構(gòu)建了以生產(chǎn)成本、庫存費用和交期延遲懲罰費用為目標的多目標分批調(diào)度模型，在模型的約束上充分考慮了《勞動法》規(guī)定的加班時長、《交易合同》中交期延遲懲罰以及PCB組裝過程的一些因素，很好地描述了PCB組裝分批調(diào)度問題，從而實現(xiàn)PCB組裝分批優(yōu)化調(diào)度問題的支持。

Abstract： PCB assembly batch scheduling mathematical model is built. The model on basis of production research in reality is built with minimizing total production cost as objective. The provision of work time in "Labor Law"， delivery delay punishment in "Business Contract" and other restricts in PCB assembly are well considered as constraints of the model. The assemble time of each process is confirmed from real production. A matrix is used to express the relations well between sub-batches， processes and machines， so PCB assembly batch scheduling problem is well described by the model.

關(guān)鍵詞：印刷電路板；多目標；分批調(diào)度

Key words： printed circuit board；make-to-order；batch scheduling

中圖分類號：F273；F224 文獻標識碼：A 文章編號：1006-4311（2018）02-0224-04

0 引言

隨著全球化市場經(jīng)濟競爭日趨激烈，客戶需求多樣化和個性化特征日趨明顯，為了適應(yīng)新的需求環(huán)境，避免市場風(fēng)險，提高企業(yè)自身的競爭力，不少電子制造企業(yè)從傳統(tǒng)的備貨式生產(chǎn)方式（Make-to-Stock，MTS）轉(zhuǎn)變?yōu)橛唵问缴a(chǎn)方式（Make-to-Order，MTO）。

在MTO生產(chǎn)模式下，許多原始設(shè)備制造商（OEM）主要專注于產(chǎn)品的設(shè)計和銷售，而將PCB組裝部分外包。根據(jù)相關(guān)資料統(tǒng)計，中國PCB組裝企業(yè)的平均利潤不超過7%[2]。

在不增加生產(chǎn)資源的條件下，對生產(chǎn)進行分批調(diào)度可以改變生產(chǎn)進程，合適的分批可以很明顯地改善生產(chǎn)設(shè)備利用率和加工周期，極大提高生產(chǎn)效率[3]。臺灣學(xué)者Low等[10]研究了生產(chǎn)車間批量調(diào)度分批調(diào)度的優(yōu)點。對等量分批和不等量分批進行了對比研究。苑麗紅等[11]在區(qū)分批量準備時間基礎(chǔ)上，研究了作業(yè)車間批量作業(yè)計劃中的批次作業(yè)計劃策略問題，但沒有指出如何確定最佳的子批數(shù)量。

為實現(xiàn)PCB組裝車間分批優(yōu)化調(diào)度，文章考慮企業(yè)實際生產(chǎn)能力和交貨延遲懲罰等因素，以生產(chǎn)成本、交貨延遲懲罰和庫存費用為目標函數(shù)，建立PCB組裝批量調(diào)度數(shù)學(xué)模型。

1 問題描述與建模

1.1 問題描述

PCB組裝批量調(diào)度問題可以描述為：在PCB組裝過程中，有N種PCB組裝任務(wù)Ni（i=1，2，3，…，N）在M臺機器Mj（j=1，2，3，…，M）上進行組裝，第i種PCB的數(shù)量為ni（i=1，2，3，…，N），每種PCB需要經(jīng)過多道工序加工，且每種PCB組裝的工序流程是確定的。需在滿足各種約束的情況下，對批量的PCB任務(wù)進行分批，劃分批次和批量大小，并確定各批次的加工機器以及在各機器上的組裝順序，使目標函數(shù)最小化。基于JST企業(yè)生產(chǎn)實際情況，文章的優(yōu)化目標是整個PCB組裝周期內(nèi)的生產(chǎn)成本、交貨延遲懲罰費用、庫存費用之和最小。

在批量調(diào)度問題的研究中，依據(jù)分批原則，將每一種工件分成若干小批量，每一小批工件稱為子批，子批的數(shù)量、大小和加工順序是決定批量調(diào)度性能最為關(guān)鍵的“三要素”[12]。目前，批量調(diào)度問題被分為三大類，即單產(chǎn)品無能力約束批量問題、單產(chǎn)品有能力約束批量問題和多產(chǎn)品有能力約束批量問題。單產(chǎn)品無能力約束問題的研究為多產(chǎn)品能力受限以及其它更加復(fù)雜批量問題研究的前提和基礎(chǔ)，該問題模型的建立比較簡單，易于求解和優(yōu)化。一些復(fù)雜的批量調(diào)度問題，例如：能力受限的單產(chǎn)品批量問題、能力受限的多產(chǎn)品、多階段批量問題，通?？梢苑纸獬苫A(chǔ)的批量問題，通過求解基礎(chǔ)批量問題得到原問題的下界，再經(jīng)過調(diào)整得到性能較好的滿意解，很多學(xué)者進行了相關(guān)研究[13-17]。能力受限批量問題的求解過程和求解算法的時間復(fù)雜度要比無能力受限批量問題高很多。多產(chǎn)品有能力約束批量問題不僅受到生產(chǎn)能力約束，而且產(chǎn)品種類不止一種，問題復(fù)雜度很高，是強NP-hard問題。

1.2 問題描述

文章基于企業(yè)生產(chǎn)調(diào)研數(shù)據(jù)，考慮企業(yè)實際生產(chǎn)能力和交貨延遲懲罰等因素，以生產(chǎn)成本、交貨延遲懲罰和庫存費用為目標函數(shù)，建立PCB組裝批量調(diào)度模型。在企業(yè)實際生產(chǎn)過程中，調(diào)度人員會依據(jù)實際情況，在生產(chǎn)能力不足時，會采用加班策略滿足生產(chǎn)需求，即在《勞動法》的相關(guān)規(guī)定下，安排員工、設(shè)備進行額外加班來完成生產(chǎn)任務(wù)?；跍蕰r生產(chǎn)（Just In Time，JIT）的思想，在恰當?shù)臅r間生產(chǎn)出恰當?shù)漠a(chǎn)品，把產(chǎn)品庫存視為一種浪費，產(chǎn)品提前完工會產(chǎn)生庫存費用。在產(chǎn)品提前完工后，企業(yè)會將完工產(chǎn)品暫時存儲在倉庫中，等到交期時間才能交貨，在存儲過程中會產(chǎn)生庫存費用。因此，以生產(chǎn)成本、交期延遲懲罰費用和庫存費用之和最小為目標，追求利潤最大化，這也正是企業(yè)最為關(guān)注的問題。endprint

企業(yè)員工、機器正常工作時間的成本是確定的，可根據(jù)企業(yè)長期的生產(chǎn)數(shù)據(jù)來進行核算，文章用CR來表示，在模型中只考慮企業(yè)所有人員和設(shè)備都正常工作時的單位時間成本，不考慮只有部分人員和設(shè)備工作的單位時間成本。

企業(yè)采用加班策略平衡生產(chǎn)計劃和生產(chǎn)能力時，按照《勞動法》的相關(guān)規(guī)定，每人每天的加班時間最多不超過3h，每月最多不得超過36h，并且加班工資不得低于正常工資的150%。在文章的模型中加班的單位時間成本為Co，文章對加班的時間約束做出如下假定：

①僅考慮每天延長工作時間的加班模式，不考慮節(jié)假日加班的情況；

②每天加班時間可為1h、2h或3h，當所需加班時間不足1小時時，按照1小時來算；

③生產(chǎn)的持續(xù)時間按天計算，不考慮非整數(shù)活動天數(shù)的情況。每人每天正常工作時間為8h，考慮加班，每人每天最多工作時間為11h；

④假設(shè)每個月的標準工作時間為22個工作日，每人在20個工作日內(nèi)的加班時間不得超過36h。

通過企業(yè)的《產(chǎn)銷合同》相關(guān)條款了解到，如不能按期交貨，需支付違約金。文章在模型中對交期延遲懲罰費用進行量化，采用τi表示某PCB任務(wù)i交貨延遲的單位時間懲罰成本。當PCB價格越高時，對應(yīng)地，如果出現(xiàn)交期延遲，則單位時間懲罰成本會越高。

PCB的存儲方式相對簡單，按照普通物料存儲方式進行保管即可。根據(jù)JST企業(yè)倉庫庫存資料，獲取PCBi的單位時間庫存費用為λi。

在PCB組裝過程中，有N種PCB組裝任務(wù)在M臺機器上進行組裝，每種PCB需要經(jīng)過多道工序加工，且每種PCB組裝的工序流程已知。在機器和資源條件一定的情況下，對批量的PCB任務(wù)進行分批，劃分批次和批量大小，并確定各批次的加工機器以及在各機器上的組裝順序，使整個生產(chǎn)周期內(nèi)的生產(chǎn)成本、交貨延遲懲罰費用、庫存費用之和最小。

在PCB組裝批量調(diào)度問題中，文章同時假設(shè)模型的建立滿足以下基本條件：

①生產(chǎn)成本主要包含員工、機器正常工作和加班工作的成本，不考慮機器的折舊和維修成本；

②庫存費用主要是PCB存儲成本，不考慮物料搬運、盤點等成本；

③假設(shè)倉庫容量無窮大，任何一種PCB在提前完工后都能存儲到倉庫；

④任何PCB的工序路線和加工時間是確定的；

⑤PCB組裝過程不考慮突發(fā)事件的發(fā)生，組裝過程不能中斷；

⑥機器的開啟、停止時間以及PCB組裝過程中的上下料時間均算入工序加工時間；

⑦每臺機器同一時刻只能組裝一種PCB；

⑧整個生產(chǎn)過程中不考慮周末或節(jié)假日加班，交期延遲時間以天為單位進行計算。

基于上述假設(shè)，建立PCB組裝車間批量調(diào)度模型。調(diào)度目標是：生產(chǎn)周期內(nèi)生產(chǎn)成本、交貨延遲懲罰費用、庫存費用之和最小，建立如下模型：

式中：

A，D，I—分別表示生產(chǎn)周期內(nèi)生產(chǎn)成本，交貨延遲懲罰費用和庫存費用；

i，j—PCB組裝任務(wù)的編號；i，j=1，2，…，n，且i≠j；

k，h—組裝設(shè)備的編號，k，h=1，2，…，M，且k≠h；

b，b'—PCB子批次序號；

Sibk，Sibh—表示PCBi的子批b在設(shè)備k和h上的組裝開始時間；

Sjb'k—表示PCBj的子批b'在設(shè)備k上的組裝開始時間；

Pibk，Pibh—表示PCBi的子批b在設(shè)備k和設(shè)備h上的組裝時間；

Eibk—表示PCBi的子批b在設(shè)備k上的組裝結(jié)束時間；

xibk—0-1變量，1表示PCBi的子批b在設(shè)備k上組裝，否則為0；

xibjb'k—0-1變量，1表示在設(shè)備k上PCBi的子批b先于PCBj的子批b'進行組裝，否則為0；

yibhk—0-1變量，1表示PCBi的子批b在設(shè)備h上的組裝先于設(shè)備k，否則為0；

Si—表示PCBi的子批數(shù)量；

R—表示t時間段內(nèi)的基本工作時間；

Z—表示t時間段內(nèi)允許的最長加班時間；

Ut—表示t時間段內(nèi)的實際工作時間；

Vt—表示t時間段內(nèi)的實際加班時間；

CR—表示基本工作時間段的單位時間生產(chǎn)費用；

CO—表示加班時間段的單位時間加班費用；

τi—表示PCBi交貨延遲的單位時間懲罰費用；

λi—PCBi的單位時間庫存費用；

Qit—表示PCBi在t時間段內(nèi)的加工時間；

Qibt—表示PCBi的子批b在t時間段內(nèi)的加工時間；

Wi—表示PCBi的交貨延遲時間長短；

Li—表示PCBi的提前完工時間長短；

T—各PCB任務(wù)組裝完成的總時間，由多個時間段t組成；

Ci—PCBi的實際完工時間；

Di—PCBi的交期；

Pi—PCBi的工序數(shù)量。

其中，公式（2）和公式（3）是正常工作時間和加班時間約束；公式（4）表示PCBi是否是延遲交貨；公式（5）表示PCBi是否是提前完工；公式（6）是PCB的組裝工藝順序約束，確保PCBi按照工序先后順序完成組裝；公式（7）是設(shè)備有效性約束，確保機器k上的PCB按照“先進先出（First In， First Out，F(xiàn)IFO）”的原則進行組裝；公式（8）確保各PCB都完成了組裝；公式（9）是組裝能力約束，確保組裝能力能滿足組裝任務(wù)需求；公式（10）表示一個PCB組裝任務(wù)至少需要在一臺機器上進行組裝。

2 目標函數(shù)關(guān)系推理

PCB組裝車間批量調(diào)度模型的目標是使得生產(chǎn)周期內(nèi)生產(chǎn)成本、交貨延遲懲罰費用、庫存費用之和最小。通過對三者之間的關(guān)系進行研究，給出了引理1和推論1，找出了目標函數(shù)中所有極小值點，并構(gòu)建出了基于目標函數(shù)的雙層調(diào)度方案。endprint

引理1：完工延遲懲罰費用D是關(guān)于加班時間Vt的非增階梯函數(shù)。完工延遲懲罰費用D與生產(chǎn)成本A（包含正常工作費用和加班費用）之和是關(guān)于加班時間Vt的階梯遞增函數(shù)。

證明：為了證明引理1，考慮某個調(diào)度方案一開始沒有使用加班時間，然后增加加班時間的情況。假設(shè)至少有一個工件完工有延遲，工件j是所有延遲完工工件中延遲時間最短的工件，γj表示工件j的完工延遲時間。加班時間從0增加到γj過程中，完工延遲懲罰費用不會有任何減少。當加班時間等于γj時，工件j恰好在交期時間內(nèi)完工，完工延遲懲罰費用會減少τj，τj表示工件j的完工延遲懲罰費用。針對完工延遲工件繼續(xù)增加加班時間，將會得到總的延遲懲罰費用與加班時間之間的函數(shù)關(guān)系，如圖1所示，其中δ（j）表示在不改變工件j完工延遲狀態(tài)情況下，可增加的最長加班時間，延遲懲罰費用是關(guān)于加班時間的非增階梯函數(shù)。

文章的生產(chǎn)成本包含正常工作費用和加班費用兩部分。表示正常工作時間段的單位時間生產(chǎn)費用，按照《勞動法》的相關(guān)規(guī)定，企業(yè)每天的正常工作時長是8h，因此每天的正常工作費用是一個固定值。單位加班時間費用為Co，是一個常數(shù)，加班費用與加班時間是線性關(guān)系，那么完工延遲懲罰費用與加班費用之和與加班時間的函數(shù)關(guān)系也是線性關(guān)系，結(jié)合圖1中完工延遲懲罰費用與加班時間的函數(shù)關(guān)系，得到如圖2所示的函數(shù)關(guān)系。延遲懲罰費用與生產(chǎn)成本之和是關(guān)于加班時間的階梯遞增函數(shù)。

另外，在調(diào)度方案確定后，采用增加加班時間，沒有改變工件的分批和加工順序，對已經(jīng)提前完工的工件不會有影響，提前完工的工件數(shù)量和時間不會因此而減少。因此，增加加班時間不會改變庫存費用，即庫存費用與加班時間是非關(guān)聯(lián)的，不構(gòu)成任何函數(shù)關(guān)系。由此得到總費用F，生產(chǎn)成本A，完工延遲懲罰費D，庫存費用I隨加班時間增加的函數(shù)關(guān)系，如圖3所示。

推論1：合理地采用加班策略可以有效減少總成本?？偝杀竞瘮?shù)F的所有極小值點對應(yīng)的加班時間VT=∑Wi，其中p為完工延遲的工件數(shù)量。

證明：基于引理1的延遲懲罰費用與生產(chǎn)成本之和關(guān)于加班時間的階梯遞增函數(shù)關(guān)系，在有工件完工延遲的調(diào)度方案中，隨著加班時間逐步增加，庫存費用不會發(fā)生改變，當加班時間等于所有延遲完工工件中延遲最短的時間，該工件完工不再延遲，不會再產(chǎn)生完工延遲懲罰費用，總成本函數(shù)圖像會出現(xiàn)“斷點”，該“斷點”所對應(yīng)的總成本是梯度函數(shù)的第一個極小值點。同理，如此重復(fù)，可以找到梯度函數(shù)的其它所有極小值點，極小值點的個數(shù)等于完工延遲的工件數(shù)量p，且極小值點所對應(yīng)的加班時間VT=∑Wi。很顯然，這些極值點中的最小值就是總成本函數(shù)的最小值。

3 總結(jié)

文章建立了PCB組裝批量調(diào)度數(shù)學(xué)模型。PCB組裝批量調(diào)度問題是典型的作業(yè)車間批量調(diào)度問題，但又具有其獨特性和復(fù)雜性。文章基于對實際生產(chǎn)企業(yè)的生產(chǎn)調(diào)研，對通用的PCB組裝批量調(diào)度模型進行了改進，以總生產(chǎn)成本最小化為目標函數(shù)，在模型的約束條件上充分考慮了《勞動法》規(guī)定的加班時長、《交易合同》中交期延遲懲罰等因素以及PCB組裝過程的一些限制條件，結(jié)合具體生產(chǎn)數(shù)據(jù)確定各工序組裝時間，并采用矩陣方式對批量劃分后的子批PCB、工序以及機器設(shè)備間的關(guān)系進行了合理表達，建立的數(shù)學(xué)模型很好地描述了PCB組裝批量調(diào)度問題?；谝?和推論1，文章以生產(chǎn)成本、交貨延遲懲罰費用和庫存費用組成的總成本F為目標函數(shù)進行求解時，可以構(gòu)建出相應(yīng)的調(diào)度方案。

參考文獻：

[1]杜軒，李宗斌，高新勤，閆利軍.基于遺傳算法的轉(zhuǎn)塔式貼片機貼裝過程優(yōu)化[J].西安交通大學(xué)學(xué)報，2008，42（3）：295-299.

[2]Ho W， Ji P. A genetic algorithm approach to optimizing component placement and retrieval sequence for chip shooter machines [J]. International Journal of Advanced Manufacturing Technology， 2006， 28（5-6）：556-560.

[3]Ammons， JC， Carlyle M， et al. Component allocation to balance workload in printed circuit card assembly systems[J]. IIE Transactions， 1997， 29（4），265-275.

[4]Lapierre SD， Debargis L， Soumis F. Balancing printed circuit board assembly line systems [J]. International Journal of Production Research.2000， 38（16）：3899-3911.

[5]Ellis KP， Bhoja， S. Optimization of the assignment of circuit cards to assembly lines in electronics assembly[J]. International Journal of Production Research， 2002，40（11）， 2609-2631.

[6]Ho W， Ji P. Optimal production planning for PCB assembly [M]. London： Springer， 2007.

[7]Wu YZ， Ji P. A scheduling problem for PCB assembly： a case with multiple lines[J]. International journal of advanced manufacturing technology， 2009，43（11-12）：1189-1201.endprint

[8]Pavlov VV. Structural simulation in CALS technology [M]. Moscow： Science Press， 2006.

[9]李宗斌.先進制造中多色集合理論的研究及應(yīng)用[M].北京：中國水利水電出版社，2005.

[10]Low Chinyao， Hsu Chih-Ming， Huang Kai-I. Benefits of lot splitting in job-shop scheduling [J]. International Journal of Advanced Manufacturing Technology， 2004， 24（9-10）：773-780.

[11]苑麗紅，崔廣才.基于遺傳算法的柔性車間批量調(diào)度研究[J].長春理工大學(xué)學(xué)報.

[12]EI-Najdawi M K. Job-splitting heuristic for lot-size scheduling in multi-stage， multi-product production processes[J]. European Journal of Operational Research， 1994，75（2）：365-377.

[13]Bao Z， Ren X， Yang Y， et al. Multi-objective integration of flexible collaborative planning and fuzzy flexible lot-splitting scheduling based on the Pareto optimal[J]. International Journal of Hybrid Information Technology， 2015，8（7）：305-318.

[14]Wang L， Chen Y， Chen T， et al. A hybrid flowshop scheduling model considering dedicated machines and lot-splitting for the solar cell industry[J]. International Journal of Systems Science， 2014，45（10）：2055-2071.

[15]Xu X， Li L， Fan L， et al. Hybrid discrete differential evolution algorithm for lot splitting with capacity constraints in flexible job scheduling[J]. Mathematical Problems in Engineering， 2013.

[16]Pimentel C， Alvelos F P E， Duarte A， et al. Exact and heuristic approaches for lot splitting and scheduling on identical parallel machines[J]. International Journal of Manufacturing Technology and Management， 2011，22（1）：39-57.

[17]Bai J， Gong Y， Wang N， et al. Multi-objective flexible Job Shop scheduling with lot-splitting[J]. Jisuanji Jicheng Zhizao Xitong/Computer Integrated Manufacturing Systems， Cims， 2010，16（2）：396-403.endprint