榮建華, 侯麗英

(1.石家莊鐵道大學 四方學院 ，河北 石家莊 051132;2.南京農(nóng)業(yè)大學 理學院，江蘇 南京 210095)

三臺可拒絕平行機在線排序問題的近似算法

榮建華1, 侯麗英2

(1.石家莊鐵道大學 四方學院 ，河北 石家莊 051132;2.南京農(nóng)業(yè)大學 理學院，江蘇 南京 210095)

同型機； 拒絕費用；中斷加工 ； 運籌學；在線排序；競爭比

0 引言

在經(jīng)典的排序文獻中，所有的工件都不允許被拒絕，換言之，任何工件都必須被安排到機器上進行加工。然而在工廠實際生產(chǎn)過程中，生產(chǎn)決策者們并非總是如此。在現(xiàn)有的生產(chǎn)資源有限的前提下，為了使企業(yè)獲得更多的利潤，生產(chǎn)廠家有時不得不拒絕一些資源耗費較多但帶來的利潤卻較少的工件，所以工件帶拒絕費用的排序問題受到研究人員廣泛的關(guān)注。本文主要研究了工件帶拒絕費用的3臺平行機在線排序問題。基本模型描述如下：設(shè)有3臺機器M1，M2，M3和n個工件J1,J2,…,Jn，每臺機器的加工速度相同，每個工件Jj帶兩個參數(shù)(tj,pj),tj表示其加工時間,pj表示其拒絕費用。當工件Jj到達后，生產(chǎn)決策者需馬上做出決定，工件可以被拒絕，但要付出一定的拒絕費用；也可以選擇被加工，花費一定的加工時間。目標為拒絕工件的總拒絕費用與加工工件的最晚完工時間(makespan)之和最小。進一步,當工件被拒絕時文中設(shè)計出H1,H2兩套拒絕策略，且兩種拒絕策略相互獨立，最后輸出目標值較好的一種。

1 H算法

為了便于設(shè)計算法和分析競爭比，下面對文中涉及到的符號作統(tǒng)一規(guī)定：

H算法

(2)最終取目標值較好的方案。

證明 情形1：首先討論由策略H1生成的排序。

子情形1.1：如果所有工件均被拒絕，則有

子情形1.2：假定不是所有工件被拒絕，令x為策略H1中最后一個完工工件，由LS規(guī)則：

(1)

(2)

(3)

情形2：其次討論由策略H2生成的排序。

子情形2.1：如果所有工件均被拒絕，則有

子情形2.2：如果不是所有工件均被拒絕，令y為策略H2中最后一個完工工件，由LS規(guī)則

(4)

(5)

(6)

2 結(jié)語

[1]BartalY,LeonardiS,Marchetti-SpaccamelaA,etal.Multiprocessorschedulingwithrejection[J].SiamJournalonDiscreteMathematics,2000,13(1):64-78.

[2]閔嘯.一特殊情形不可中斷的兩臺可拒絕同型平行機在線排序問題[J].數(shù)學的實踐與認識,2006,36(6):163-169.

[3]閔嘯.一特殊情形的三臺可拒絕同型機在線排序問題[J].嘉興學院學報,2006,18(3):44-47.

[4]閔嘯，張玉才.一個可中斷兩臺可拒絕同型機半在線排序問題[J].浙江大學學報：理學版,2007,34(5):509-514.

[5]MINXiao,KONGXiangqing.Semion-lineschedulingontwoidenticalmachineswithrejection[J].ORTransactions,2009,13(1):29-36.

[6]閔嘯，劉靜，王玉青. 兩臺可中斷同類機可拒絕半在線排序問題的近似算法[J].浙江大學學報：理學版, 2010,37(5):519-523.

[7]榮建華，侯麗英.帶拒絕費用的平行機在線排序[J].石家莊鐵道大學學報:自然科學版,2016,29(2): 107-110.

On-line Scheduling on Three Identical Machines with Rejection

Rong Jianhua1, Hou Liying2

(1.Department of Basic Courses,Shijiazhuang Tiedao University Sifang College,Shijiazhuang 051132,China;2.College of Sciences,Nanjing Agricultural University,Nanjing 210095,China)

identical machine;rejection;preemptive;operations research;on-line scheduling；competitive ratio

南京農(nóng)業(yè)大學青年科技創(chuàng)新基金(0506J0116)河北省高等教育教學改革研究與實踐項目(2015GJJG293);河北省高等教育科學研究課題 (GJXH2015-291)

榮建華(1981-)，女，碩士，講師，主要從事組合最優(yōu)化、近似算法、排序論的研究。E-mail:rongjianhua2006@126.com

O223

A

2095-0373(2017)02-0101-05

2016-06-01 責任編輯:劉憲福

10.13319/j.cnki.sjztddxxbzrb.2017.02.18

榮建華,侯麗英.三臺可拒絕平行機在線排序問題的近似算法[J].石家莊鐵道大學學報:自然科學版,2017,30(2):101-104.