平行機排序與轉包問題的動態(tài)規(guī)劃算法

陳榮軍,唐國春

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

1 引言

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

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

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

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

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

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

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

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

2 模型與符號

假設制造商有m臺平行機{M1,M2,···,Mm},需要加工一批工件,記為

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

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

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

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

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

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

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

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

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

6 結束語

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