葉飛浪,劉　麗,陳光亭

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

?

一類帶外包選擇的單機排序問題

葉飛浪,劉麗,陳光亭

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

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

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

0　引　言

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

1　算法設計與分析

1.1∑IUj+∑Oqj問題的動態(tài)規(guī)劃算法

下面給出問題的動態(tài)規(guī)劃算法:

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

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

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

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

1.2∑IUj+∑Oxpj問題的近似算法

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

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

2)用Moore算法求解單臺機極小化誤工工件數(shù)的排序問題，設所得排序中誤工工件集為T而按時完工工件的集合記為E；

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

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

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

2　結(jié)束語

本文研究了一類帶外包選擇的排序問題，在有一臺本地機器、一個外包商的前提下，考慮了極小化本地和外包總加工費用的NP-難問題，首先給出了一個偽多項式時間算法，接著對外包費用正比于加工時間的情形設計了一個近似算法并給出了算法的最壞情況分析.

[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)包加工的排序問題研究[J].運籌學學報,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

國家自然科學基金資助項目(11571252，11201105)

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

O221.7

A

1001-9146(2016)01-0090-03