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

王愛豪++孔珍珠

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

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

中圖分類號(hào)：F273；F224 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1006-4311（2018）02-0224-04

0 引言

隨著全球化市場經(jīng)濟(jì)競爭日趨激烈，客戶需求多樣化和個(gè)性化特征日趨明顯，為了適應(yīng)新的需求環(huán)境，避免市場風(fēng)險(xiǎn)，提高企業(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è)計(jì)和銷售，而將PCB組裝部分外包。根據(jù)相關(guān)資料統(tǒng)計(jì)，中國PCB組裝企業(yè)的平均利潤不超過7%[2]。

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

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

1 問題描述與建模

1.1 問題描述

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

在批量調(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é)者進(jìn)行了相關(guān)研究[13-17]。能力受限批量問題的求解過程和求解算法的時(shí)間復(fù)雜度要比無能力受限批量問題高很多。多產(chǎn)品有能力約束批量問題不僅受到生產(chǎn)能力約束，而且產(chǎn)品種類不止一種，問題復(fù)雜度很高，是強(qiáng)NP-hard問題。

1.2 問題描述

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

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

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

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

②每天加班時(shí)間可為1h、2h或3h，當(dāng)所需加班時(shí)間不足1小時(shí)時(shí)，按照1小時(shí)來算；

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

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

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

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

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

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

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

②庫存費(fèi)用主要是PCB存儲(chǔ)成本，不考慮物料搬運(yùn)、盤點(diǎn)等成本；

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

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

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

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

⑦每臺(tái)機(jī)器同一時(shí)刻只能組裝一種PCB；

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

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

式中：

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

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

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

b，b'—PCB子批次序號(hào)；

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

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

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

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

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

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

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

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

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

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

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

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

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

CO—表示加班時(shí)間段的單位時(shí)間加班費(fèi)用；

τi—表示PCBi交貨延遲的單位時(shí)間懲罰費(fèi)用；

λi—PCBi的單位時(shí)間庫存費(fèi)用；

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

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

Wi—表示PCBi的交貨延遲時(shí)間長短；

Li—表示PCBi的提前完工時(shí)間長短；

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

Ci—PCBi的實(shí)際完工時(shí)間；

Di—PCBi的交期；

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

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

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

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

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

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

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

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

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

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

3 總結(jié)

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

參考文獻(xiàn)：

[1]杜軒，李宗斌，高新勤，閆利軍.基于遺傳算法的轉(zhuǎn)塔式貼片機(jī)貼裝過程優(yōu)化[J].西安交通大學(xué)學(xué)報(bào)，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]李宗斌.先進(jìn)制造中多色集合理論的研究及應(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é)報(bào).

[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