劉 澈，羅成新

（沈陽師范大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，沈陽 110034）

帶有不可用區(qū)間的單機排序問題

劉 澈，羅成新

（沈陽師范大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，沈陽 110034）

考慮的是帶有到達(dá)時間、拒絕工件、不可用區(qū)間的單機排序問題。一個工件或者被拒絕加工，或者被接受。若工件被拒絕加工，廠家必須支付一定的拒絕懲罰；若工件被接受，則把工件放在機器上進(jìn)行加工。在張麗琦工作的基礎(chǔ)上增加了一個不可用區(qū)間，機器在此區(qū)間內(nèi)不能加工工件，并且在同一時刻至多加工一個工件。目標(biāo)函數(shù)是最小化所有接受工件的時間表長與所有拒絕工件的拒絕懲罰之和。首先給出一個動態(tài)規(guī)劃算法，然后通過構(gòu)造輸入，將拒絕懲罰進(jìn)行取整運算，再通過動態(tài)規(guī)劃算法，得到拒絕懲罰取整后的一個最優(yōu)排序，按照這個工件排序得到原問題的一個可行排序，最后借助一個3—因子算法得到一個全多項式時間近似方案。

到達(dá)時間；拒絕工件；不可用區(qū)間；時間表長

在經(jīng)典排序問題中，所有的工件必須被接受，拒絕工件是不允許的。然而，在實際生產(chǎn)中，廠家為了獲得更大的利潤，通常會拒絕那些加工時間長且獲利相對小的工件，也因此得到一定的懲罰。在加工工件時，通常也會因為機器故障、工人問題等其他原因造成機器在某一時間段內(nèi)不能加工工件，即產(chǎn)生了不可用區(qū)間。由于上述問題的實用性，帶有拒絕工件及不可用區(qū)間的排序問題得到了越來越多人的關(guān)注。

Zhang等［1］研究的是帶有到達(dá)時間和拒絕工件的單機排序問題，證明出文獻(xiàn)所研究的問題是NP－難的。此外，還有許多文獻(xiàn)研究的也是帶有拒絕工件的排序問題［2－4］。Kacem［5］研究的是在帶不可用區(qū)間的條件下，極小化時間表長問題。Kacem等［6］研究的是帶不可用區(qū)間的極小化加權(quán)流時間的單機排序問題。此外，文獻(xiàn)［7-10］研究的也是帶有不可用區(qū)間的排序問題。Woeginger［11］研究的是滿足一定條件的動態(tài)規(guī)劃算法能夠得到全多項式時間近似方案，文獻(xiàn)［12-14］是對相應(yīng)的問題分別得到了全多項式時間近似方案。

本章在文獻(xiàn)［1］的基礎(chǔ)上加了一個不可用區(qū)間，運用文獻(xiàn)［1］的方法設(shè)計了一個全多項式近似方案。

1 問題描述

2 動態(tài)規(guī)劃算法

3 全多項式近似方案Aε

算法Aε

4 結(jié) 論

本章考慮的是帶有到達(dá)時間，拒絕工件，不可用區(qū)間的單機排序問題，目標(biāo)函數(shù)是最小化時間表長與所有拒絕工件的懲罰的和。給出了一個動態(tài)規(guī)劃算法及一個全多項式時間近似方案，此全多項式時間近似方案的時間復(fù)雜性為

［1］ZHANG Liqi，LU Lingfa，YUAN Jinjiang.Single machine scheduling with release dates and rejection［J］.Eur J Oper Res，2009，198（3）：975-978.

［2］LI Shisheng，YUAN Jinjiang.Parallel-machine scheduling with deteriorating jobs and rejection［J］.Theor Comput Sci，2009，411（40／41／42）：3642-3650.

［3］CHENG Yushao，SUN Shijie.Scheduling linear deteriorating jobs with rejection on a single machine［J］.Eur J Oper Res，2009，194（1）：18-27.

［4］SEIDEN S S.Preemptive multiprocessor scheduling with rejection［J］.Theor Comput Sci，2001，262（1／2）：437-458.

［5］KACEM I.Approximation algorithms for the makespan minimization with positive tails on a single machine with a fixed non－availability interval［J］.J Comb Opt，2009，17（2）：117-133.

［6］KACEM I，MAHJOUB A R.Fully polynomial time approximation scheme for the weighted flow-time minimization on a single machine with a fixed non-availability interval［J］.Comput Indust Eng，2009，56（4）：1708-1712.

［7］KACEM I.Approximation algorithms for the makespan minimization with positive tails on a single machine with a fixed non-availability interval［J］.J Comb Optim，2009，17（2）：117-133.

［8］MOSHEIOV G，ORON D.Due-date assignment and maintenance activity scheduling problem［J］.Math Comput Modeling，2006，44（11／12）：1053-1057.

［9］KELLERER H，KUBZIN M A，STRUSEVICH V A.Two simple constant ratio approximation algorithms for minimizing the total weighted completion time on a single machine with a fixed non-availability interval［J］.Eur J Oper Res，2009，199（1）：111-116.

［10］MOSHEIOV G，SARIG A.Scheduling a maintenance activity to minimize total weighted completion-time［J］.App Math Comput，2009，57（4）：619-623.

［11］WOEGINGER G J.When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximationscheme（FPTAS）？［J］.Informs J Comput，2000，12（1）：57-75.

［12］KACEM I.Fully polynomial time approximation scheme for the total weighted tardiness minimization with a common due date［J］.Discrete Appl Math，2010，158（9）：1035-1040.

［13］KELLERER H，STRUSEVICH V A.A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date［J］.Theor Comput Sci，2006，369（1／2／3）：230-238.

［14］喬玉，羅成新.具有禁用區(qū)間的平行機排序時間表長問題的全多項式近似方案［J］.沈陽師范大學(xué)學(xué)報：自然科學(xué)版，2012，30（1）：12-15.

［15］劉澈.帶到達(dá)時間和不可用區(qū)間以及拒絕工件的排序問題［D］.沈陽：沈陽師范大學(xué)，2013.

Single machine scheduling problem with unavailable interval

LIU Che，LUO Chengxin

（School of Mathematics and System Science，Shenyang Normal University，Shenyang 110034，China）

In this paper，we consider a single machine scheduling problem with release dates，rejection and an unavailable interval.A job is either rejected，in which case a rejection penalty has to be paid，or accepted and processed on the machine.Based on the work of Zhang Liqi，we add an unavailable interval，in that the machine is unavailable in an unavailable interval，and it can process at most one job at a time.The objective is to minimize the sum of the makespan of the accepted jobs and total rejection penalty of the rejected jobs.First we propose a dynamic programming algorithm，and construct the input，then round the input and get an optimal schedule by the dynamic programming algorithm，and thus get a feasible schedule for the original problem.Finally we obtain a fully polynomial-time approximation scheme for this problem by using 3-approximation algorithm.

release dates；rejection；unavailable interval；makespan

O223

A

10.3969／j.issn.1673-5862.2013.03.009

1673-5862（2013）03-0353-03

2012-09-18。

國家自然科學(xué)基金資助項目（61070242）。

劉 澈（1988-），女（滿族），遼寧鞍山人，沈陽師范大學(xué)碩士研究生；羅成新（1958-），男，遼寧新賓人，沈陽師范大學(xué)教授，博士，碩士研究生導(dǎo)師。