張浩楠，羅成新

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

基礎(chǔ)科學(xué)與工程

加工時間依賴與位置有關(guān)的負荷和資源的工期指派問題

張浩楠，羅成新

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

討論了帶有公共工期且加工時間依賴與有關(guān)的位置負荷和資源的單機排序問題。工件的加工時間是一個和資源分配、工件在排序中的位置以及負荷有關(guān)的凸函數(shù)，所有任務(wù)具有一個公共工期。目標(biāo)是確定最優(yōu)工期的位置、分配給每個工件的資源和最優(yōu)的工件排序，使由提前、誤工、工期、資源分配構(gòu)成的總費用最小化。應(yīng)用指派問題解法給出了時間復(fù)雜度為O(n3)的最優(yōu)算法。

單機排序；資源分配；可控加工時間；依賴位置的負荷；工期

近年來，帶有資源分配和工期指派的單機排序問題倍受關(guān)注。在傳統(tǒng)的排序問題中，工件的加工時間是一個常數(shù)。然而在實際環(huán)境中，工件的加工時間可能是一個和資源分配、工件在排序中位置有關(guān)的函數(shù)，由此產(chǎn)生一些新型排序問題。Wang D等[1]考慮了帶有資源分配和學(xué)習(xí)效應(yīng)的單機排序問題并給出多項式算法。Lu Y-Y等[2]研究了帶有資源分配的單機排序問題。王吉波等[3]考慮了具有惡化工件的不同工期指派問題，證明該問題的算法復(fù)雜性是多項式時間可解的，并給出了如何求解該問題的最優(yōu)算法。Wang J-B等[4]研究了帶有公共工期、資源分配以及學(xué)習(xí)效應(yīng)的單機指派問題。郭玲等[5]討論了帶有公共交貨期窗口和工件的加工時間可控的單機排序問題，給出了最優(yōu)解的一些性質(zhì)，并且證明了這個問題是多項式時間可解的。Mosheiov G[6]研究了帶有學(xué)習(xí)效應(yīng)的排序問題。王洪芳等[7]研究單機排序下加工時間可變的工期窗口指派問題,任務(wù)的加工時間是關(guān)于所獲資源分配量的一個凸函數(shù)，證明了此問題是多項式時間可解的,并給出了最優(yōu)算法。He H等[8]研究了帶有資源約束和標(biāo)準(zhǔn)截斷學(xué)習(xí)效應(yīng)的排序問題。Ng CT等[9]考慮了帶有幾種公共工期和資源分配的單機排序問題。王吉波等[10]研究了具有學(xué)習(xí)效應(yīng)的單機可控加工時間排序問題，其中工件的加工時間是其所在位置的函數(shù)，且與加工時間的控制變量有關(guān)，并證明他們都能轉(zhuǎn)化為指派問題，從而多項式時間可解。此外，Seidmann A等[11]研究了工期指派的排序問題。Gordon V等[12]考慮了公共工期指派的單機排序問題。Shabtay D等[13]研究了可控加工時間的排序問題。

上述文獻大多數(shù)沒有提到負荷，負荷是與工件本身及位置有關(guān)的參數(shù)，而工件的加工時間是一個和負荷有關(guān)的凸函數(shù)，但關(guān)于負荷的排序問題的研究很少。Oron D[14]考慮了可控加工時間與位置有關(guān)負荷的單機排序問題，他所假定的模型中不含有工件的工期。然而在實際的生產(chǎn)過程中，顧客需要在一定時間內(nèi)獲得產(chǎn)品，沒有按時完成或提前完成可能會產(chǎn)生一定的費用，這樣就產(chǎn)生了帶有工期指派的排序問題。本文考慮的是加工時間依賴與位置有關(guān)的負荷、資源的工期指派的單機排序問題。所有任務(wù)具有一個公共工期(是決策變量)。目標(biāo)是確定最優(yōu)工期的位置、分配給每個工件的資源和最優(yōu)的工件排序，使由提前、誤工、工期、資源分配構(gòu)成的總費用最小化。應(yīng)用指派問題解法給出了時間復(fù)雜度為O(n3)的最優(yōu)算法。

1 問題描述

設(shè)有n個獨立的工件J={J1,J2,…,Jn}在一臺機器上加工，所有的工件在零時刻都已到達，且加工不可中斷，機器在每個時刻至多加工一個工件。假設(shè)當(dāng)工件Jj排第r個位置上加工時，它的實際加工時間為

其中參數(shù)wjr是與工件本身及位置有關(guān)的任務(wù)負荷，h>0，uj為分配給Jj的資源，工件Jj的資源uj的單位費用為vj，所有工件有一個公共工期d。工件Jj的提前和誤工分別為Ej=max{0,d-Cj}和Tj={0,Cj-d}，其中Cj表示工件Jj的完工時間。給定每個工件一個固定的資源，那么相應(yīng)地它的加工時間也被確定，因此目標(biāo)是確定工期d的最優(yōu)位置，分配給每個工件的資源u*={u1,u2,…,un}和最優(yōu)的工件排序，使得下面的目標(biāo)函數(shù)最小。

其中α>0,β>0,δ>0,vj>0是給定的常數(shù)，分別表示提前、誤工、工期和資源的單位費用。

本文考慮的是有公共工期的單機排序問題。利用三參數(shù)表示法(Graham R L,Lawler E L, Lenstra J K，et al[15])，此排序問題可記為

2 初步分析

引理1 任意給定一個排序π，存在最優(yōu)的工期d與某一個工件的完工時間是一致的。

證明 設(shè)給定的任務(wù)排序，π=[J[1],J[2],…,J[n]]

設(shè)C[k-1]

其中

A=[α(k-1)-β(n-k+1)+nδ]

A,B與Δ無關(guān)，為使得目標(biāo)函數(shù)Z最小，則當(dāng)A≥0時，取Δ=0；當(dāng)A<0時，取Δ=p[k]k(u[k])。工期d與某一個工件的完工時間是一致的。引理1證畢。

證明 由引理1我們知道最優(yōu)的工期d與某一個工件的完工時間是一致的，令這一工件的角標(biāo)為J[k]，其中1≤k≤n，其相應(yīng)的最優(yōu)的目標(biāo)函數(shù)為f(C[k],π)。

對任意有σ>0，有f(C[k]+σ)-f(C[k],π)≥0。工期由C[k]變?yōu)镃[k]+σ，工期和提前的費用至少增加σ(nδ+kα)，誤工的費用減少了σ(n-k)β。

3 排序問題的最優(yōu)解

由引理1、引理2可知工期d*=C[k]被確定。所以，提前完工的工件為J[1],J[2],…,J[k-1]，誤工的工件為J[k+1],J[k+2],…,J[n]。

u[r]*=

(1)

證明

(2)

將式(2)對u[r]求偏導(dǎo)：

將最優(yōu)資源表達式(1)帶入目標(biāo)函數(shù),可得

令xjr為0/1變量，當(dāng)工件Jj排在第r個位置加工時xjr=1，否則xjr=0。問題可以由以下指派問題求解。

(3)

(4)

(5)

xjr∈{0 , 1}j,r=1,2,…,n

(6)

(7)

其中j=1,2,…,n，基于上述分析，給出下述最優(yōu)算法。

算法1

第一步：輸入α,β,δ,vj,h,n,wjr；

第三步：求解指派問題式(3)-式(6)得到最優(yōu)任務(wù)排序。π*=[J[1],J[2],…,J[n]]；

第五步：求出d*=C[k]，再由(2)計算最優(yōu)目標(biāo)函數(shù)值。

定理1 算法1可在O(n3)內(nèi)求出問題1

表1 例1中wjr的值

表2 例1中λjr的值

4 結(jié)論

本文考慮的是加工時間依賴與位置有關(guān)的負荷、資源的工期指派的單機排序問題。所有任務(wù)具有一個公共工期，目標(biāo)是確定最優(yōu)工期的位置、分配給每個工件的資源和最優(yōu)的工件排序，使由提前、誤工、工期、資源分配構(gòu)成的總費用最小化。應(yīng)用指派問題解法給出了時間復(fù)雜度為的最優(yōu)算法。

[1]WANG D,WANG M-Z,WANG J-B.Single-machine scheduling with learning effect and resource-dependent processing times[J].Computers & Industrial Engineering,2010,59(3):458-462.

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

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

[4]WANG J-B,WANG M-Z.Single-machine due-window assignment and scheduling with learning effect and resource-dependent processing times[J].Asia Pacific Journal of Operational Research,2014,31(5):1450036-1-1450036-15.

[5]郭玲,趙傳立.帶有公共交貨期窗口和加工時間可控的單機排序問題[J].重慶師范大學(xué)學(xué)報:自然科學(xué)版,2012,29(6):9-14.

[6]MOSHEIOV G.Scheduling problems with a learning effect[J].European Journal of Operational Research,2001,132(3):687-693.

[7]王洪芳,羅成新.資源約束下加工時間可變的工期窗口指派問題[J].沈陽師范大學(xué)學(xué)報(自然科學(xué)版),2015,33(4):482-487.

[8]HE H,LIU M,WANG J-B.Resource constrained scheduling with general truncated job-dependent learning effect[J].Journal of Combinatorial Optimization,December,2015:1-19.

[9]NG CT,CHENG TCE,KOVALYOV MY,et al.Single machine scheduling with a variable common due date and resource-dependent processing times[J].Computers & Operations Research,2003,30(8):1173-1185.

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

[11]SEIDMANN A,PANWALKAR S S,SMITH M L.Optimal assignment of due-dates for a single processor scheduling problem[J].International Journal of Production Research,2010,19(4):393-399.

[12]GORDON V,PROTH J M,CHU C.A survey of the state-of-the-art of common due date assignment and scheduling research[J].European Journal of Operational Research,2002,139(1):1-25.

[13]SHABTAY D,STEINER G.A survey of scheduling with controllable processing times[J].Discrete Applied Mathematics,2007,155(13):1643-1666.

[14]ORON D.Scheduling controllable processing time jobs with position-dependent workloads[J].International Journal of Production Economics,2015,173:153-160.

[15]GRAHAM RL,LAWLER EL,LENSTRA JK,et.al.Optimization and approximation in deterministic sequencing and scheduling.a survey[J].Ann Discret Math,1979,5(1):287-326

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

Due-date assignment problem with position-dependent workload and resource processing times

ZHANG Hao-nan,LUO Cheng-xin

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

We consider a common due-date assignment and single machine scheduling problem in which job processing time has position-dependent workload.Under the condition that the processing time of a job is a convex function of the amount of a resource allocated to it and its position in the processing sequence and workload,all jobs have a common due-date.The objective is to find the optimal due-date,the optimal resource allocation scheme and the optimal job sequence to minimize the total cost,which involves earliness,tardiness,due-date,and resource consumption.We proposed an efficientO(n3) algorithm to solve this assignment problem.

single machine scheduling;resource allocation;controllable processing times;position-dependent workload;due-date

2016-10-24

國家自然科學(xué)基金(項目編號：11171050)；遼寧省教育廳項目(項目編號：L2014433)

張浩楠(1993-),女,遼寧錦州人,碩士研究生，主要研究方向：組合最優(yōu)化,E-mail:zhnagnes@foxmail.com；羅成新,(1958-),男,遼寧新賓人,教授，主要研究方向：組合最優(yōu)化，E-mail:luochengxin@163.com。

2095-1248(2017)01-0091-06

O223

A

10.3969/j.issn.2095-1248.2017.01.014