張 棟, 胡祥培, 黃敏芳

(1.大連理工大學(xué) 系統(tǒng)工程研究所,遼寧 大連 116024; 2.華北電力大學(xué) 經(jīng)濟(jì)與管理學(xué)院,北京 102206)

0 引言

2010年以來農(nóng)產(chǎn)品網(wǎng)上直銷模式相繼在北京、上海等地的出現(xiàn)，使蔬果類商品的流通模式由“農(nóng)超對接”躍入“農(nóng)宅對接”，為都市居民帶來極大便利。對于通過網(wǎng)上直銷銷售蔬果類商品的企業(yè)來說，加工配送是蔬果類商品網(wǎng)上直銷模式的關(guān)鍵作業(yè)環(huán)節(jié)，為了讓客戶當(dāng)天吃到當(dāng)日采摘的新鮮蔬果，企業(yè)在每天訂單截止后于蔬菜基地進(jìn)行采摘，經(jīng)包裝分揀作業(yè)后送至客戶手中。這一過程要求加工配送中心在十分短暫的時(shí)間內(nèi)處理大量個(gè)性化訂單，且每一個(gè)訂單的處理都需要經(jīng)過采摘、標(biāo)準(zhǔn)銷售單元包裝、訂單分揀多道工序，大量的個(gè)性化訂單導(dǎo)致這一過程如何組織和調(diào)度變得十分復(fù)雜。且由于蔬菜種類繁多，形態(tài)各異，企業(yè)短期內(nèi)無法實(shí)現(xiàn)全自動(dòng)機(jī)器化包裝，需要人工手動(dòng)完成標(biāo)準(zhǔn)銷售單元包裝作業(yè)。人工作業(yè)效率的不穩(wěn)定性、作業(yè)時(shí)間的隨機(jī)性也使得這一問題的復(fù)雜性增加。綜上分析，傳統(tǒng)的手工作坊式生產(chǎn)模式已不能解決蔬果類商品的加工配送問題，要引入大規(guī)模流水作業(yè)的生產(chǎn)模式，而在這一模式下，如何高效地組織蔬果標(biāo)準(zhǔn)銷售單元包裝作業(yè)，有效協(xié)調(diào)標(biāo)準(zhǔn)銷售單元包裝、訂單分揀、裝車配送三個(gè)關(guān)鍵環(huán)節(jié)的生產(chǎn)節(jié)拍，使得作業(yè)人員能夠按時(shí)無誤地完成訂單的分揀和裝車配送的工作，提高效率，降低成本，確保前后作業(yè)工序的合理銜接，是蔬果類商品網(wǎng)上直銷企業(yè)亟待解決的關(guān)鍵問題。

關(guān)于蔬果類商品包裝作業(yè)的研究，可以歸結(jié)為易腐品生產(chǎn)調(diào)度問題(perishable products scheduling)。近年來隨著易腐品生產(chǎn)企業(yè)競爭加劇，企業(yè)不斷提高自身服務(wù)質(zhì)量，易腐品生產(chǎn)調(diào)度相關(guān)研究越來越受到國內(nèi)外學(xué)者的重視，下面從模型和算法兩個(gè)方面進(jìn)行綜述：

對于易腐品生產(chǎn)調(diào)度問題模型的研究，從研究思路上主要可以分為兩類：第一種是以易腐品生產(chǎn)作業(yè)總成本或完成時(shí)間為目標(biāo)，加上時(shí)間窗等約束條件，建立生產(chǎn)調(diào)度排序模型，設(shè)計(jì)求解算法的思路；另一種思路從庫存控制的角度切入，考慮易腐品庫存方面的特殊要求，研究易腐品訂貨策略和庫存控制策略等[1,2]。鑒于本文所依托的企業(yè)采用直銷模式，企業(yè)當(dāng)日訂單截止后直接從蔬菜基地采摘，經(jīng)加工配送中心包裝分揀后直接送達(dá)客戶，不涉及多級供應(yīng)商，所以本文采用第一種思路研究，故下文主要針對第一類文獻(xiàn)進(jìn)行綜述。Claassen等[3]首先從戰(zhàn)略和操作兩個(gè)層面研究了食品等易腐品加工工業(yè)的包裝作業(yè)計(jì)劃和調(diào)度問題，并針對這一NP-hard問題提出啟發(fā)式算法求解。Sabah等[4]在此基礎(chǔ)上，將易腐品的生產(chǎn)線抽象為多階段的流水作業(yè)系統(tǒng)，研究其作業(yè)調(diào)度問題，以按時(shí)完成為約束，以最小化系統(tǒng)流時(shí)間為目標(biāo)，并考慮了多機(jī)工作負(fù)荷分配的平衡。Soman等[5,6]以一家荷蘭的食品加工企業(yè)為例，考慮食品從加工到包裝的過程，在調(diào)度生產(chǎn)的同時(shí)，針對食品工業(yè)的特殊性，加入了對庫存成本進(jìn)行控制的思想。Bilge等[7]以酸奶的生產(chǎn)加工線為例，以最小化總成本為目標(biāo)，對生產(chǎn)和配送聯(lián)合優(yōu)化，考慮了酸奶的壽命期，轉(zhuǎn)換時(shí)間和庫存容量等一系列限制條件，建立混合整數(shù)規(guī)劃模型并求解。Chen等[8]以最大化期望收益為目標(biāo)，考慮商品的易腐性，對最優(yōu)生產(chǎn)數(shù)量，生產(chǎn)時(shí)間和生產(chǎn)結(jié)束之后的配送路徑進(jìn)行決策。Nargess等[9]分析了快速消費(fèi)品的周期需求特性，考慮了任務(wù)的最早開始時(shí)間、交付時(shí)間和最遲交付時(shí)間，建立周期調(diào)度問題(cyclic scheduling problem，以下簡稱CSP)數(shù)學(xué)模型，并應(yīng)用WSPT優(yōu)先規(guī)則和啟發(fā)式算法進(jìn)行求解。以上研究豐富了易腐品調(diào)度的理論研究，并為實(shí)際應(yīng)用提供了一定的借鑒，但上述研究中的需求來自于超市對零售商，其需求波動(dòng)較小，配送點(diǎn)少且集中，與網(wǎng)上直銷模式的特點(diǎn)截然不同。在網(wǎng)上直銷模式下，客戶訂單存在較大的個(gè)性化差異，客戶配送點(diǎn)多且分散，這些特點(diǎn)導(dǎo)致已有研究結(jié)論與方法不再適用于本文考慮的包裝作業(yè)調(diào)度問題。另外，為了按時(shí)處理大量個(gè)性化訂單，加工配送作業(yè)具有多機(jī)并行作業(yè)、周期輪番作業(yè)、多車配送等特點(diǎn)。這些特點(diǎn)使得包裝作業(yè)計(jì)劃更加復(fù)雜。因此，網(wǎng)上直銷模式下蔬果商品包裝作業(yè)計(jì)劃問題有待進(jìn)一步的研究。

本文在現(xiàn)有研究的基礎(chǔ)上，首先分析蔬果類商品標(biāo)準(zhǔn)銷售單元包裝作業(yè)的特點(diǎn)，然后建立個(gè)性化差異訂單需求下的易腐品周期調(diào)度模型，以確定每個(gè)時(shí)間段、每個(gè)包裝作業(yè)工作地所包裝的蔬果種類、數(shù)量和順序；針對前述問題的復(fù)雜性，改進(jìn)現(xiàn)有啟發(fā)式算法對模型進(jìn)行求解。本研究有助于豐富易腐品生產(chǎn)調(diào)度理論，同時(shí)為解決網(wǎng)上直銷模式下蔬果類商品的包裝作業(yè)問題提供科學(xué)有效的模型和算法，具有重要的理論意義和實(shí)際意義。

1 問題描述

網(wǎng)上商城以最小銷售單元(一般為某種蔬菜的500g或1000g左右)的形式進(jìn)行銷售，客戶對最小銷售單元隨意組合并下單，蔬菜加工配送中心根據(jù)當(dāng)日客戶訂單匯總，到蔬菜基地進(jìn)行采摘，運(yùn)至加工配送中心將新鮮蔬菜包裝成為最小銷售單元，然后按單分揀，裝車配送。作業(yè)流程如圖1所示。

圖1 蔬果類商品網(wǎng)上直銷模式基本流程

由于訂單數(shù)量巨大，蔬菜種類繁多，所以本文研究引入流水作業(yè)思想，將包裝——分揀——配送作為上中下游三道工序。本問題中采用統(tǒng)一規(guī)格的車輛按照客戶訂單所屬的小區(qū)分區(qū)進(jìn)行配送，以配送車輛作為流水作業(yè)節(jié)拍，將整個(gè)包裝作業(yè)計(jì)劃期按照每一配送車輛的作業(yè)任務(wù)劃分為若干個(gè)作業(yè)周期，所以就包裝作業(yè)而言，其作業(yè)任務(wù)呈現(xiàn)周期性需求的特點(diǎn)，作業(yè)方式具有成批作業(yè)輪番生產(chǎn)的特性。

本文將每一種蔬菜在每一個(gè)作業(yè)周期內(nèi)的需求定義為一個(gè)作業(yè)任務(wù)(job)，決策具體包括分派job的作業(yè)機(jī)器與調(diào)度job之間的作業(yè)順序。由于蔬菜商品具有易腐性和快速消費(fèi)的特性，早于交貨期(due date)完成會(huì)造成較高的庫存管理成本，而晚于交貨期完成會(huì)造成下游分揀需求無法供應(yīng)，所以在建模時(shí)對每種蔬菜設(shè)置相應(yīng)的提早和延遲完成的懲罰系數(shù)，并對每個(gè)job設(shè)定最早開始時(shí)間(release date)，和最遲完成時(shí)間(deadline)，任務(wù)早于其最早開始時(shí)間進(jìn)行作業(yè)和晚于其最遲完成時(shí)間進(jìn)行作業(yè)是不允許的，為簡化計(jì)算，將庫存懲罰系數(shù)和延遲懲罰系數(shù)設(shè)置為常數(shù)，即作業(yè)成本隨著提前時(shí)間和延遲時(shí)間呈線性變化，具體時(shí)間窗約束如圖2所示。

圖2 標(biāo)準(zhǔn)銷售單元包裝作業(yè)任務(wù)時(shí)間窗

由于易腐品調(diào)度的關(guān)鍵在于有效地控制中間在制品庫存，而且蔬果包裝中人工作業(yè)容易出錯(cuò)，而周期調(diào)度方法在控制中間環(huán)節(jié)在制品庫存以及減少人工作業(yè)出錯(cuò)率等方面具有優(yōu)勢[9]，所以本文采用周期調(diào)度的思想對蔬菜標(biāo)準(zhǔn)銷售單元包裝作業(yè)問題進(jìn)行建模。但由于在直銷模式下，客戶訂單需求存在個(gè)性化差異，導(dǎo)致每個(gè)生產(chǎn)周期總體包裝作業(yè)任務(wù)量存在較大變動(dòng)，加上網(wǎng)上商城訂單規(guī)模大、客戶需求分散，需采用多機(jī)并行流水作業(yè)方式才能完成既定任務(wù)，如果采用原有建模思路，會(huì)造成包裝環(huán)節(jié)和分揀環(huán)節(jié)無法精準(zhǔn)對接，甚至可能由于某一訂單的某一品類缺少，導(dǎo)致后續(xù)訂單分揀工作無法進(jìn)行。所以如何基于周期調(diào)度思想，結(jié)合本問題的特點(diǎn)，構(gòu)建科學(xué)的模型對這一問題進(jìn)行描述，是本問題建模的難點(diǎn)。針對這一難點(diǎn)，本文根據(jù)每個(gè)作業(yè)周期的實(shí)際蔬果需求量來計(jì)算每個(gè)作業(yè)任務(wù)的時(shí)間和作業(yè)過程中帶來的各項(xiàng)成本。以有效緩解由于包裝和分揀環(huán)節(jié)需求不對稱帶來的分揀工序擁堵和可能存在的在制品庫存過大等問題。

2 模型構(gòu)建

2.1 基本假設(shè)

模型建立之前對本問題作如下界定：

(1)所有標(biāo)準(zhǔn)銷售單元包裝作業(yè)的包裝臺(tái)為一致平行機(jī)，即包裝同種數(shù)量的同種蔬果所需時(shí)間一致；

(2)作業(yè)人員包裝不同種類蔬果之間的轉(zhuǎn)換成本與任務(wù)的作業(yè)序列有關(guān)(sequence-dependent setup cost)；

(3)在每個(gè)周期內(nèi)，包裝作業(yè)一旦開始，則不允許有空閑，即機(jī)器只在每個(gè)周期的開始階段可有閑置；

(4)每個(gè)任務(wù)只允許在一臺(tái)機(jī)器上作業(yè)，且任務(wù)作業(yè)過程中不允許間斷；

(5)作業(yè)計(jì)劃期已經(jīng)根據(jù)分揀需求被劃分為明確的C個(gè)長度為T的階段(周期)；

(6)對于每一臺(tái)包裝機(jī)器而言，在整個(gè)作業(yè)計(jì)劃期內(nèi)輪番包裝固定的幾種蔬果，其作業(yè)順序相同，但作業(yè)數(shù)量會(huì)根據(jù)每個(gè)周期的需求有所不同。

2.2 參數(shù)及變量表示

決策變量:Btij/Btij′:Btij為t周期內(nèi)機(jī)器i上jobj的作業(yè)開始時(shí)間，Btij′為計(jì)算Btij的中間變量，Bti0為周期內(nèi)首個(gè)任務(wù)的開始時(shí)間;Ctij/Ctij′：Ctij為t周期內(nèi)機(jī)器i上jobj的作業(yè)完成時(shí)間，Ctij′為計(jì)算Ctij的中間變量，Ctif為周期內(nèi)最后一個(gè)任務(wù)的完成時(shí)間;Etj：t周期內(nèi)jobj的提前完成時(shí)間;Ttj：t周期內(nèi)jobj的延遲完成時(shí)間;Dtj：t周期內(nèi)jobj的需求量;Q：一個(gè)足夠大的正數(shù)。

二進(jìn)制變量：

2.3 數(shù)學(xué)模型

(1)

(1)式為目標(biāo)函數(shù)，第一項(xiàng)為提前完成的庫存成本和滯后完成的懲罰成本總和，第二項(xiàng)為各周期任務(wù)之間的轉(zhuǎn)換總成本，因需求存在較大波動(dòng)，模型對作業(yè)總成本進(jìn)行優(yōu)化，體現(xiàn)了與一般周期調(diào)度只對單周期成本進(jìn)行優(yōu)化的不同之處；(2)式表示每個(gè)任務(wù)只能在一臺(tái)機(jī)器上進(jìn)行加工；(3)式表示任何一個(gè)任務(wù)都有一個(gè)緊前任務(wù)和一個(gè)緊后任務(wù)；(4)式為周期調(diào)度假設(shè)約束，對每臺(tái)機(jī)器，在每個(gè)周期內(nèi)所包裝的蔬菜種類及順序一致；(5)表示每兩個(gè)連續(xù)作業(yè)的任務(wù)之間一定有一大于等于0的間隔時(shí)間t；(6)式為初始任務(wù)開始時(shí)間約束；(7)～(9)式表示基于本問題特殊性的任務(wù)相關(guān)時(shí)間(包括開始時(shí)間和完成時(shí)間)的計(jì)算約束；(10)式表示相鄰周期間的任務(wù)作業(yè)時(shí)間約束；(11)～(12)式表示任務(wù)的提前完成時(shí)間和延遲完成時(shí)間約束；(14)式表示任務(wù)的起始時(shí)間不早于規(guī)定的提前時(shí)間；(15)式表示任務(wù)的完工延遲時(shí)間不晚于任務(wù)的截止時(shí)間。

3 算法設(shè)計(jì)與求解

本文所研究的標(biāo)準(zhǔn)銷售單元包裝作業(yè)計(jì)劃問題屬于組合優(yōu)化領(lǐng)域中的排序問題，已有研究文獻(xiàn)[16]表明這一問題即使在包裝機(jī)器為2時(shí)仍為NP-hard問題，當(dāng)蔬果種類多，作業(yè)機(jī)器多時(shí)，解空間巨大，且本問題的多機(jī)并行作業(yè)和任務(wù)時(shí)間窗等約束條件也增加了模型求解的復(fù)雜性。上述特點(diǎn)導(dǎo)致本問題求解困難。模擬增壓-退火算法[8]具有較少受初始條件約束、操作簡單、以一定概率接受時(shí)間窗以外不可行解等主要特點(diǎn)，為有效求解這一復(fù)雜的含時(shí)間窗約束的組合優(yōu)化問題提供思路。但由于該算法具有最終得到解的質(zhì)量對初始解和鄰域解生成策略有較強(qiáng)依賴性的缺陷，為克服上述缺陷，本文對模擬增壓-退火算法進(jìn)行改進(jìn)，提出改進(jìn)的模擬增壓-退火算法對模型進(jìn)行求解，具體算法設(shè)計(jì)如圖3所示。

圖3 模擬增壓——退火算法求解流程圖

3.1 解的表示

對N種蔬菜按照種類進(jìn)行編號為1,2…N，對M臺(tái)平行機(jī)也進(jìn)行編號為1,2…M。由于每臺(tái)機(jī)器所要作業(yè)的任務(wù)數(shù)不一定一致，所以，為便于作業(yè)計(jì)劃解的表示，根據(jù)實(shí)際情況，設(shè)定每臺(tái)機(jī)器所負(fù)責(zé)任務(wù)的蔬果種類數(shù)上限為W，則此問題的解可以表示為一個(gè)M×W的矩陣，如圖4所示，其中M1,M2,M3,M4表示編號為1號到4號的機(jī)器，0表示虛擬任務(wù)。

圖4 解的結(jié)構(gòu)表示

3.2 初始解的生成

由于模擬退火算法的求解效果對初始解的鄰域解生成策略依賴較較強(qiáng)，所以需要根據(jù)問題本身的特性生成好的初始解。根據(jù)前述周期調(diào)度的假設(shè)，生成初始解時(shí)需要將N種蔬菜安排在M條包裝機(jī)器上進(jìn)行包裝作業(yè)，并使得每臺(tái)包裝機(jī)器上的總工作量盡量均衡。這實(shí)質(zhì)為一個(gè)具有M個(gè)作業(yè)者的指派問題。對于將N個(gè)任務(wù)分配在兩臺(tái)機(jī)器上的問題，從相關(guān)研究可知，該問題可轉(zhuǎn)化為0-1背包問題進(jìn)行求解，屬于NP-hard問題，所以當(dāng)包裝機(jī)器數(shù)M較大時(shí)，此任務(wù)分派問題較難得到最優(yōu)解。而任務(wù)分派并非包裝作業(yè)的最終目標(biāo)，所以本文采用如下啟發(fā)式算法生成初始解：

由前面假設(shè)，本問題每個(gè)周期中，客戶對每一種蔬菜的需求只存在小幅度的波動(dòng)，所以在生成初始種群時(shí)，為簡化計(jì)算，先假定每個(gè)周期的需求一致，以此為基準(zhǔn)來進(jìn)行包裝作業(yè)方案的初始化。算出每種蔬菜當(dāng)日的需求總量，再根據(jù)每種蔬菜單元加工時(shí)間算出其總加工時(shí)間。

Step1將N種蔬果的總加工時(shí)間按照從大到小的順序進(jìn)行排序，所得到的蔬果種類序號依次為(a1,a2,a3…an)，對應(yīng)的加工時(shí)間依次為(A1,A2,A3…An)，把(A1,A2,A3…Am)分別分至第1,2,…,M條包裝生產(chǎn)線上，并令i=1。

Step2計(jì)算第1,2,…,M條包裝生產(chǎn)線的當(dāng)前總工作時(shí)間，將AM+i分派在工作時(shí)間最小的包裝生產(chǎn)線上。

Step3令i=i+1，如果i>N-M，則得到任務(wù)分派初始解，轉(zhuǎn)Step4，否則轉(zhuǎn)Step2。

Step4得到初始解，結(jié)束。

3.3 鄰域解生成策略

策略1隨機(jī)選擇兩組機(jī)器數(shù)M1,M2，任務(wù)數(shù)N1,N2，然后將二者進(jìn)行交換，得到鄰域解。

由于策略1中隨機(jī)交換任務(wù)生成鄰域解的方法固定了每臺(tái)包裝機(jī)器上作業(yè)任務(wù)數(shù)，限制了鄰域解的搜索空間，為了擴(kuò)大鄰域解的搜索范圍，增加獲得最優(yōu)解的可能性，在此提出如下策略2，以解除任務(wù)數(shù)固定的限制。

策略2隨機(jī)選擇一組機(jī)器數(shù)和任務(wù)數(shù)(M1,N1)，和一組機(jī)器數(shù)M2和位置P，任務(wù)N1插入到M2機(jī)器上的P位置，得到鄰域解。

圖5 鄰域解生成策略

3.4 迭代過程及降溫升壓準(zhǔn)則

本問題采用“模擬升壓-退火算法”進(jìn)行求解，在迭代過程中設(shè)置溫度和壓強(qiáng)雙重參數(shù)，隨著迭代次數(shù)的增加，溫度隨之下降，壓強(qiáng)隨之上升，對于當(dāng)前最優(yōu)解根據(jù)上述鄰域解生成策略生成其鄰域解。對于鄰域解，主要考察其目標(biāo)函數(shù)值f(s)和違反時(shí)間窗的懲罰成本函數(shù)值p(s)，若兩個(gè)方面同時(shí)優(yōu)于當(dāng)前最優(yōu)值，則接受鄰域解，否則以概率exp(-(f(S′,λk)-f(Sbest,λk))/τk)接受鄰域解。并通過如下二式更新溫度和壓強(qiáng)(其中τ代表溫度，λ代表壓強(qiáng)):

τk+1=βτk

(15)

(16)

上面二式中相關(guān)參數(shù)設(shè)置可參考文獻(xiàn)[10]。

3.5 迭代終止條件

本文算法將最大迭代次數(shù)Imax設(shè)置為10000，初始溫度τ0設(shè)置為30000，終止溫度τ′設(shè)置為1，當(dāng)?shù)螖?shù)I達(dá)到Imax或迭代溫度τk低于τ′時(shí)，即終止迭代，輸出此時(shí)的解，作為調(diào)度方案的最優(yōu)解。

4 應(yīng)用實(shí)例

4.1 CSP方法和非周期調(diào)度方法結(jié)果對比

本問題以北京昊宇神鷹農(nóng)業(yè)科技有限公司為例，該公司蔬菜加工配送中心坐落于廊坊境內(nèi)的蔬菜生產(chǎn)基地，毗鄰北京城郊。初期主要服務(wù)于北京部分小區(qū)，現(xiàn)有蔬菜種類40種，日處理訂單約4000個(gè)，其中一個(gè)訂單平均重量4公斤、包含8種蔬菜(日采摘蔬菜近16000公斤，標(biāo)準(zhǔn)銷售單元32000個(gè))。公司每日下午4點(diǎn)截止當(dāng)日訂單，由于北京早晚車輛行駛高峰擁堵，車輛每日配送時(shí)間為凌晨，將貨物送至小區(qū)智能配送柜.在每日下午4點(diǎn)至次日凌晨需完成采摘、標(biāo)準(zhǔn)銷售單元包裝、訂單分揀與裝車配送等一系列工作。為提高配送效率，先對所面對的數(shù)十個(gè)小區(qū)進(jìn)行地區(qū)上的聚類，每輛配送車負(fù)責(zé)配送地區(qū)上相近的幾個(gè)小區(qū)，采用配送車載重量為4t。每日的任務(wù)分4車配送完成。每日從下午6時(shí)開始標(biāo)準(zhǔn)銷售單元包裝作業(yè)，每車任務(wù)需在兩個(gè)小時(shí)內(nèi)完成，即6時(shí)～8時(shí)作業(yè)第一車任務(wù)，依次類推。

由于篇幅限制，挑取其中N=20,M=5(N為蔬菜種類數(shù)，M為包裝機(jī)器數(shù))的例子進(jìn)行詳細(xì)分析。

表1第一行為蔬菜種類編號(如1代表白菜，2代表茄子……)，第二至五行表示A,B,C,D四個(gè)小區(qū)當(dāng)日蔬菜的訂單匯總需求總量，第六行UPT為完成一個(gè)標(biāo)準(zhǔn)銷售單元所需的時(shí)間，第七行UHC為一個(gè)標(biāo)準(zhǔn)銷售單元所消耗的單元庫存成本，第八行UDC為一個(gè)標(biāo)準(zhǔn)銷售單元所消耗的單元延誤成本。

為反應(yīng)蔬果商品的需求特點(diǎn)，將蔬果劃分為“常用”和“非常用”兩類，標(biāo)號上方有*的為常用蔬菜，否則為非常用蔬菜，常用蔬菜需求量在140～180之間生成隨機(jī)數(shù)，非常用蔬菜需求量在60～100之間生成隨機(jī)數(shù)，單元作業(yè)時(shí)間在10～20s之間。單元庫存成本為3～5，單元延遲成本為10～15，為計(jì)算方便，對庫存成本、延遲成本以及下面提到的作業(yè)轉(zhuǎn)換成本進(jìn)行無量綱數(shù)據(jù)處理，得到表1初始數(shù)據(jù)：

表1 各類蔬果需求數(shù)據(jù)

在表1中，UPT為單元作業(yè)時(shí)間(unit processing time)，UHC為單元庫存成本(unit holding cost)，UDC為單元延遲成本(unit delaying cost)。

為簡化計(jì)算過程，將蔬菜包裝作業(yè)按照包裝類別分為4類，上表中編號1～7為A類；為挑揀捆扎式包裝，8～11為B類，為裝袋式包裝；12～15為C類，為托盤保鮮膜包裝；16～20為D類，為翻筐挑揀式包裝。同一類蔬菜之間的作業(yè)轉(zhuǎn)換成本設(shè)置為10，不同類之間的轉(zhuǎn)換成本如下矩陣所示：

ABCDA5504015B5053530C4035530D1530305

本文模型和算法基于周期調(diào)度的思想(以下圖表中簡稱CSP)，而企業(yè)一般所采用的非周期調(diào)度方法(以下圖表中簡稱非CSP)在安排作業(yè)計(jì)劃時(shí)對每個(gè)作業(yè)周期單獨(dú)考慮，而通常不會(huì)考慮周期與周期之間的聯(lián)系，即在每一周期單獨(dú)制定每臺(tái)機(jī)器的作業(yè)計(jì)劃，表2是本文方法與非周期調(diào)度方法對于上述算例的求解比較。

對每一種調(diào)度方法的程序運(yùn)行50次，剔除異常解，取其中總成本最低的解進(jìn)行比較，從上述結(jié)果可以看出，周期調(diào)度方法對于每種蔬菜的需求趨于穩(wěn)定的假設(shè)下，相比于經(jīng)驗(yàn)調(diào)度，在成本上有很大的改進(jìn)，具體來說，周期調(diào)度方法得到的方案相比非周期調(diào)度方法在庫存成本方面有很大程度的節(jié)約，在延遲成本方面也有明顯改進(jìn)，作業(yè)轉(zhuǎn)換成本相近，造成延遲的任務(wù)數(shù)也有所減少。

表2 CSP調(diào)度方法與非CSP調(diào)度方法結(jié)果比較

圖6和圖7分別是本文方法和非周期調(diào)度方法所得到的方案甘特圖，同種顏色表示同一種類型的蔬果，可見，在本文方法得到的方案中，對每一個(gè)包裝作業(yè)機(jī)器來說，其工作頻率比較均衡，對于所有包裝作業(yè)工作地之間的比較，略微存在工作均衡上的差異，這可以通過每日之間的作業(yè)差異來進(jìn)行調(diào)整。而對于非周期調(diào)度方法得到的方案，包裝作業(yè)機(jī)器之間的工作量差異性比較明顯，單臺(tái)機(jī)器上的作業(yè)人員存在有時(shí)很忙，有時(shí)很閑的“閑忙不均”現(xiàn)象。從所有的包裝機(jī)器的工作量來說，總工作量參差不齊，這不但加大了成本，還嚴(yán)重影響了作業(yè)完成時(shí)間和資源利用效率，在生產(chǎn)調(diào)度過程中是不合理的。

從包裝作業(yè)出錯(cuò)率角度來說，從非周期調(diào)度方案生成的甘特圖來看，對于同一臺(tái)機(jī)器上的包裝作業(yè)人員來說，作業(yè)蔬果種類頻繁轉(zhuǎn)換會(huì)導(dǎo)致作業(yè)人員的精神疲勞，從而導(dǎo)致包裝出錯(cuò)率的提高。而CSP方法得到的方案在每臺(tái)機(jī)器上，每個(gè)作業(yè)周期固定輪番地包裝幾種蔬菜，可以增加作業(yè)人員的熟練程度，有效降低作業(yè)出錯(cuò)率。

圖6 CSP調(diào)度方案甘特圖

圖7 非CSP調(diào)度方案甘特圖

4.2 參數(shù)靈敏度分析

主要分析蔬菜種類數(shù)N，包裝機(jī)器數(shù)M和單位庫存成本與延遲成本之比α(即庫存成本在整個(gè)作業(yè)成本中所占的比重)三個(gè)參數(shù)發(fā)生變化時(shí)，CSP調(diào)度方法和非周期調(diào)度方法的適用性。

蔬菜種類N變化結(jié)果比較及分析：N=10,20,30,40(固定M=5,α=0.33)

表3 蔬菜種類總數(shù)N靈敏度分析

由此看出隨著蔬菜種類的增加，周期調(diào)度方案產(chǎn)生的庫存成本比之非周期調(diào)度有較大幅度的減少，但是減少的幅度呈下降趨勢，周期調(diào)度產(chǎn)生的延遲成本則略有上升，作業(yè)轉(zhuǎn)換成本相對比較穩(wěn)定，無明顯變化。證明周期調(diào)度比之非周期調(diào)度，在蔬菜種類較少時(shí)，效果更為明顯。

包裝作業(yè)機(jī)器數(shù)M變化結(jié)果比較及分析：m=3,5,7(固定N=20，α=0.33)

表4 機(jī)器數(shù)M靈敏度分析

隨著包裝作業(yè)機(jī)器數(shù)的增加，周期調(diào)度比之非周期調(diào)度在庫存成本和轉(zhuǎn)換成本兩個(gè)方面改善幅度有所下降，但對延遲成本的改善幅度有所上升，說明當(dāng)包裝作業(yè)機(jī)器數(shù)較少時(shí)，周期調(diào)度方法可以很好地控制作業(yè)庫存成本和作業(yè)轉(zhuǎn)換成本，而當(dāng)包裝作業(yè)機(jī)器是較多時(shí)，周期調(diào)度方法對延遲成本的控制效果更為明顯。

庫存成本與延遲成本之比(α)靈敏度分析：α=0.25,0.5,1,2(固定N=20，M=5)

表5 參數(shù)α靈敏度分析

隨著庫存成本和延遲成本比值的加大，周期調(diào)度方法相比之非周期調(diào)度方法，在庫存成本，延遲成本和轉(zhuǎn)換成本控制方面的優(yōu)勢下降比較明顯，有些結(jié)果甚至不及非周期調(diào)度方法得到的結(jié)果，當(dāng)以保持流水作業(yè)通暢進(jìn)行，不致因任務(wù)延遲完成帶來下游作業(yè)擁堵為首要目標(biāo)，即任務(wù)延遲完成所帶來的延遲成本相對于庫存成本較大時(shí)，這時(shí)的調(diào)度方案首要考慮降低任務(wù)延遲成本，其次考慮庫存成本，在此情況下，周期調(diào)度方法在降低成本方面明顯好于非周期調(diào)度方法。當(dāng)任務(wù)延遲完成所帶來的成本相對于庫存成本不大時(shí)，這時(shí)降低庫存成本成為首要控制的任務(wù)，在此情況下，周期調(diào)度方法并不適用。

綜上數(shù)值應(yīng)用實(shí)例結(jié)果，當(dāng)所采用的生產(chǎn)模式為流水作業(yè)時(shí)，首先需要考慮上下游工序的銜接，保證生產(chǎn)作業(yè)能夠順利進(jìn)行，而不至于因中間某一環(huán)節(jié)擁堵導(dǎo)致整個(gè)流水系統(tǒng)停滯，也就是說在這一模式下中間某一環(huán)節(jié)作業(yè)任務(wù)的延遲完成會(huì)對整個(gè)系統(tǒng)帶來很大的影響，此時(shí)采用周期調(diào)度方法可以有效地控制作業(yè)成本。而當(dāng)生產(chǎn)作業(yè)模式為單階段生產(chǎn)或手工作坊式生產(chǎn)而非流水作業(yè)生產(chǎn)時(shí)，控制在制品庫存成本成為首要目標(biāo)，周期調(diào)度方法得到的方案在作業(yè)總成本上的優(yōu)勢并不明顯，此時(shí)為方便起見，可以用非周期調(diào)度來指導(dǎo)生產(chǎn)。

5 結(jié)論

本文采用周期調(diào)度方法對蔬果商品網(wǎng)上直銷的標(biāo)準(zhǔn)銷售單元包裝作業(yè)問題進(jìn)行建模，通過啟發(fā)式算法求解，最后通過算例驗(yàn)證，將得到的調(diào)度方案與非周期調(diào)度方案進(jìn)行比較分析，結(jié)果表明本文模型和算法比非周期調(diào)度方法在作業(yè)成本方面有了明顯的改善。

本文模型和算法有助于在網(wǎng)上直銷環(huán)境下采用大規(guī)模流水作業(yè)解決蔬果類商品進(jìn)行標(biāo)準(zhǔn)銷售單元包裝作業(yè)的問題，用科學(xué)定量描述的方法取代了傳統(tǒng)的非周期調(diào)度方法，合理銜接了蔬果采摘和按訂單分揀的作業(yè)，并大大減少了作業(yè)過程中的成本，為企業(yè)擴(kuò)大生產(chǎn)銷售規(guī)模奠定基礎(chǔ)，具有重要的實(shí)際意義；在理論方面，文章采用周期調(diào)度的思想，針對任務(wù)人工作業(yè)時(shí)間不確定，作業(yè)時(shí)間窗嚴(yán)格的特點(diǎn)，解決了多機(jī)并行流水作業(yè)、周期輪番作業(yè)、多車配送等一系列復(fù)雜作業(yè)條件下的易腐品調(diào)度的建模問題，并改進(jìn)了現(xiàn)有啟發(fā)式算法對這一問題進(jìn)行求解，在短時(shí)間內(nèi)得到了優(yōu)化的調(diào)度方案，文章的模型和算法豐富了易腐品生產(chǎn)調(diào)度相關(guān)理論。

后續(xù)工作將圍繞包裝作業(yè)機(jī)器異質(zhì)化，包裝作業(yè)區(qū)至分揀作業(yè)區(qū)送貨車容量限制，以及考慮包裝作業(yè)區(qū)至分揀作業(yè)區(qū)供應(yīng)成本的聯(lián)合優(yōu)化等方面進(jìn)行。