隋 楠，羅成新

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

具有維護活動及公共工期的加工時間依賴資源的單機排序問題

隋 楠，羅成新

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

研究在工件的提前懲罰、延誤懲罰等總費用受限的前提下，最小化資源費用的單機排序問題。所有工件具有一個公共工期，工件的加工時間是關(guān)于位置與資源的具有退化效應(yīng)的凸函數(shù)。在加工過程中，存在一次維護活動。考慮維護活動對依賴于資源的加工時間的影響，確定最優(yōu)資源分配、最優(yōu)公共工期、最優(yōu)維護位置及維護持續(xù)時間，并給出一個求得最小資源費用的多項式時間最優(yōu)算法。

排序；維護活動；工期；資源分配；退化效應(yīng)

排序問題是一類重要的組合最優(yōu)化問題，多年來人們一直在運籌學(xué)、計算機科學(xué)、管理科學(xué)等領(lǐng)域進行著該問題的研究。在經(jīng)典排序模型中，工件的加工時間是一個獨立的且與加工位置和資源無關(guān)的常數(shù)，但在實際問題中，工件的加工時間可能會在機器的維護作用下相應(yīng)縮短，或者通過適當(dāng)?shù)胤峙浣o工件一定的資源，使其加工效率提高，加工時間縮短。

近20年，由于現(xiàn)代運營管理等產(chǎn)業(yè)的引進，具有公共工期的排序問題陸續(xù)進入人們的視野。如果一個工件在它的工期之前完成加工，那么它需要承擔(dān)一部分的提前懲罰費用，相應(yīng)的，如果一個工件在它的工期之后完成加工，那么它需要承擔(dān)一部分的延誤懲罰費用。文獻(xiàn)[6]首先研究了帶有公共工期的排序問題，目標(biāo)是最小化提前懲罰、延誤懲罰和工期的總費用。自此之后，在不同環(huán)境下的帶有公共工期的排序問題被陸續(xù)研究著。

文獻(xiàn)[4]首先研究了帶有退化效應(yīng)的排序問題。由于實際生產(chǎn)的需要，維護問題越來越受重視。為了更好地提高機器的運行效率，需要對機器進行維護，使機器恢復(fù)到初始狀態(tài)或者提高機器的生產(chǎn)效率，文獻(xiàn)[13]研究了具有固定維護時間的單機排序問題，給出了多項式算法。在研究具有維護活動的排序問題中，維護活動持續(xù)的時間都是固定的常數(shù)，但在實際生產(chǎn)過程中，維護活動持續(xù)的時間受到多種因素影響，通常假定為關(guān)于維護活動開始時間的線性函數(shù)。文獻(xiàn)[2]和[5]研究了具有公共工期和維護活動的單機排序問題。

經(jīng)典排序模型中，任務(wù)的加工時間通常都是固定的常數(shù)，然而考慮到學(xué)習(xí)效應(yīng)、退化效應(yīng)、資源分配等情況，任務(wù)的加工時間不再是固定不變的。文獻(xiàn)[7]和[8]研究了不同環(huán)境下的具有維護活動的單機排序問題。由于實際生產(chǎn)活動的需要，帶有資源分配的問題逐漸引起關(guān)注，文獻(xiàn)[3]、[10]和[11]研究了關(guān)于資源分配的單機排序問題。

在大多排序模型中，往往以最小化所需費用為首要目標(biāo)。但實際生產(chǎn)過程中，有時即便使得總費用最小，也不能滿足生產(chǎn)者對費用的預(yù)估最小值。因此生產(chǎn)者常常會事先給定預(yù)算以限制總費用。文獻(xiàn)[11]研究了多種工期下資源受限的單機排序問題，并給出了在總費用受限的前提下資源總數(shù)的最優(yōu)算法。因此，本文在文獻(xiàn)[11]的基礎(chǔ)上，研究了帶有公共工期和維護活動的總費用受限的單機排序問題,工件的加工時間是關(guān)于位置與資源的具有退化效應(yīng)的凸函數(shù)，并給出了最優(yōu)算法，該算法通過求解指派問題在O(n4)時間內(nèi)求得最優(yōu)資源分配、最優(yōu)公共工期、最優(yōu)維護位置及維護持續(xù)時間及最小資源費用。

1 問題(1)描述

(1)在維修活動之后，機器恢復(fù)到初始狀態(tài)，退化影響也重新計算；

(2)機器維修的持續(xù)時間是關(guān)于開始時間的線性函數(shù)，表示為f(t)=x+yt，其中x>0，y≥0為常數(shù)，分別為基本維護時間和維護退化因子，t為維修開始時間；

(3)i為維修活動前的最后一個工件，即維修活動后的第一個工件表示為i+1，其中i∈{1,2,…,n}。

其中α>0、β>0、γ>0、θ≥0、δ≥0為給定常數(shù)，vj(>0)為資源分配的單位費用。用三參數(shù)表示法[9]如式(1)所示。

(1)

其中Q>max{nx(γ+max{α,δ}),(β+δ)nx}為已知常數(shù)。

2 問題的最優(yōu)解

2.1 重要結(jié)論

引理1 存在最優(yōu)排序，任務(wù)開始加工時間為0,且兩個相鄰工件之間無空閑時間。

證明 詳細(xì)證明見參考文獻(xiàn)[6]。

證明 詳細(xì)證明與參考文獻(xiàn)[2]中證明類似。證畢。

2.2 最優(yōu)算法

若維修活動在工期前，即當(dāng)1≤i≤m時：

從而

(2)

(3)

j=1,2,…,n

(4)

其中

(5)

(6)

對于任意給定排序，拉格朗日函數(shù)如式(7)所示。

(7)

其中λ為拉格朗日乘數(shù)。對(7)式中的變量分別求偏導(dǎo)，如式(8)和式(9)所示。

(8)

(9)

由式(8)和式(9)可得

(10)

(11)

由式(10)和式(11)可得式(4)，證畢。

(12)

為了求出式(12)的最小值，考慮指派問題如下：

則問題轉(zhuǎn)化為如下指派問題：

(13)

(14)

(15)

yjr=1或0 j,r=1,2,…,n

(16)

若維修活動在工期后，即當(dāng)m

此時，可以得到約束條件如下:

(17)

j=1,2,…,n

(18)

其中

(19)

對于任意給定排序，拉格朗日函數(shù)如式(20)所示。

(20)

其中λ為拉格朗日乘數(shù)。對式(20)中的變量分別求偏導(dǎo)，得到

(21)

(22)

由式(21)和式(22)可得

(23)

(24)

由式(23)和式(24)可得式(18)，證畢。

Z(π,d,u*)

(25)

為了求出式(25)的最小值，考慮指派問題如下：

則問題轉(zhuǎn)化為如下指派問題：

(26)

(27)

(28)

yjr=1或0 j,r=1,2,…,n

(29)

證明 每個指派問題可以在O(n3)時間內(nèi)求得最優(yōu)解，而維修的位置可取1,2,…,n，共n種情況，結(jié)論得證。

表1 例1的數(shù)據(jù)

表2 例1中ci′值

3 結(jié)論

本文研究了具有維護活動及公共工期，且加工時間依賴于資源的單機排序問題。加工時間是關(guān)于資源的凸函數(shù)，維護活動有且僅有一次，在部分總費用受限的前提下，給出了一個最優(yōu)算法求解最優(yōu)資源費用、最優(yōu)資源分配及最優(yōu)工期。

[1]CHENG T C E.Optimal single machine sequencing and assignment of common due-date[J].Computers and Industrial Engineering,1992,22:115-120.

[2]YANG S J,HSU C J,YANG D L.Single-machine scheduling with due-date assignment and aging effect under a deteriorating maintenance activity consideration[J].International Journal of Information and Management Sciences,2010,21:177-195.

[3]LU Y Y,LI G,WU B P.JI.Optimal due-date assignment problem with learning effect and resource-dependent processing times[J].Optimization Letters 2014,8(1):113-127.

[4]LEE W C.A note on deteriorating jobs and learning in single machine scheduling problems[J].Int J Business Econ,2004,3(1):83-89.

[5]MOSHEIOV G,ORON D.Due-date assignment and maintenance activity scheduling problem[J].Mathematical and Computer Modeling,2006,44(11-12):1053-1057.

[6]PANWALKAR S S,SMITH M L,SEIDMANN A.Common due date assignment to minimize total penalty for the one machine scheduling problem[J].Operations Research,1982,30(2):391-399.

[7]YAO M J,HUANG J Y.A global-optimization algorithm for solving the maintenance scheduling problem for a family of machines[J].International Journal of Information and Management Sciences,2007,18(4):365-386.

[8]MOSHEIOV G,SARIG A.Scheduling a maintenance activity to minimize total weighted completion time[J].Computer and Mathematics with Application,2009,57:619-623.

[9]GRAHAM R L,LAWLER E L,LENSTRA J K,et al.Optimization and approximation in deterministic sequencing and scheduling[J].A survey,Annals of Discrete Mathematics,1979,5(1):287-326.

[10]WANG X Y,WANG J J.Single-machine due-date assignment problem with deteriorating jobs and resource-dependent processing times[J].International Journal of Advanced Manufacturing Technology,2013,67(1):255-260.

[11]WANG J B,WANG J J.Research on scheduling with job-dependent learning effect and convex resource-dependent processing times[J].International Journal of Production Research,2015,53(19):1-11.

[12]MOSHEIOV G,SIDNEY J B.Scheduling a deteriorating maintenance activity on a single machine[J].Journal of the Operational Research Society,2010,61(5):882-887.

[13]MPSJEOPV G,SARIG A.Scheduling a maintenance activity and due-window assignment on a single Machine[J].Computers&Operations Research,2009,36(9):2541-2545.

[14]WAN G.Single machine common due window scheduling with controllable job processing times[J].Lecture Notes in Computer Science,2007,4616:279-290.

[15]王吉波，郭苗苗，劉桓，等.具有依賴開工時間惡化工件的流水作業(yè)排序問題研究綜述[J].沈陽航空航天大學(xué)學(xué)報 2016,33(3):1-10.

[16]王吉波，劉璐，許揚濤，等.具有惡化工件的不同工期指派問題研究[J].沈 陽航空航天大學(xué)學(xué)報，2013,30(5):83-87.

[17]王吉波，汪佳，牛玉萍.具有學(xué)習(xí)效應(yīng) 的單機可控加工時間排序問題研究[J].沈陽航空航天大學(xué)學(xué)報，2014,31(5):82-86.

(責(zé)任編輯：劉劃 英文審校：劉勇進)

Single machine scheduling with job-dependent and maintenance activities and processing time dependent on resources with due-date

SUI Nan,LUO Cheng-xin

(School of Mathematics and Systems Science,Shenyang Normal University,Shenyang 110034，China)

In this paper,we study the single machine scheduling problem of minimizing resource costs under the conditions that the earliness,tardiness and other penalties are limited.All the jobs have a common due-date,and the actual processing times are defined by a convex function of their normal processing times,positions and the effect index of deteriorating and resources.There is a maintenance activity in the processing.Considering the effect on the processing time of resource from maintenance,we give the optimal resource allocation,the optimal due-date,the optimal place for maintenance and the lasting time of maintenance.An optimal polynomial time algorithm for the minimum resource cost is given.

scheduling;maintenance activities;due-date;resource allocation;deteriorating effect

2016-10-28

隋 楠(1992-)，女，遼寧鐵嶺人，碩士研究生，主要研究方向：組合最優(yōu)化與隨機運籌學(xué),E-mail：nannan879@126.com。

2095-1248(2016)06-0090-07

O223

A

10.3969/j.issn.2095-1248.2016.06.015