考慮產(chǎn)品變質(zhì)的生產(chǎn)與分車聯(lián)合優(yōu)化調(diào)度問題研究

馬 英, 馬晶晶, 李 凱

(1.合肥工業(yè)大學(xué) 管理學(xué)院,安徽 合肥 230009; 2.合肥工業(yè)大學(xué) 過程優(yōu)化與智能決策教育部重點(diǎn)實(shí)驗(yàn)室,安徽 合肥 230009)

考慮產(chǎn)品變質(zhì)的生產(chǎn)與分車聯(lián)合優(yōu)化調(diào)度問題研究

馬 英1,2, 馬晶晶1, 李 凱1,2

(1.合肥工業(yè)大學(xué) 管理學(xué)院,安徽 合肥 230009; 2.合肥工業(yè)大學(xué) 過程優(yōu)化與智能決策教育部重點(diǎn)實(shí)驗(yàn)室,安徽 合肥 230009)

文章研究了冷鏈環(huán)境中單機(jī)生產(chǎn)模式下多訂單的生產(chǎn)與分車問題,即生產(chǎn)商為客戶生產(chǎn)多個(gè)訂單并分配車輛為客戶配送。由于產(chǎn)品為易變質(zhì)產(chǎn)品,隨著時(shí)間的推移會(huì)產(chǎn)生變質(zhì)成本,且配送存在車輛使用成本,因此需要合理安排生產(chǎn)計(jì)劃及分車方案,以便使得車輛成本與產(chǎn)品變質(zhì)成本之和最小化。文章首先進(jìn)行問題分析,提出幾條最優(yōu)解的性質(zhì),在此基礎(chǔ)上構(gòu)造2個(gè)算法,進(jìn)而提出問題的一個(gè)下界,并通過大規(guī)模實(shí)驗(yàn)驗(yàn)證算法的有效性。

生產(chǎn);分車;聯(lián)合調(diào)度;易變質(zhì)產(chǎn)品;單機(jī)

0 引 言

關(guān)于冷鏈型企業(yè)所生產(chǎn)的易變質(zhì)產(chǎn)品的研究大多聚焦庫存控制、經(jīng)濟(jì)批量等問題,如文獻(xiàn)[1]研究了基于產(chǎn)品變質(zhì)和零售商部分延期支付的經(jīng)濟(jì)訂貨批量(economic order quantity,EOQ)模型,但是涉及生產(chǎn)調(diào)度和供應(yīng)鏈調(diào)度方面的研究文獻(xiàn)相對(duì)較少。隨著供應(yīng)鏈管理理論的發(fā)展,人們逐漸認(rèn)識(shí)到供應(yīng)鏈中各個(gè)環(huán)節(jié)的有效配合才能發(fā)揮最大功用,特別是對(duì)于冷鏈型企業(yè),其時(shí)效性要求冷鏈各環(huán)節(jié)具有更高的組織協(xié)調(diào)性,因此冷鏈型企業(yè)資源調(diào)度問題逐漸成為供應(yīng)鏈管理和生產(chǎn)調(diào)度領(lǐng)域的一個(gè)熱點(diǎn)和前沿問題。

文獻(xiàn)[2]最早提出了分車配送問題,研究了單機(jī)生產(chǎn)模式下使總加權(quán)提前懲罰與配送成本最小化問題;文獻(xiàn)[3]論證了此問題可轉(zhuǎn)化為經(jīng)典平行機(jī)調(diào)度問題,并且可將解決平行機(jī)調(diào)度問題的方法直接應(yīng)用于解決該問題。之后,許多學(xué)者在文獻(xiàn)[2]研究的基礎(chǔ)上進(jìn)行了拓展,文獻(xiàn)[4]考慮了配送成本是每車訂單數(shù)量的線性增函數(shù),且車輛數(shù)是有限制的；文獻(xiàn)[5]考慮了一種更復(fù)雜的情況,目標(biāo)函數(shù)由提前與延遲懲罰、庫存和配送成本構(gòu)成；文獻(xiàn)[6]在多周期隨機(jī)需求下研究了供應(yīng)鏈庫存與配送的聯(lián)合優(yōu)化模型；文獻(xiàn)[7]研究了訂單帶交貨期時(shí)間窗的情況,使包括提前、延遲、庫存和配送成本在內(nèi)的總成本最小化。目前,分車配送研究的共同點(diǎn)如下：① 車輛配送的起始時(shí)間等于該車最后一個(gè)加工訂單的完工時(shí)間; ② 配送成本是使用車輛數(shù)的非減函數(shù); ③ 車輛是沒有容量限制的。然而以上文獻(xiàn)均未涉及冷鏈型企業(yè)易變質(zhì)產(chǎn)品問題的研究。

目前,學(xué)術(shù)界對(duì)于易變質(zhì)產(chǎn)品生產(chǎn)與分車配送的研究并不多。文獻(xiàn)[8]研究了具有保質(zhì)期的單一產(chǎn)品由單一車輛配送問題，并且假設(shè)生產(chǎn)序列與配送序列是固定且相同的;文獻(xiàn)[9]在文獻(xiàn)[8]固定交付順序問題的基礎(chǔ)上做了進(jìn)一步研究,對(duì)其提出的分支定界算法做了修正,解決了在產(chǎn)量和配送條件有限的情形下最大限度地滿足客戶需求問題;文獻(xiàn)[10]研究了批量生產(chǎn)易變質(zhì)產(chǎn)品的問題,并且在產(chǎn)品變質(zhì)的前提下證明了批量有利于降低生產(chǎn)設(shè)置成本及配送成本,從而達(dá)到降低總成本的目的。文獻(xiàn)[8-10]并沒有考慮到產(chǎn)品持續(xù)性變質(zhì)的情況,考慮的產(chǎn)品變質(zhì)特性均體現(xiàn)在產(chǎn)品的保質(zhì)期上,即某一產(chǎn)品一旦生產(chǎn)完成后經(jīng)過一段固定的時(shí)間,產(chǎn)品就會(huì)變質(zhì)不可用,在到達(dá)保質(zhì)期之前,產(chǎn)品性狀是不發(fā)生變化的,但是在現(xiàn)實(shí)中許多產(chǎn)品是持續(xù)性變質(zhì)的,而保質(zhì)期無法體現(xiàn)這一特性。針對(duì)這一問題,文獻(xiàn)[11]考慮了產(chǎn)品變質(zhì)率為常數(shù)的情況下,每個(gè)時(shí)段內(nèi)產(chǎn)品的需求量是已知的,決定每個(gè)時(shí)段產(chǎn)品的生產(chǎn)量及生產(chǎn)順序,滿足需求并且使總成本最小化;文獻(xiàn)[12]研究了單一生產(chǎn)線生產(chǎn)變質(zhì)率為常數(shù)的易變質(zhì)產(chǎn)品并配送給多個(gè)零售商的問題,企業(yè)需要確定每種產(chǎn)品的生產(chǎn)數(shù)量、開始生產(chǎn)時(shí)間以及產(chǎn)品的配送路線,其優(yōu)化的目標(biāo)是使企業(yè)期望總收益最大化;文獻(xiàn)[13]研究問題的假設(shè)條件與文獻(xiàn)[12]相同,也考慮了變質(zhì)成本,只是其優(yōu)化的目標(biāo)是使期望總成本最小化;文獻(xiàn)[14]把研究推廣到了更復(fù)雜的生產(chǎn)環(huán)境,假設(shè)企業(yè)內(nèi)有多條生產(chǎn)線,客戶訂單要求每種產(chǎn)品數(shù)量是固定的,并且產(chǎn)品之間存在與順序相關(guān)的調(diào)整時(shí)間和調(diào)整成本,但是沒有考慮到車輛使用的固定成本以及車輛的容量限制,事實(shí)上在現(xiàn)實(shí)中使用車輛時(shí)通常會(huì)有一定的啟動(dòng)成本,車容量也是有限制的,即只能容納一定體積的產(chǎn)品。

本文研究了冷鏈環(huán)境下單一生產(chǎn)商為客戶生產(chǎn)多訂單的生產(chǎn)與分車問題,車輛有固定的容積限制,通過合理安排訂單生產(chǎn)順序及訂單分車方案,使車輛成本和產(chǎn)品變質(zhì)成本達(dá)到最小,從而降低生產(chǎn)商的成本。針對(duì)該問題,本文提出了解決方法,通過與下界比較證明了其有效性。

1 問題描述及分析

1.1 問題描述

在該問題中只有1個(gè)生產(chǎn)商,在1個(gè)調(diào)度周期初共有n個(gè)訂單Jj(j=1,2,…,n)構(gòu)成了1個(gè)作業(yè)集合,每一個(gè)周期內(nèi)的訂單只來自于同一個(gè)客戶。

本文考慮的是單機(jī)生產(chǎn)模式,訂單Jj的加工時(shí)間為pj(pj>0),體積為vj,產(chǎn)品呈線性變質(zhì),且變質(zhì)率為uj,產(chǎn)品一旦生產(chǎn)完成后便開始變質(zhì),變質(zhì)后產(chǎn)品的體積并不發(fā)生變化,生產(chǎn)單位體積產(chǎn)品需耗費(fèi)的資源價(jià)值為mj。在產(chǎn)品的生產(chǎn)過程中,機(jī)器在同一時(shí)刻只能加工1個(gè)作業(yè),并且作業(yè)是不允許中斷的。對(duì)于1個(gè)訂單Jj,Cj與Rj分別為作業(yè)的完工時(shí)間和裝車時(shí)間。生產(chǎn)商使用的車輛均是容量為Q的同型車,n個(gè)訂單分裝到不同車輛上,每輛車的裝車時(shí)間為該車輛訂單中最后1個(gè)加工訂單的完工時(shí)間。每輛車都有相同的啟動(dòng)成本,設(shè)每輛車送貨1次的成本為F,共使用K輛車,整個(gè)周期的車輛總成本為KF。假設(shè)產(chǎn)品的加工是勻速進(jìn)行的,在1個(gè)訂單中,先完成產(chǎn)品的變質(zhì)時(shí)間大于后完成產(chǎn)品的變質(zhì)時(shí)間,在單個(gè)訂單加工過程中,該訂單產(chǎn)品的平均變質(zhì)體積為vjujpj/2。在整個(gè)調(diào)度問題中,訂單Jj發(fā)生變質(zhì)的產(chǎn)品體積為vjuj(Rj-Cj+pj/2)。本文考慮的發(fā)生變質(zhì)產(chǎn)品的體積為vj′=vjuj(Rj-Cj+pj/2),這部分產(chǎn)品在交貨時(shí)不可用,其耗費(fèi)的資源成為一種浪費(fèi),先視為耗材成本,對(duì)于訂單Jj,其耗材成本即為vj′mj。由于用于交貨的產(chǎn)品量少于訂單量,缺少的這部分產(chǎn)品產(chǎn)生相應(yīng)的缺貨成本vj′gj,其中g(shù)j為單位體積的缺貨費(fèi)用。缺貨成本是由產(chǎn)品變質(zhì)產(chǎn)生的,且單位體積產(chǎn)品的耗材費(fèi)用與缺貨費(fèi)用均為常數(shù),在此問題中,將耗材成本與缺貨成本合并統(tǒng)稱為變質(zhì)成本,用lj表示單位體積產(chǎn)品的變質(zhì)費(fèi)用lj=mjgj,則訂單Jj的變質(zhì)成本即為vj′lj。生產(chǎn)訂單量產(chǎn)品所耗費(fèi)的資源價(jià)值為vjmj,這部分成本為固定成本,在此問題中不作考慮。

該生產(chǎn)與分車問題的目標(biāo)是總成本的最小化,即有：

(1)

設(shè)Π為生產(chǎn)調(diào)度的訂單加工順序集合。π∈Π為某一調(diào)度方案,π={π(1),π(2),…,π(n)},其中π(j)為調(diào)度方案π中第j個(gè)生產(chǎn)的訂單,生產(chǎn)結(jié)束時(shí)間為Cπ(j)。ψ∈Ψ為某一分車方案,ψ=[ψ(π(1)),ψ(π(2)),…,ψ(π(n))],其中,ψ[π(j)]表示裝載的車輛。

設(shè)π(j)對(duì)應(yīng)的車輛的作業(yè)集為Aπ(j)={π(i)|ψ(π(i))=ψ(π(j)),i=1,2,…,n};訂單π(j)的裝車時(shí)間為：

(2)

(3)

對(duì)于一個(gè)生產(chǎn)方案π和分車方案ψ,其使用的車輛數(shù)為K,則該生產(chǎn)與分車問題的協(xié)同優(yōu)化目標(biāo)為：

(4)

在該問題中,目的是找到最優(yōu)的生產(chǎn)與分車方案π*和ψ*,其中車輛數(shù)為K*,使得目標(biāo)函數(shù)最小化,則有：

(5)

1.2 問題分析

通過分析該協(xié)同調(diào)度問題最優(yōu)解具有的特征,并根據(jù)解的性質(zhì)提出有效的方法。

性質(zhì)1 同一車輛的訂單在生產(chǎn)過程中彼此相鄰。

圖1 最優(yōu)解性質(zhì)1的生產(chǎn)順序

綜上可知,當(dāng)某一輛車上訂單的生產(chǎn)序列中包含了非該輛車配送的訂單時(shí),均可以通過改變?cè)撚唵蔚纳a(chǎn)順序使得目標(biāo)函數(shù)減小,與最優(yōu)解中必存在某輛車的訂單不連續(xù)的假設(shè)相矛盾,因此假設(shè)不成立,則性質(zhì)1是成立的。

性質(zhì)2 每輛車上的訂單生產(chǎn)順序根據(jù)vjujlj/pj的值按照從小到大的規(guī)則排列。

圖2 最優(yōu)解性質(zhì)2車輛k的訂單生產(chǎn)順序

設(shè)Δ為圖2b所示生產(chǎn)順序的變質(zhì)成本減去圖2a所示生產(chǎn)順序的變質(zhì)成本差值,則有：

(6)

性質(zhì)3 以車輛為整體,每車訂單的加工序列既定,改變整車訂單加工的次序,不影響目標(biāo)函數(shù)值。

證明略。目標(biāo)函數(shù)不受每車訂單的加工開始時(shí)間的影響,因此改變整車訂單的加工次序不會(huì)對(duì)目標(biāo)函數(shù)產(chǎn)生影響。

2 算法及下界

2.1 算法

根據(jù)性質(zhì)1和性質(zhì)2可知,若分車方案確定,生產(chǎn)的最優(yōu)順序是可以確定的,因此本文的生產(chǎn)與分車問題可以看作是求解最優(yōu)分車方案。首先,固定容積的車輛,其使用數(shù)量必須滿足裝載全部訂單的要求。由性質(zhì)2可知,每輛車上先加工訂單的vjujlj/pj值越小越好,因此考慮將vjujlj/pj值較小的訂單分別排列在每輛車的前面加工。將所有的訂單按照vjujlj/pj值從小到大排列,再從序列中的第1個(gè)訂單開始,依次為其分配裝載車輛。

車輛容積有限制,先分配的訂單要盡可能地排列在每車訂單中的前面,因此考慮在為每個(gè)訂單分配車輛時(shí),首先選擇剩余容積最小的車輛,根據(jù)此原則構(gòu)建剩余容積最小車輛優(yōu)先算法。由于產(chǎn)品的易變質(zhì)性與時(shí)間有很大的關(guān)系,在為每個(gè)訂單分配車輛時(shí),考慮選擇已有訂單加工時(shí)間和最小的車輛,根據(jù)該原則構(gòu)建訂單加工時(shí)間和最小車輛優(yōu)先算法。

剩余容積最小車輛優(yōu)先算法步驟如下：

(2) 車輛i(i=1,2,…,K)上裝載的訂單集合為Ki,Ki中所有訂單的體積之和記為Vi,初始狀態(tài)為Ki空集,Vi=0;將訂單集合記作J,集合內(nèi)所有訂單按照vjujlj/pj值從小到大排列。

(3) 若J為空集,計(jì)算當(dāng)前解的目標(biāo)函數(shù)值,記為U′,若U′>U,則結(jié)束,返回U及其對(duì)應(yīng)的集合Ki(i=1,2,…,K);若U′≤U,則令U=U′,K=K+1,返回到步驟(2)。

(4) 將J中第1個(gè)訂單插入到Vi最小且插入后Vi≤Q的集合Ki中的最后一個(gè)位置,插入后將J中第1個(gè)訂單剔除,執(zhí)行步驟(3);若J中第1個(gè)訂單找不到滿足條件的集合Ki可以插入,則令K=K+1,返回到步驟(2)。

訂單加工時(shí)間和最小車輛優(yōu)先算法步驟為：

(3) 若J為空集,計(jì)算當(dāng)前解的目標(biāo)函數(shù)值,記為U′。若U′>U,則結(jié)束,返回及其對(duì)應(yīng)的集合Ki(i=1,2,…,K);若U′≤U,則令U=U′,K=K+1,返回到步驟(2)。

剩余容積最小車輛優(yōu)先算法與訂單加工時(shí)間和最小車輛優(yōu)先算法首先是將所有的訂單按照vjujlj/pj值從小到大排列,再依次為每個(gè)訂單分配裝載車輛,剩余容積最小車輛優(yōu)先算法分配車輛時(shí),優(yōu)先選擇剩余容積最小的車輛,訂單加工時(shí)間和最小車輛優(yōu)先算法則優(yōu)先選擇訂單加工時(shí)間和最小的車輛。

2.2 下界

本文考慮作業(yè)可中斷情形的最優(yōu)解,并將其作為問題的下界。作業(yè)可中斷,在本文研究的問題中可描述為1個(gè)訂單上的產(chǎn)品可以分多次加工,每次只加工了一部分的產(chǎn)品,但是這部分產(chǎn)品是完成品,可以先行運(yùn)送到客戶手中用于交貨,只是數(shù)量上不滿足訂單量,其中產(chǎn)品的加工時(shí)間與加工數(shù)量成正比。

在加工可中斷的情形下,問題的最優(yōu)解仍然滿足本文的3個(gè)性質(zhì),由此提出可中斷情形下的最優(yōu)算法，具體如下：

(2) 將所有訂單按照vjujlj/pj值從小到大排列,每個(gè)訂單都均分成K個(gè)部分,分別由K輛車裝載運(yùn)送,即將所有訂單的1/K訂單量的產(chǎn)品全部加工完成后裝車運(yùn)送,重復(fù)加工運(yùn)送K次,且每次訂單都是按照vjujlj/pj值從小到大的順序加工,具體如圖3所示。

(3) 計(jì)算當(dāng)前解的目標(biāo)函數(shù)值,記為U′。若U′>U,則結(jié)束,返回U及其對(duì)應(yīng)的集合Ki(i=1,2,…,K);若U′≤U,則令U=U′,K=K+1,返回到步驟(2)。

圖3 可中斷情形下的訂單加工順序

可中斷情形最優(yōu)算法是將每個(gè)訂單平均分配給每輛車,每車的訂單按照vjujlj/pj值從小到大的順序加工。

定理1 可中斷情形最優(yōu)算法能夠求得可中斷情形下的最優(yōu)解。

證明 假設(shè)定理不成立,即最優(yōu)解不是按照可中斷情形最優(yōu)算法的規(guī)則排列的,根據(jù)性質(zhì)2可知,若每一車輛上訂單的加工順序已經(jīng)是最優(yōu)的,則最優(yōu)解會(huì)出現(xiàn)以下2種情形。

(1) 最優(yōu)解的車輛數(shù)與可中斷情形最優(yōu)算法求得的車輛數(shù)相同,記為K。由性質(zhì)2可知,訂單排序既定,最優(yōu)解與可中斷情形最優(yōu)算法求得解的不同之處在于每個(gè)訂單的加工量不同,則最優(yōu)解中至少存在某一個(gè)作業(yè),有2輛車的加工量不等于該訂單量的1/K。

圖4 定理證明的分車加工順序

現(xiàn)比較圖4a與圖4b所示方案變質(zhì)成本的大小,令Δ1為圖4a所示方案變質(zhì)成本減去圖4b所示方案變質(zhì)成本，則有：

(7)

顯然,由于x≠1,必有Δ1>0,即圖4a所示方案的變質(zhì)成本大于圖4b所示方案的,這與圖4a為最優(yōu)解的假設(shè)相矛盾。

以上討論的是2輛車的情形,接下來討論多輛車的情形。設(shè)最優(yōu)解中對(duì)于某一訂單,有s輛車上的訂單加工量都不等于該訂單量的1/K,其中s≤K。

設(shè)Δ2表示最優(yōu)解的變質(zhì)成本減去可中斷情形最優(yōu)算法所得解的變質(zhì)成本。在s輛車上訂單Jj的加工量分別為ai,i=1,2,3,…,s,且a1+a2+a3+…+as=vj，則有：

(8)

由柯西不等式

可得：

(9)

(2) 最優(yōu)解的車輛數(shù)與可中斷情形最優(yōu)算法求得的車輛數(shù)不相同,設(shè)最優(yōu)解的車輛數(shù)為M,目標(biāo)函數(shù)為U1;可中斷情形最優(yōu)算法求得車輛數(shù)為K,目標(biāo)函數(shù)為U2;再令車輛數(shù)為M,運(yùn)用可中斷情形最優(yōu)算法的規(guī)則求得該車輛數(shù)下的目標(biāo)函數(shù)為U3。顯然U2≤U3,根據(jù)情形(1)的證明可以得到U3≤U1,從而有U2≤U1,這與最優(yōu)解的假設(shè)相矛盾。

以上2種情形下假設(shè)均不成立,故定理成立。

3 實(shí)驗(yàn)數(shù)據(jù)及分析

本文通過大量的實(shí)驗(yàn)數(shù)據(jù)將剩余容積最小車輛優(yōu)先算法、訂單加工時(shí)間和最小車輛優(yōu)先算法與下界比較,驗(yàn)證2個(gè)算法的有效性。算法是運(yùn)用Java語言編寫,其開發(fā)平臺(tái)為My Eclipse 8.5企業(yè)版;計(jì)算機(jī)的硬件配置為處理器Intel(R) Core(TM) i5-4590 CPU @ 3.30 GHz、內(nèi)存4.00 GB;操作系統(tǒng)為Windows7 旗艦版。

實(shí)驗(yàn)中各個(gè)參數(shù)的范圍如下:

(1) 訂單數(shù)量n={20,40,60}。

(2) 車輛容積Q={50,100}。

(3) 車輛運(yùn)送1次的固定成本F={20,50}。

(4) 訂單的加工時(shí)間pj∈U[1,10],訂單的體積vj∈U[10,20],訂單產(chǎn)品的變質(zhì)率uj∈U[0,0.01],訂單產(chǎn)品的單位成本lj∈U[1,10]。

為了客觀真實(shí)地反映2個(gè)算法的性能,本文針對(duì)Q、F、n的不同情形進(jìn)行多次實(shí)驗(yàn),每種情形下其他參數(shù)均隨機(jī)產(chǎn)生且滿足上述范圍,每種情形下進(jìn)行了5個(gè)不同算例的實(shí)驗(yàn)，結(jié)果見表1～表3所列。在3個(gè)表中,U0表示目標(biāo)函數(shù)值的下界,K0為下界對(duì)應(yīng)的車輛數(shù);U1表示剩余容積最小車輛優(yōu)先算法求得的目標(biāo)函數(shù)值,K1為其對(duì)應(yīng)的車輛數(shù);U2表示訂單加工時(shí)間和最小車輛優(yōu)先算法求得的目標(biāo)函數(shù)值,K2為其對(duì)應(yīng)的車輛數(shù);Gap1和Gap2分別表示剩余容積最小車輛優(yōu)先算法和訂單加工時(shí)間和最小車輛優(yōu)先算法的誤差界,其中,Gap1=(U1-U0)/U0,Gap2=(U2-U0)/U0。分析表1～表3中的數(shù)據(jù)可以得到以下結(jié)論：

(1) 在Q=50、F=20的情形下,剩余容積最小車輛優(yōu)先算法的誤差界在0.05～0.28之間不等,訂單加工時(shí)間和最小車輛優(yōu)先算法的誤差界在0.03～0.14之間不等;在Q=100、F=20的情形下,剩余容積最小車輛優(yōu)先算法的誤差界在0.01～0.06之間不等,訂單加工時(shí)間和最小車輛優(yōu)先算法的誤差界在0.01～0.04之間不等;在Q=100、F=50的情形下,剩余容積最小車輛優(yōu)先算法的誤差界在0.01～0.20之間不等,訂單加工時(shí)間和最小車輛優(yōu)先算法的誤差界在0.01～0.21之間不等。

(2) 比較表1和表2可以看出,當(dāng)其他參數(shù)相同、車輛容積較大時(shí),剩余容積最小車輛優(yōu)先算法與訂單加工時(shí)間和最小車輛優(yōu)先算法得到的解均更優(yōu)。其原因是車輛容積大,能裝載的訂單數(shù)增多,節(jié)省了車輛的固定成本。

(3) 分析表2和表3可以看出,當(dāng)其他參數(shù)相同、車輛固定成本較小時(shí),剩余容積最小車輛優(yōu)先算法和訂單加工時(shí)間和最小車輛優(yōu)先算法得到的解均更優(yōu)。其原因是分析當(dāng)車輛固定成本高時(shí),為了降低車輛總成本,盡可能使用較少的車輛,每輛車均處于滿載的狀態(tài),可能導(dǎo)致產(chǎn)品的變質(zhì)成本增加,而車輛成本低,可以通過增加車輛來降低產(chǎn)品的變質(zhì)成本。

(4) 從以上3種情況中可以看出,當(dāng)Q較大F較小時(shí),剩余容積最小車輛優(yōu)先算法與訂單加工時(shí)間和最小車輛優(yōu)先算法求得的解更接近下界,解較其他2種情形更優(yōu)。因此,剩余容積最小車輛優(yōu)先算法與訂單加工時(shí)間和最小車輛優(yōu)先算法更適用于Q較大F較小的情形。

(5) 從總體上來看,訂單加工時(shí)間和最小車輛優(yōu)先算法的解比剩余容積最小車輛優(yōu)先算法更接近下界,但是也存在例外的情況?？梢酝ㄟ^結(jié)合2種算法的結(jié)果來確定方案。

表2 Q=100、F=20的實(shí)驗(yàn)結(jié)果

表3 Q=100、F=50的實(shí)驗(yàn)結(jié)果

4 結(jié) 論

本文研究了單機(jī)生產(chǎn)模式下多訂單的生產(chǎn)及分車問題,即生產(chǎn)商按訂單加工產(chǎn)品并裝車運(yùn)送到客戶處。訂單產(chǎn)品是具有易變質(zhì)性的冷鏈產(chǎn)品,本文對(duì)產(chǎn)品的加工順序及分車情況進(jìn)行聯(lián)合優(yōu)化,優(yōu)化的目標(biāo)是使車輛成本與產(chǎn)品變質(zhì)成本之和最小化。通過對(duì)問題的分析,本文提出了幾條最優(yōu)解的性質(zhì),在此基礎(chǔ)上,提出了2個(gè)優(yōu)化算法和1個(gè)問題下界,并通過實(shí)驗(yàn)數(shù)據(jù)將2個(gè)算法所得解與下界進(jìn)行比較,結(jié)果表明，這2個(gè)算法能夠求解出較優(yōu)的聯(lián)合調(diào)度與分車方案,并且在車輛容量較大、成本較小的情況下,算法的優(yōu)化性能更好,能得到非常高質(zhì)量的滿意解。

[1] 楊愛峰,李佐平.基于產(chǎn)品變質(zhì)和零售商部分延期支付的EOQ模型[J].合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版),2011,34(9):1413-1418.

[2] CHENG T C E,KAHIBACHER H G.Scheduling with delivery and earliness penalties[J].Asia Pacific Journal of Operational Research,1993,10(2):145-152.

[3] CHENG T C E,GORDON V S,KOVALYOV M Y.Single machine scheduling with batch delivery[J].European Journal of Operational Research,1996,94(2):227-283.

[4] MAZDEH M M,SHASHAANI S,ASHOURI A,et al.Single-machine batch scheduling minimizing weighted flow times and delivery costs[J].Applied Mathematical Modelling,2011,35(1):563-670.

[5] HAMIDINIA A,KHAKABIMAMAGHANI S,MAZDEH M M,et al.A genetic algorithm for minimizing total tardiness/earliness of weighted jobs in a batched delivery system[J].Computers & Industrial Engineering,2012,62(1):29-38.

[6] 倪志偉,朱旭輝,伍章俊.隨機(jī)需求下多周期供應(yīng)鏈庫存配送聯(lián)合優(yōu)化模型[J].合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版),2015,38(1):121-126.

[7] AHMADIZAR F,FARHADI S.Single-machine batch delivery scheduling with job release dates,due windows and earliness,tardiness,holding and delivery costs[J].Computers & Operations Research,2015,53:194-205.

[8] ARMSTRONG R,GAO S,LEI L.A zero-inventory production and distribution problem with a fixed customer sequence[J].Annals of Operations Research,2008,159(1): 395-414.

[9] VIRGUTZ C,KNUST S.Integrated production and distribution scheduling with lifespan constraints[J].Annals of Operations Research,2014,213(1):293-318.

[10] AMORIM P,BELO-FILHO M A F,TOLEDO F M B,et al.Lot sizing versus batching in the production and distribution planning of perishable goods[J].International Journal of Production Economics,2013,146(1):208-218.

[11] 周泓,夏曉雯.易變質(zhì)產(chǎn)品的生產(chǎn)計(jì)劃與作業(yè)排序集成優(yōu)化研究[J].計(jì)算機(jī)工程與應(yīng)用,2010,46(18):192-195.

[12] CHEN H K,HSUEH C F,CHANG M S.Production scheduling and vehicle routing with time windows for perishable food products[J].Computers & Operations Research,2009,36(1):2311-2319.

[13] 李娜,王首彬.不確定需求下易腐產(chǎn)品的生產(chǎn)配送優(yōu)化模型[J].計(jì)算機(jī)應(yīng)用研究,2011,28(3):927-929.

(責(zé)任編輯 萬倫來)

Integrated production and batch delivery scheduling for perishable products

MA Ying1,2, MA Jingjing1, LI Kai1,2

(1.School of Management, Hefei University of Technology, Hefei 230009, China; 2.Key Laboratory of Process Optimization and Intelligent Decision Making of Ministry of Education, Hefei University of Technology, Hefei 230009, China)

In this paper, the integration problem of production and batch delivery in cold chain environment under single-machine production mode is considered. Manufacturer produces the products of multiple orders on the single machine, then delivers them to customers by several identical vehicles. Extra deterioration cost is produced over time due to the perishability of products and vehicle cost is also produced from the delivery. So it is necessary to arrange production and delivery batches reasonably to minimize the total cost including vehicles cost and deterioration cost. Problem analysis is done firstly to present several properties of optimal solutions, based on which two algorithms and a lower bound are proposed. Finally, the validity of these two algorithms are shown by large-scale experiments of random data.

production; batch delivery; integrated scheduling; perishable product; single machine

2015-07-29；

2015-09-23

國家自然科學(xué)基金資助項(xiàng)目(71201046;71471052);安徽省自然科學(xué)基金資助項(xiàng)目(1208085QG133)

馬 英(1979-),女,安徽淮北人,博士,合肥工業(yè)大學(xué)副教授,碩士生導(dǎo)師.

10.3969/j.issn.1003-5060.2017.01.023

O223;F406.2;TP301.6

A

1003-5060(2017)01-0128-08