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

關(guān)于帶時(shí)間約束的單機(jī)排序的一個(gè)注記

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

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

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

0 引 言

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

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

1 最優(yōu)排序的結(jié)構(gòu)與性質(zhì)

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

性質(zhì)1對(duì)于給定排列，任意規(guī)則產(chǎn)生的可行排序的目標(biāo)值都相等.

此外，由交換原理和排列兩端的對(duì)稱(chēng)性，又能得到

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

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

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

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

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

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

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

圖2 性質(zhì)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]完工時(shí)刻開(kāi)工，即排列在交換前后第3，4位置工件的完工時(shí)間不變，因此此后的工件完工時(shí)間也不變，即交換后的排列仍是最優(yōu)排列.

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

由性質(zhì)3及排列兩端的對(duì)稱(chēng)性，易得

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

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

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

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

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

由于算法的第1步需要對(duì)n個(gè)工件進(jìn)行排序，所以其時(shí)間復(fù)雜性是O(nlogn).

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

證明當(dāng)n≤4時(shí)，由性質(zhì)2及排列的兩端對(duì)稱(chēng)性，算法W給出的排列顯然最優(yōu).

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

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

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

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

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

(1)

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

(2)

由于按照M規(guī)則，空閑時(shí)間只能由滿(mǎn)足時(shí)間約束產(chǎn)生，結(jié)合式(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產(chǎn)生的總空閑時(shí)長(zhǎng)不超過(guò)π產(chǎn)生的總空閑時(shí)長(zhǎng)，故πW是最優(yōu)的.

文獻(xiàn)[4]已證明排列(pn,p1,p2,p3,…,pn-1)是漸近最優(yōu)的，對(duì)比該排列與算法W所給出的排列，并經(jīng)過(guò)類(lèi)似分析不難得到以下結(jié)論：

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

實(shí)例說(shuō)明見(jiàn)表1.

表1 n=7的實(shí)例Table 1 Instance with n=7

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

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

[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.

國(guó)家自然科學(xué)基金資助項(xiàng)目(11771114,11571252,11401149)；浙江省自然科學(xué)基金資助項(xiàng)目(LY16A010015).

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

*通信作者，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