關于帶時間約束的單機排序的一個注記

萬紹春，張安*，陳永，陳光亭(. 杭州電子科技大學 理學院， 浙江 杭州 3008； . 臺州學院 數(shù)學與信息工程學院， 浙江 臺州37000)

關于帶時間約束的單機排序的一個注記

萬紹春1，張安1*，陳永1，陳光亭2
(1. 杭州電子科技大學 理學院， 浙江 杭州 310018； 2. 臺州學院 數(shù)學與信息工程學院， 浙江 臺州317000)

研究單機帶時間B-約束的排序問題，即在任意單位時間區(qū)間[x,x+1)內至多允許加工B個工件,目標函數(shù)是極小化工件的最大完工時間.分析了B=2時最優(yōu)排序的結構與性質，設計了O(nlogn)時間的啟發(fā)式算法. 當工件數(shù)較少(≤6)時，證明了該算法的最優(yōu)性.

單機排序；時間約束；最優(yōu)性；啟發(fā)式算法

0 引 言

最近，BRAUN等[1]提出了如下帶時間約束(time restrictions)的單機排序問題： 設有n個工件需在單臺機上加工，工件i的加工時間為pi≥0，其中加工時間為0的工件稱為零工件. 工件i可以在任意長度為pi的時間區(qū)間[α,α+pi)內加工并完成，其中α≥0為其開工時刻. 除零工件外，同一時刻至多允許1個工件在機器上加工. 同時，機器在加工過程中還需滿足時間B-約束，即在任意單位時間區(qū)間[x,x+1)內至多允許加工B個工件，其中B為給定正整數(shù).該問題可看作一類帶資源約束的排序新模型[2]，如機動車自動導引、醫(yī)院手術排程等[3-4]. BRAUN等[1]以極小化工件最大完工時間為目標函數(shù)，證明了當B為輸入值時問題是NP-難的；當B為常數(shù)時，對求解問題的LS算法進行了漸近最壞情況分析，特別是當B=2時證明了LS算法的漸近緊界為4/3. BRAUN等[5]分析得到LPT算法的漸近最壞情況界為2-2/B. ZHANG等[4]改進了上述結果，給出了B=2時的漸近最優(yōu)算法以及B≥5時的漸近緊界為5/4的改進算法.

BRAUN等[1]將B為常數(shù)情形的計算復雜性作為公開問題，ZHANG等[4]猜測B=2的情形屬于P問題(多項式時間可解問題).本文分析B=2時最優(yōu)排序的結構與最優(yōu)解的性質，并在此基礎上設計了一個時間復雜度為O(nlogn)的啟發(fā)式算法；當工件數(shù)較少(≤6)時，證明了該算法的最優(yōu)性.

1 最優(yōu)排序的結構與性質

假設工件的加工時間滿足p1≥p2≥…≥pn.為方便敘述，下文僅用加工時間表示對應工件. 由文獻[1,4]的結論，不妨假設p1≤1. 根據文獻[1]，一個可行排序可以用工件或其加工時間的排列π來表示，如π=(p[1],p[2],…,p[n]). 具體地，首先從0時刻開始加工工件p[1]，在加工第i個工件p[i]時，為滿足時間B-約束，其開工時間既不能早于p[i-2]的完工時間后一個單位時間，也不能早于p[i-1]的完工時間，每個工件都盡可能早開工，稱上述由排列產生可行排序的規(guī)則為LR規(guī)則. 類似地，可以從排列中最后一個工件自右向左產生可行排序，稱為RL規(guī)則. 從排列中任意一個工件向左右兩邊產生可行排序的規(guī)則，稱為M規(guī)則.根據時間約束的定義及上述規(guī)則，顯然有以下性質：

性質1對于給定排列，任意規(guī)則產生的可行排序的目標值都相等.

此外，由交換原理和排列兩端的對稱性，又能得到

性質2存在最優(yōu)排列，使得加工時間最小的工件pn，pn-1位于兩端.

證明由排列兩端的對稱性，僅需證明最小工件pn在最優(yōu)排列的前端，即第1個位置. 設有最優(yōu)排列

π*=(p[1],p[2],…,p[k-1],pn,p[k+1],…,p[n])，

其中pn位于第k(>1)個位置. 交換pn與p[1]的位置(如圖1所示)，由于pn

圖1 性質2證明中交換前后的排序Fig.1 Alternative schedules in the proof of property 2

性質3存在最優(yōu)排列，使得第2位置工件的加工時間不短于第3和第4位置工件的加工時間.

證明設有最優(yōu)排列π*=(pn,p[2],p[3],p[4],…,pn-1)，其中p[2]

圖2 性質3證明中交換第2,3位置工件前后的排序Fig.2 Schedules by swapping job 2 and 3 in the proof of property 3

由于p[3]+Δ≥1，p[2]+Δ=1,因此排序仍可行，且工件p[4]可在p[2]完工時刻開工，即排列在交換前后第3，4位置工件的完工時間不變，因此此后的工件完工時間也不變，即交換后的排列仍是最優(yōu)排列.

由以上證明，設有最優(yōu)排列π*=(pn,p[2],p[3],p[4],…,pn-1)，且p[3]≤p[2]

由性質3及排列兩端的對稱性，易得

性質4存在最優(yōu)排列，使得第n-1位置工件的加工時間不短于第n-2和n-3位置工件的加工時間.

圖3 性質3證明中交換第2，4位置工件前后的排序Fig.3 Schedules by swapping job 2 and 4 in the proof of property 3

2 基于最優(yōu)結構的啟發(fā)式算法

根據第1節(jié)對最優(yōu)排序結構的討論，設計如下啟發(fā)式算法:

算法W(1) 將工件按加工時間從大到小排序，即p1≥p2≥…≥pn；(2) 生成排列π=(pn,p1,p3,…,p4,p2,pn-1)，并按照M規(guī)則產生可行排序.

由于算法的第1步需要對n個工件進行排序，所以其時間復雜性是O(nlogn).

定理1當工件數(shù)n≤6時，算法W給出的是最優(yōu)排序.

證明當n≤4時，由性質2及排列的兩端對稱性，算法W給出的排列顯然最優(yōu).

當n=5時，由性質2至性質4，加工時間最少的工件p5,p4在最優(yōu)排列的兩端，而排在第2位置的工件加工時長長于第3，4位置的工件，排在倒數(shù)第2即第4位置的工件加工時長長于第3位置的工件，由此可知，算法W所給的排列(p5,p1,p3,p2,p4)滿足上述特征，因此是最優(yōu)的.

當n=6時，由性質2至性質4及上述類似分析，最優(yōu)排序必為(p6,p1,p3,p4,p2,p5)和(p6,p1,p4,p3,p2,p5)之一.前者為算法W給出的排列，記為πW，后者記為π，按照M規(guī)則產生對應的排序如圖4所示.

圖4 由M規(guī)則產生的πW與π對應排序Fig.4 Schedules of πW and π generated by the M rule

在πW與π中，顯然第2，3位置工件之間的空閑時長相等，第4，5位置工件之間的空閑時長也相等，且滿足Δ1+p1=1，Δ2+p2=1. 令πW與π中第3，4位置工件之間的空閑時長分別為ΔW和Δ，則根據M規(guī)則有：

Δ1+p3+ΔW≥1，Δ2+p4+ΔW≥1，ΔW≥0.

(1)

Δ1+p4+Δ≥1，Δ2+p3+Δ≥1，ΔW≥0.

(2)

由于按照M規(guī)則，空閑時間只能由滿足時間約束產生，結合式(1)，(2)，就有

ΔW= max{1-Δ1-p3,1-Δ2-p4,0}=

max{p1-p3,p2-p4,0}，

Δ= max{1-Δ1-p4,1-Δ2-p3,0}=

max{p1-p4,p2-p3,0}.

注意到p1-p3≤p1-p4，p2-p4≤p1-p4,所以ΔW≤Δ. 從而πW產生的總空閑時長不超過π產生的總空閑時長，故πW是最優(yōu)的.

文獻[4]已證明排列(pn,p1,p2,p3,…,pn-1)是漸近最優(yōu)的，對比該排列與算法W所給出的排列，并經過類似分析不難得到以下結論：

所以當n≥7時，算法W是漸近最優(yōu)的. 然而即使當n=7時，算法W也不是最優(yōu)的.

實例說明見表1.

表1 n=7的實例Table 1 Instance with n=7

3 結束語

研究了單機帶時間B-約束的排序問題，分析了B=2時最優(yōu)排序的性質并設計了啟發(fā)式算法W，證明算法在工件數(shù)n≤6時是最優(yōu)的.當n≥7時，算法W是漸近最優(yōu)的，但當n=7時，算法也非絕對最優(yōu)，因此猜想B=2時帶時間約束的單機排序可能是NP-難的，未來研究方向是設法給出該問題的計算復雜性證明.

[1] BRAUN O, CHUNG F, GRAHAM R. Single-processor scheduling with time restrictions[J].JournalofScheduling, 2014, 17： 399-403.

[2] LEUNG J.HandbookofScheduling[M]. Boca Raton： Chapman and Hall, 2004.

[3] EDIS P, OGUZ C, OZKARAHAN I. Parallel machine scheduling with additional resources： Notation, classification, models and solution methods[J].EuropeanJournalofOperationalResearch, 2013, 230： 449-463.

[4] ZHANG A, YE F, CHEN Y,et al. Better permutations for the single-processor scheduling with time restrictions[J].OptimizationLetters, 2017, 11： 715-724.

[5] BRAUN O, CHUNG F, GRAHAM R. Worst-case analysis of the LPT algorithm for single processor scheduling with time restrictions[J].ORSpectrum, 2016, 38： 531-540.

WAN Shaochun1, ZHANG An1, CHEN Yong1, CHEN Guangting2
(1.SchoolofSciences，HangzhouDianziUniversity，Hangzhou310018，China；2.SchoolofMathematics&InformationEngineering，TaizhouUniversity，Taizhou317000，ZhejiangProvince,China)

This paper studies single processor scheduling with time restrictions ofB-constraint, which means that no unit time interval [x,x+1) can be allocated to more thanBjobs for any realx≥0. By analyzing the structure and properties of optimal schedules forB=2, a heuristic algorithm with running time O(nlogn) is presented. For a small number (≤6) of jobs, it is proved that the algorithm is optimal.

single processor scheduling; time restrictions; optimality; heuristic algorithm

2016-10-24.

國家自然科學基金資助項目(11771114,11571252,11401149)；浙江省自然科學基金資助項目(LY16A010015).

萬紹春(1995—)，ORCID： http： //orcid.org/0000-0002-9337-4460，男，本科，主要從事應用數(shù)學研究.

*通信作者，ORCID： http： //orcid.org/0000-0002-2622-5158，E-mail： anzhang@hdu.edu.cn.

10.3785/j.issn.1008-9497.2018.01.003

O 224

A

1008-9497(2018)01-014-04

Anoteonsingleprocessorschedulingwithtimerestrictions. Journal of Zhejiang University (Science Edition)，2018，45(1)： 014-017