陳榮軍,唐國(guó)春

(1.常州工學(xué)院理學(xué)院,江蘇 常州 213032;2.上海第二工業(yè)大學(xué)管理工程研究所,上海 201209)

1 引言

在現(xiàn)代工商業(yè)領(lǐng)域,轉(zhuǎn)包策略正在被越來越廣泛地應(yīng)用.通過轉(zhuǎn)包,制造商至少可以實(shí)現(xiàn)以下兩個(gè)目的:一是實(shí)現(xiàn)產(chǎn)品按期交貨.由于受自身生產(chǎn)能力、存儲(chǔ)條件等限制,制造商往往無法在規(guī)定期限內(nèi)完成生產(chǎn)任務(wù),這時(shí)需要將部分訂單轉(zhuǎn)包給承包商加工,以提高自身對(duì)市場(chǎng)的響應(yīng)能力;二是節(jié)約投資成本.由于產(chǎn)品往往由多道工序組成,需要不同的生產(chǎn)設(shè)備及技術(shù).通過將部分工序轉(zhuǎn)包,制造商可以將有限資源用于關(guān)鍵技術(shù)研發(fā)與重要設(shè)備更新,不僅提高了企業(yè)核心競(jìng)爭(zhēng)力,還節(jié)約投資成本,降低因市場(chǎng)變化而帶來的投資風(fēng)險(xiǎn).當(dāng)然,制造商因執(zhí)行轉(zhuǎn)包任務(wù)需要分出一定額度利潤(rùn)給承包商.為了實(shí)現(xiàn)自身利益的最大化,制造商往往需要同時(shí)考慮哪些工件或工序需要轉(zhuǎn)包,哪些工件或工序自己加工,以及工件的加工次序,即排序.因此,研究轉(zhuǎn)包策略具有非常重要的應(yīng)用背景.

關(guān)于排序與轉(zhuǎn)包的集成研究引起了許多學(xué)者的興趣,在過去十多年里發(fā)表了一批相關(guān)研究成果,這些成果重點(diǎn)圍繞制造商或承包商機(jī)器加工方式,轉(zhuǎn)包費(fèi)用以及工件運(yùn)輸方式等展開.下面重點(diǎn)介紹在平行機(jī)加工環(huán)境下的部分研究成果.

文獻(xiàn)[1]等研究產(chǎn)品具有時(shí)間敏感性的排序與轉(zhuǎn)包問題,假設(shè)制造商為平行機(jī)加工環(huán)境且承包商具有無限加工能力,目標(biāo)是在工件最大完工時(shí)間不超過給定值情況下,極小化加工與轉(zhuǎn)包費(fèi)用和,設(shè)計(jì)啟發(fā)式算法并分析了算法的漸進(jìn)性能比.文獻(xiàn)[2]等研究單階段排序問題,假設(shè)工件既可以在內(nèi)部制造商機(jī)器加工,也可以轉(zhuǎn)包給外面的承包商加工.內(nèi)部制造商有一個(gè)獨(dú)立的平行機(jī)系統(tǒng),而承包商有一臺(tái)單機(jī)可以加工所有工件.研究?jī)?nèi)部加工工件和轉(zhuǎn)包工件之集成排序,目標(biāo)是極小化全部工件加工時(shí)間與轉(zhuǎn)包費(fèi)用和,提出了整數(shù)規(guī)劃算法以及啟發(fā)式算法,后者是將原問題分解為若干小且易解決的子問題并求出這些子問題的最優(yōu)解.

文獻(xiàn) [3]等研究工件允許轉(zhuǎn)包的單階段平行機(jī)排序問題,目標(biāo)是從可用的機(jī)器集(或承包商)中選出一些用于加工這些工件,目標(biāo)是極小化若干費(fèi)用函數(shù).假設(shè)工件加工時(shí)間相同且分配給每臺(tái)機(jī)器(或承包商)的工件數(shù)有一個(gè)上界和下界,分別研究了下界為0以及一般情形.文獻(xiàn)[4]等研究平行機(jī)環(huán)境下的排序與轉(zhuǎn)包問題,目標(biāo)是極小化轉(zhuǎn)包與延誤費(fèi)用和,他們?cè)O(shè)計(jì)了蟻群算法,并進(jìn)行了數(shù)值試驗(yàn).

文獻(xiàn) [5]研究平行機(jī)環(huán)境下工件排序與轉(zhuǎn)包問題,基于人工團(tuán)隊(duì)過程算法 (簡(jiǎn)稱TPA)設(shè)計(jì)了智能決策算法.同時(shí),為了提高解的質(zhì)量,在TPA每一迭代步設(shè)計(jì)了具有三種鄰域結(jié)構(gòu)的鄰域搜索算法(簡(jiǎn)稱NSA).此外,作者還用列排序算法(簡(jiǎn)稱LS),GA,SA算法求解被研究問題,并對(duì)計(jì)算結(jié)果進(jìn)行比較.同年,文獻(xiàn)[6]研究平行機(jī)排序問題,目標(biāo)是在工件最大延遲不超過給定值的情況下,極小化資源消耗與轉(zhuǎn)包費(fèi)用和,證明該問題在可中斷情況下是多項(xiàng)式可解的,而在非中斷情況下是強(qiáng)NP困難的,提出了分支定界算法及混合數(shù)學(xué)算法分別求得精確和近似解,并進(jìn)行算法驗(yàn)證.

文獻(xiàn)[7]研究n個(gè)單操作任務(wù)(或工件)要在m臺(tái)平行機(jī)上加工的排序問題,且允許工件轉(zhuǎn)包.當(dāng)一臺(tái)機(jī)器或承包商被選中加工工件時(shí),需要付出一次性的固定費(fèi)用;當(dāng)一工件被一機(jī)器或承包商加工時(shí),需要付出依賴于該機(jī)器或承包商的加工費(fèi)用.目標(biāo)是從m個(gè)空閑機(jī)器和(或)承包商中,選擇k個(gè)機(jī)器和(或)承包商加工全部工件,極小化加工費(fèi)用與固定費(fèi)用和.證明了問題的NP困難性,并設(shè)計(jì)了有效的禁忌搜索算法,用中等規(guī)模實(shí)例進(jìn)行驗(yàn)證.

除上述平行機(jī)加工環(huán)境外,近些年不少學(xué)者還研究了制造商為單機(jī),自由作業(yè),流水作業(yè),異序作業(yè)等加工環(huán)境下的排序與轉(zhuǎn)包問題[8-14],限于篇幅,本文不再詳細(xì)闡述.

本文繼續(xù)研究制造商是平行機(jī)環(huán)境的排序與轉(zhuǎn)包問題,且假設(shè)承包商僅有一臺(tái)單機(jī).工件在制造商和承包商機(jī)器上所需的加工時(shí)間與費(fèi)用均不同,且轉(zhuǎn)包工件需要運(yùn)回到制造商.本文需要確定轉(zhuǎn)包工件集與全部工件加工順序,分別極小化幾個(gè)經(jīng)典排序目標(biāo)與轉(zhuǎn)包費(fèi)用和.本文余下部分是這樣安排的:第2節(jié)介紹問題的模型及相關(guān)記號(hào);第3-5節(jié)分別研究工件總完工時(shí)間,工件最大延誤,誤工工件數(shù)與轉(zhuǎn)包費(fèi)用和三個(gè)不同目標(biāo)問題,分析問題困難性,并設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法,最后第6節(jié)總結(jié)全文.

2 模型與符號(hào)

假設(shè)制造商有m臺(tái)平行機(jī){M1,M2,···,Mm},需要加工一批工件,記為

工件j∈N在制造商每臺(tái)機(jī)器上需要加工時(shí)間pj,工期為dj.為了盡快完成加工任務(wù),制造商常常要把部分工件轉(zhuǎn)包給承包商加工.設(shè)承包商僅有一臺(tái)單機(jī),如果工件j∈N轉(zhuǎn)包給承包商單機(jī)加工,需要加工時(shí)間αpj和加工費(fèi)用βpj,其中α>0,β>0為常數(shù).工件j被承包商加工后,即刻由專門工具運(yùn)回制造商,但需要花費(fèi)時(shí)間τ.

記Cj為工件j完工時(shí)間.如果工件j在制造商處加工,則它在平行機(jī)上完成加工的時(shí)刻即為Cj;否則,工件j在承包商處加工,將其運(yùn)回至制造商的時(shí)刻稱為完工時(shí)間.令Lmax=max{Lj,j∈N},其中Lj=Cj?dj,j∈N.置

本文研究哪些工件要在制造商平行機(jī)上加工,哪些工件要轉(zhuǎn)包給承包商加工,以及工件在這些機(jī)器上的加工順序即排序,使給定的目標(biāo)函數(shù)最優(yōu).用傳統(tǒng)三參數(shù)法[15]將本文問題記為m+1||λf+(1?λ)G,其中 “m+1”表示制造商有m臺(tái)平行機(jī),承包商有一臺(tái)單機(jī),為經(jīng)典排序目標(biāo)函數(shù),G為工件總轉(zhuǎn)包費(fèi)用,λ∈[0,1]為常數(shù).

定理 2.1是普通意義下NP困難的.

4 問題 m+1||λLmax+(1?λ)G

對(duì)問題m+1||λLmax+(1?λ)G,由問題 1||Lmax最優(yōu)性,有性質(zhì)4.1:

性質(zhì) 4.1對(duì)問題m+1||λLmax+(1?λ)G,存在最優(yōu)排序,在制造商及承包商機(jī)器上工件按EDD序加工.

根據(jù)性質(zhì)4.1,設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法,記DF 2,用于求解問題

將全部工件按照EDD序重新編號(hào),并記Aj={1,2,,···,j},j∈N.取(j,t1,t2,···,tm)為狀態(tài)變量,其中tk為工件集Aj分配在機(jī)器Mk上工件加工總長(zhǎng).令L(j,t1,t2,···,tm)為在狀態(tài) (j,t1,t2,···,tm)下Lmax最優(yōu)值.

6 結(jié)束語

本文研究了制造商為平行機(jī)加工環(huán)境下的排序問題,且工件可以轉(zhuǎn)包給僅有一臺(tái)單機(jī)的承包商加工,分別為極小化工件總完工時(shí)間,最大延誤,誤工工件數(shù)與轉(zhuǎn)包費(fèi)用和的三個(gè)目標(biāo).本文分析了問題的NP困難性,并設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法.對(duì)于其它復(fù)雜機(jī)器環(huán)境或者目標(biāo)函數(shù)的問題,如何設(shè)計(jì)有效算法,值得繼續(xù)研究.