一類(lèi)帶外包選擇的單機(jī)排序問(wèn)題

葉飛浪,劉　麗,陳光亭

(杭州電子科技大學(xué)理學(xué)院，浙江 杭州 310018)

?

一類(lèi)帶外包選擇的單機(jī)排序問(wèn)題

葉飛浪,劉麗,陳光亭

(杭州電子科技大學(xué)理學(xué)院，浙江 杭州 310018)

研究了一類(lèi)帶外包選擇的單機(jī)排序問(wèn)題.假設(shè)僅有一臺(tái)本地機(jī)器和一個(gè)外包承包商，每個(gè)工件既可以在本地機(jī)器上加工又可以外包商處加工.本地加工的費(fèi)用為總誤工工件數(shù)，外包加工的費(fèi)用與外包工件有關(guān).對(duì)于極小化總加工費(fèi)用這一NP難問(wèn)題，給出偽多項(xiàng)式時(shí)間動(dòng)態(tài)規(guī)劃算法.如果外包費(fèi)用正比于外包工件的加工時(shí)間，設(shè)計(jì)出近似算法并給出最壞情況分析.

排序；外包；動(dòng)態(tài)規(guī)劃；近似算法

0　引　言

設(shè)有n個(gè)工件、一臺(tái)本地機(jī)器及一個(gè)外部承包商，工件既可以在本地機(jī)器上加工，又可以選擇外包加工，上述問(wèn)題稱(chēng)為帶外包選擇的排序問(wèn)題[1].文獻(xiàn)[1]提出并對(duì)問(wèn)題進(jìn)行定性分析，文獻(xiàn)[2-5]研究本地機(jī)器為多臺(tái)平行機(jī)的情形，文獻(xiàn)[6-8]研究本地機(jī)器為單臺(tái)機(jī)情形.這些文獻(xiàn)都假設(shè)本地機(jī)器的費(fèi)用為工件的最大完工時(shí)間，而本文考慮本地加工的費(fèi)用為總誤工工件數(shù)，并假定外包加工的費(fèi)用與外包工件相關(guān).研究目標(biāo)為極小化總加工費(fèi)用的排序問(wèn)題，由于在外包費(fèi)用足夠大時(shí)該問(wèn)題等價(jià)于經(jīng)典背包問(wèn)題，因此顯然是NP-困難的.假設(shè)工件Jj的加工時(shí)間為pj(正整數(shù))，交工期為dj，外包費(fèi)用為qj.記Jj的完工時(shí)間為Cj，如果Cj>dj，此時(shí)工件延誤，記Uj=1；否則工件不延誤，記Uj=0.若以I和O分別表示本地和外包加工工件的集合，本地的誤工工件數(shù)作為本地加工的費(fèi)用，則本地加工的費(fèi)用為∑IUj，外包加工的費(fèi)用為∑Oqj，從而總加工費(fèi)用為∑IUj+∑Oqj.本文首先利用動(dòng)態(tài)規(guī)劃給出極小化總加工費(fèi)用問(wèn)題的一個(gè)偽多項(xiàng)式時(shí)間算法，接著對(duì)外包費(fèi)用正比于外包工件的加工時(shí)間，即qj=xpj的情形，設(shè)計(jì)多項(xiàng)式時(shí)間近似算法，并給出最壞情況分析.

1　算法設(shè)計(jì)與分析

1.1∑IUj+∑Oqj問(wèn)題的動(dòng)態(tài)規(guī)劃算法

下面給出問(wèn)題的動(dòng)態(tài)規(guī)劃算法:

為設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法，先按工件的交工期從小到大順序?qū)⒐ぜ匦聵?biāo)記(即EDD序)，d1≤d2≤…≤dn.接著定義H(j,m,t)為本地加工總時(shí)長(zhǎng)為t、工件個(gè)數(shù)為m時(shí)前j個(gè)工件的最優(yōu)目標(biāo)值.顯然m≤1時(shí)，由于t為本地加工總時(shí)長(zhǎng)，則t=0或t=p1.當(dāng)j=1時(shí)，顯然有

一般地，如果工件Jj外包加工，則加工費(fèi)用增加qj；如果Jj本地加工且t≤dj，加工費(fèi)用不改變，則Jj可在t-pj時(shí)刻開(kāi)工而不誤工；如果Jj本地加工且t>dj，加工費(fèi)用增加1，則Jj在t-pj時(shí)刻開(kāi)工必然導(dǎo)致誤工.因此，H(j,m,t)可通過(guò)遞歸表達(dá)式計(jì)算

從而，問(wèn)題的最優(yōu)值就可以由min{H(n,m,t)|m=0,1,…，n;t=0,1,…,P}求解，相應(yīng)最優(yōu)解也可以通過(guò)一般的回溯法產(chǎn)生.

由于j、m的可能取值有n個(gè)，t的可能取值有P個(gè)，因此算法的時(shí)間復(fù)雜度為O(n2P)，即該動(dòng)態(tài)規(guī)劃是一個(gè)偽多項(xiàng)式時(shí)間算法.

1.2∑IUj+∑Oxpj問(wèn)題的近似算法

當(dāng)不考慮外包費(fèi)用，單臺(tái)機(jī)極小化誤工工件數(shù)的排序問(wèn)題可由Moore算法[9]得到最優(yōu)解.而當(dāng)外包費(fèi)用與加工時(shí)間成正比時(shí)，即qj=xpj(x>0)，本文設(shè)計(jì)了算法ALGO，步驟如下:

1)將工件排成EDD序，即d1≤d2≤…≤dn；

2)用Moore算法求解單臺(tái)機(jī)極小化誤工工件數(shù)的排序問(wèn)題，設(shè)所得排序中誤工工件集為T(mén)而按時(shí)完工工件的集合記為E；

3)將E中的工件加入I，并在本地機(jī)器上按EDD順序加工；

4)對(duì)于T中的工件Jj，如果xpj≥1，則Jj加入I，將其放在E工件之后加工；否則，將Jj加入O，通過(guò)外包加工.

證明不妨用OUTALGO表示算法目標(biāo)值，OPT表示最優(yōu)值.注意到工件加工時(shí)間pj為正整數(shù)，對(duì)x分情況討論如下：

2　結(jié)束語(yǔ)

本文研究了一類(lèi)帶外包選擇的排序問(wèn)題，在有一臺(tái)本地機(jī)器、一個(gè)外包商的前提下，考慮了極小化本地和外包總加工費(fèi)用的NP-難問(wèn)題，首先給出了一個(gè)偽多項(xiàng)式時(shí)間算法，接著對(duì)外包費(fèi)用正比于加工時(shí)間的情形設(shè)計(jì)了一個(gè)近似算法并給出了算法的最壞情況分析.

[1]BERTRAND J W M,Sridharan V.A study of simple rules for subcontracting in make-to-order manufacturing[J].European Journal of Operational Research,2001,128(3):509-531.

[2]CHEN Z L,LI C L.Scheduling with subcontracting options[J].IIE Transactions,2008,40(12):1171-1184.

[3]CHENG R J,TANG G C.Scheduling and subcontracting under parallel machines[J].Chinese Quarterly Journal of Mathematics,2012,27(4):590-597.

[4]QI X.Coordinated logistics scheduling for in-house production and outsourcing[J].IEEE Transactions on Automation Science and Engineering,2008,5(1):188-192.

[5]Qi X.Two-stage production scheduling with an option of outsourcing from a remote supplier[J].Journal of Systems Science and Systems Engineering,2009,18(1):1-15.

[6]LEE I S,SUNG C S.Single machine scheduling with outsourcing allowed[J].International Journal of Production Economics,2008,111(2):623-634.

[7]仲維亞,劉曉蕾,霍志明.工件可轉(zhuǎn)包加工的排序問(wèn)題研究[J].運(yùn)籌學(xué)學(xué)報(bào),2012,16(1):121-126.

[8]ZHONG W Y,HUO Z M.Single machine scheduling problems with subcontracting options[J].Journal of Combinatorial Optimization,2013,26(3):489-498.

[9]MOORE J M.An n-jobs,one machine sequencing algorithm for minimizing the number of late jobs[J].Management Science,1968,15(1):102-109.

Single Machine Scheduling with Subcontracting Options

YE Feilang, LIU Li, CHEN Guangting

(SchoolofScience,HangzhouDianziUniversity,HangzhouZhejiang310018,China)

This paper studies single-machine scheduling with subcontracting options. There is a single machine in-house and only one subcontractor. Each job can either be scheduled in-house or be subcontracted. The production cost on the in-house machine is measured by the number of tardy jobs, while the outsourcing cost is determined by the subcontracted jobs. The problem of minimizing the total cost is NP-hard. It gives a pseudo-polynomial time algorithm based on the dynamic programming method. Moreover, if the outsourcing cost is proportional to the total processing time of subcontracted jobs, then an approximation algorithm with worst case analysis is designed.

scheduling; subcontracting; dynamic programming; approximation algorithm

10.13954/j.cnki.hdu.2016.01.018

2015-05-22

國(guó)家自然科學(xué)基金資助項(xiàng)目(11571252，11201105)

葉飛浪(1991-)，男，浙江永康人，碩士研究生，運(yùn)籌學(xué)與控制論.通信作者：陳光亭教授，E-mail:gtchen@hdu.edu.cn.

O221.7

A

1001-9146(2016)01-0090-03