殷君芳

（江蘇財(cái)經(jīng)職業(yè)技術(shù)學(xué)院基礎(chǔ)教學(xué)部，江蘇淮安223001）

隨著汽車保有量的大幅增長，輪胎的需求量與日俱增。越來越多的輪胎企業(yè)開始在不同地方建立分工廠來解決輪胎的生產(chǎn)和配送問題，并希望以此降低輪胎的生產(chǎn)成本和物流成本。這種分布式的工廠使得生產(chǎn)調(diào)度問題變得更加復(fù)雜，調(diào)度員需要在多個(gè)異地工廠之間統(tǒng)籌規(guī)劃，考慮全局，力求找到一個(gè)滿意的生產(chǎn)調(diào)度方案。若僅憑借人力通過經(jīng)驗(yàn)找尋，不僅耗時(shí)耗力，也很難保證得到最優(yōu)解。這正是研究分布式工廠輪胎生產(chǎn)調(diào)度系統(tǒng)的重要意義。

生產(chǎn)調(diào)度問題（Production Scheduling Problems）一直以來都是工業(yè)領(lǐng)域的熱點(diǎn)和難點(diǎn)問題，往往具有極高的復(fù)雜性而被視為NP難問題[1，2]。假設(shè)某工廠在三個(gè)不同城市建設(shè)有三個(gè)分工廠，需要處理的下個(gè)月訂單為100個(gè)，每個(gè)訂單需要選擇一個(gè)工廠進(jìn)行輪胎的生產(chǎn)以及配送。雖然問題看似規(guī)模不大，但是共有3100種不同的生產(chǎn)調(diào)度方案。無論依賴于何種大型計(jì)算機(jī)都無法通過枚舉各個(gè)調(diào)度方案在有生之年求出問題的最優(yōu)解。此前，已有研究嘗試過不少傳統(tǒng)優(yōu)化方法來解決生產(chǎn)調(diào)度問題，如整數(shù)規(guī)劃、線性規(guī)劃、牛頓法、共軛梯度法、三次插值法以及貪心法等等。但是對(duì)于生產(chǎn)調(diào)度這種NP難問題，面對(duì)如此巨大的搜索空間，傳統(tǒng)優(yōu)化方法往往無法得到滿意的調(diào)度方案，因?yàn)樗惴ㄍy以收斂到全局最優(yōu)解或是難以在可容忍的時(shí)間范圍內(nèi)搜索到較為滿意的可行解，亟需新的高效的生產(chǎn)調(diào)度模型和算法。

此外，因?yàn)楝F(xiàn)實(shí)生產(chǎn)過程中的一些限制條件，生產(chǎn)調(diào)度問題往往具備多種約束。這些復(fù)雜現(xiàn)實(shí)約束進(jìn)一步增加了生產(chǎn)調(diào)度問題的復(fù)雜性。可見，生產(chǎn)調(diào)度問題可以被視作帶約束的大規(guī)模組合優(yōu)化問題。

本文以國內(nèi)某大型輪胎生產(chǎn)廠商的實(shí)際生產(chǎn)調(diào)度需求為背景，分析了分布式工廠的輪胎生產(chǎn)調(diào)度的模型。

1 問題描述

設(shè)工廠在M個(gè)地區(qū)設(shè)立了M個(gè)分工廠，每個(gè)地區(qū)僅有一個(gè)分工廠，每個(gè)月有N個(gè)訂單等待系統(tǒng)調(diào)度。根據(jù)訂單的產(chǎn)品規(guī)格、產(chǎn)量及提貨點(diǎn)要求，尋求最優(yōu)的工廠生產(chǎn)計(jì)劃和運(yùn)輸方案，使得在滿足約束的條件下，實(shí)現(xiàn)企業(yè)的生產(chǎn)成本和運(yùn)輸成本最小化。

圖1展示了一種可能的訂單、送達(dá)地和工廠三者之間的關(guān)系。每個(gè)訂單都包含以下信息：客戶編碼、客戶名稱、送達(dá)方編碼、送達(dá)方名稱、產(chǎn)品編碼、產(chǎn)品名稱以及訂單發(fā)貨量。調(diào)度系統(tǒng)需要為每個(gè)訂單分配一個(gè)工廠，該工廠負(fù)責(zé)這個(gè)訂單的全部生產(chǎn)和配送。每個(gè)工廠里有若干種生產(chǎn)線，負(fù)責(zé)不同類別的產(chǎn)品加工。每個(gè)工廠包含以下基本信息：工廠編碼、工廠名稱、工廠所在城市?？蛻舻男畔⒂蓛刹糠纸M成：客戶編碼和客戶名稱。送達(dá)方的信息由三部分組成：送達(dá)方編碼、送達(dá)方名稱以及送達(dá)方所在城市。產(chǎn)品的信息由四部分組成：產(chǎn)品編碼、產(chǎn)品名稱、產(chǎn)品類別以及單位產(chǎn)品生產(chǎn)時(shí)間。并且每種生產(chǎn)線只負(fù)責(zé)一種產(chǎn)品，即產(chǎn)品類別數(shù)目與生產(chǎn)線種類數(shù)目相一致。

圖1 訂單、送達(dá)地和工廠的關(guān)系

舉例而言，公司目前有三個(gè)分工廠，分別位于河北石家莊、江蘇連云港和安徽馬鞍山，那么三個(gè)工廠可以表示為：

生產(chǎn)調(diào)度方案包含客戶編碼、客戶名稱、工廠編碼、工廠名稱、送達(dá)方編碼、送達(dá)方名稱、產(chǎn)品編碼、產(chǎn)品名稱以及訂單發(fā)貨量。若分別將三個(gè)訂單分配給F1、F2和F3三個(gè)工廠，那么三個(gè)訂單對(duì)應(yīng)的三條生產(chǎn)計(jì)劃可以分別記作：

訂單1的生產(chǎn)計(jì)劃：（C1，汽車廠A，F(xiàn)1，石家莊生產(chǎn)基地，D2，常州武進(jìn)區(qū)，P3，三號(hào)產(chǎn)品，50）；

訂單2的生產(chǎn)計(jì)劃：（C2，汽車廠B，F(xiàn)2，連云港生產(chǎn)基地，D4，武漢洪山區(qū)，P1，一號(hào)產(chǎn)品，20）；

訂單3的生產(chǎn)計(jì)劃：（C3，汽車廠C，F(xiàn)3，馬鞍山生產(chǎn)基地，D1，鄭州惠濟(jì)區(qū)，P4，四號(hào)產(chǎn)品，5）。

設(shè)三個(gè)工廠的單位生產(chǎn)成本和運(yùn)輸成本分別如表1和表2所示，可以計(jì)算出上述三條生產(chǎn)計(jì)劃的總生產(chǎn)成本和總運(yùn)輸成本。第一條訂單需要50噸的發(fā)貨量，在石家莊生產(chǎn)基地生產(chǎn)，需要運(yùn)輸?shù)匠Ｖ菸溥M(jìn)區(qū)，送達(dá)方所在城市是常州，所需產(chǎn)品類別是II類。根據(jù)表1可知其生產(chǎn)成本為相應(yīng)單位生產(chǎn)成本乘以訂單發(fā)貨量，即15萬元每噸乘以50噸，得750萬元；根據(jù)表2運(yùn)輸成本可得10萬元每噸乘以50噸，為500萬元。綜上，第一條訂單的總成本是750萬元加上500萬元，為1250萬元。同理可得，二號(hào)訂單生產(chǎn)成本為200萬元，運(yùn)輸成本300萬元，總成本是500萬元。三號(hào)訂單生產(chǎn)成本為150萬元，運(yùn)輸成本75萬元，總成本是225 萬元。表3總結(jié)了三條訂單的各項(xiàng)成本明細(xì)。

表1 三個(gè)工廠的單位生產(chǎn)成本

表2 三個(gè)工廠的單位運(yùn)輸成本

表3 三條訂單的各項(xiàng)成本明細(xì)

2 輪胎生產(chǎn)調(diào)度系統(tǒng)的模型設(shè)計(jì)

2.1 優(yōu)化目標(biāo)分析

記運(yùn)輸成本為Ctransport，從工廠Fi到送達(dá)方Dj的單位運(yùn)輸成本記為Cij，則相應(yīng)的總運(yùn)輸成本可以表示為式：

為了以備不時(shí)之需，各工廠都會(huì)留有庫存，庫存的存在可以降低生產(chǎn)成本，因?yàn)榭蓮膸齑嬷苯犹崛∝浳铩Ｋ圆⒉皇菃挝簧a(chǎn)成本最低的工廠就能達(dá)到最低的總生產(chǎn)成本，還需考慮庫存的影響。將Vij記為工廠F i里產(chǎn)品Pj的庫存量，Vi記為訂單Oi的庫存提貨量。當(dāng)庫存量高于訂單發(fā)貨量時(shí)，生產(chǎn)成本會(huì)減少到0，此時(shí)庫存提貨量等于訂單發(fā)貨量；當(dāng)庫存量不足訂單發(fā)貨量時(shí)，生產(chǎn)成本會(huì)減少一部分，此時(shí)庫存提貨量就等于庫存量；而當(dāng)庫存量為0時(shí)，生產(chǎn)成本不變，庫存提貨量也為0。除此以外，當(dāng)庫存提貨量不為0時(shí)，需要更新相應(yīng)的庫存量，即用當(dāng)前庫存量減去庫存提貨量，從而避免庫存被多次計(jì)算。庫存提貨量以及庫存的更新方式如式(4)和(5)，而生產(chǎn)成本將按式(6)進(jìn)行更新。

實(shí)際應(yīng)用中，單位運(yùn)輸成本并不是一旦確定發(fā)貨工廠和送達(dá)方城市后就完全固定的，而是一個(gè)隨著發(fā)貨量而變化的階梯報(bào)價(jià)，可以看成一個(gè)類似電費(fèi)的分段函數(shù)，不同范圍的發(fā)貨量對(duì)應(yīng)著不同的單位運(yùn)輸成本。我們把這個(gè)階梯報(bào)價(jià)表示為一個(gè)分段函數(shù)，記為L(x)，并假設(shè)該分段函數(shù)一共有T段。假設(shè)該分段函數(shù)的分段點(diǎn)表示為l=(l1，l2，…，lT-1)。并記此分段函數(shù)各階段的函數(shù)值分別為h=(h1，h2，..，hT)，則這些函數(shù)值可以構(gòu)成一個(gè)遞減序列，即h1＞h2＞...＞hT。該分段函數(shù)表示為式(7)，新的總運(yùn)輸成本將由式(8)來表示，其中將原有的單位運(yùn)輸成本記號(hào)C ij改為以表示從工廠所在城市Fi到送達(dá)方城市Dj以發(fā)貨量在第k段報(bào)價(jià)的單位運(yùn)輸成本。

2.2 約束條件分析

輪胎生產(chǎn)調(diào)度問題包含多個(gè)約束條件，包括：分批次發(fā)貨約束、可生產(chǎn)產(chǎn)品約束、偏好工廠約束、生產(chǎn)線能力上限約束和生產(chǎn)線工作時(shí)間上限約束。下面將依次介紹這五大約束并分析其對(duì)優(yōu)化問題的影響。

2.2.1 分批次發(fā)貨約束

部分客戶有時(shí)要求將同一訂單生產(chǎn)的產(chǎn)品分批次發(fā)貨，運(yùn)輸成本就等于每批次運(yùn)輸成本之和。

對(duì)于分批次發(fā)貨約束，令zi表示訂單Oi每批次需要的發(fā)貨量，如果ai能被zi整除，每批次的運(yùn)輸成本都將一樣；如果ai不能被zi整除，在最后一批運(yùn)輸時(shí)，運(yùn)輸成本則會(huì)有些不同。特別地，如果訂單Oi不存在分批運(yùn)輸?shù)募s束，即貨物將一次性全部運(yùn)輸?shù)剿瓦_(dá)方所在城市，那么就令zi等于ai。所以，新的運(yùn)輸成本計(jì)算公式如下：

2.2.2 可生產(chǎn)產(chǎn)品約束

雖然分布式工廠的布局里有很多工廠，但不代表每個(gè)工廠都有能力生產(chǎn)所有種類的產(chǎn)品，因此在為每個(gè)訂單分配生產(chǎn)工廠時(shí)，需要使得工廠有能力生產(chǎn)目標(biāo)產(chǎn)品，否則這種安排就毫無意義。對(duì)于可生產(chǎn)產(chǎn)品約束，定義工廠Fi的可生產(chǎn)產(chǎn)品集合為Si，則有Si=?{P1，P2，…，Pk}。這項(xiàng)約束將被表示為式：pi∈Sfi（11）

2.2.3 偏好工廠約束

在選擇工廠時(shí)，客戶會(huì)要求部分訂單只能從所約定的偏好工廠里選擇。此時(shí)該工廠必然滿足可生產(chǎn)產(chǎn)品約束。為了簡化問題，把偏好工廠直接和訂單綁定，即每個(gè)訂單存在一組偏好工廠。如果某條訂單沒有偏好工廠約束，則所有工廠都是其偏好工廠。對(duì)于偏好工廠約束，將Xi記作訂單Oi的偏好工廠集合，則Xi?{F1，F(xiàn)2，…，F(xiàn)N}。這個(gè)偏好工廠約束可以表示為式：pi∈Xi（12）

將生產(chǎn)產(chǎn)品約束和偏好工廠約束這兩項(xiàng)約束合并為可選工廠約束。將Ui記作訂單Oi的可選工廠集合，則Ui?{F1，F(xiàn)2，…，F(xiàn)N}。從而可選工廠約束可以表示為式：pi∈Ui（13），且顯然有Ui=Sfi∩Xi。

2.2.4 生產(chǎn)線能力上限約束

2.2.5 生產(chǎn)線工作時(shí)間上限約束

生產(chǎn)線工作時(shí)間上限與上一項(xiàng)約束類似，每條生產(chǎn)線每月的工作時(shí)間有上限，否則會(huì)對(duì)生產(chǎn)線造成不可逆轉(zhuǎn)損害。因?yàn)橛唵谓M每個(gè)月會(huì)更新一次，即每次進(jìn)行調(diào)度安排時(shí)，保證此次生產(chǎn)不會(huì)違反這項(xiàng)約束即可。

綜上，該生產(chǎn)調(diào)度問題的優(yōu)化目標(biāo)將由式(9)確定，并且受到式(10)(13)(14)和(15)的約束。

3 總結(jié)

生產(chǎn)調(diào)度問題一直以來都是工業(yè)領(lǐng)域中重點(diǎn)研究的問題。每得到一次改進(jìn)，相關(guān)工業(yè)的生產(chǎn)成本就會(huì)有一定的降低，生產(chǎn)效率也會(huì)有所提升。輪胎作為生活中的重要工具，其大規(guī)模分布式生產(chǎn)離不開調(diào)度與優(yōu)化。隨著輪胎的需求不斷增加，輪胎生產(chǎn)需要一個(gè)更符合實(shí)際的優(yōu)化調(diào)度模型。本文以最優(yōu)的總成本為目標(biāo)，給出了分布式工廠的輪胎調(diào)度問題的精確數(shù)學(xué)表述，得出優(yōu)化目標(biāo)的函數(shù)表達(dá)式，然后分析了多種約束的限制條件，并給出所有約束的精確表述，建立了帶約束的生產(chǎn)調(diào)度模型。

由于生產(chǎn)調(diào)度問題過于復(fù)雜，本文的調(diào)度模型雖可以滿足所有約束，但仍然存在一些不足并需改進(jìn)。文中提出的模型將一條訂單派給一個(gè)工廠去生產(chǎn)，忽略了多個(gè)工廠合作完成一條訂單的可能性。如果多個(gè)工廠同時(shí)有所需產(chǎn)品的存貨，同時(shí)分給這些工廠就能大大降低生產(chǎn)成本，從而以更大幅度減少總成本。這種情況下問題會(huì)變得更復(fù)雜，更難處理。新的調(diào)度模型將由工廠序號(hào)組成的序列轉(zhuǎn)為兩個(gè)自然數(shù)矩陣，即兩個(gè)矩陣的每一行都代表1條訂單而其中每一列分別代表在該工廠需要為該訂單生產(chǎn)的數(shù)量以及庫存的提取數(shù)量。雖然問題不再屬于組合優(yōu)化問題，但是搜索空間會(huì)更加廣闊，解的數(shù)量將急劇增加。