張浩楠，羅成新

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

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

加工時(shí)間依賴(lài)與位置有關(guān)的負(fù)荷和資源的工期指派問(wèn)題

張浩楠，羅成新

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

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

單機(jī)排序；資源分配；可控加工時(shí)間；依賴(lài)位置的負(fù)荷；工期

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

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

1 問(wèn)題描述

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

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

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

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

2 初步分析

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

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

設(shè)C[k-1]

其中

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

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

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

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

3 排序問(wèn)題的最優(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)對(duì)u[r]求偏導(dǎo)：

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

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

(3)

(4)

(5)

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

(6)

(7)

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

算法1

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

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

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

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

表1 例1中wjr的值

表2 例1中λjr的值

4 結(jié)論

本文考慮的是加工時(shí)間依賴(lài)與位置有關(guān)的負(fù)荷、資源的工期指派的單機(jī)排序問(wèn)題。所有任務(wù)具有一個(gè)公共工期，目標(biāo)是確定最優(yōu)工期的位置、分配給每個(gè)工件的資源和最優(yōu)的工件排序，使由提前、誤工、工期、資源分配構(gòu)成的總費(fèi)用最小化。應(yīng)用指派問(wèn)題解法給出了時(shí)間復(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]王吉波，劉璐，許揚(yáng)濤，等.具有惡化工件的不同工期指派問(wèn)題研究[J].沈陽(yáng)航空航天大學(xué)學(xué)報(bào)，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]郭玲,趙傳立.帶有公共交貨期窗口和加工時(shí)間可控的單機(jī)排序問(wèn)題[J].重慶師范大學(xué)學(xué)報(bào):自然科學(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]王洪芳,羅成新.資源約束下加工時(shí)間可變的工期窗口指派問(wèn)題[J].沈陽(yáng)師范大學(xué)學(xué)報(bào)(自然科學(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ī)可控加工時(shí)間排序問(wèn)題研究[J].沈陽(yáng)航空航天大學(xué)學(xué)報(bào),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é)任編輯：劉劃 英文審校：劉勇進(jìn))

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

國(guó)家自然科學(xué)基金(項(xiàng)目編號(hào)：11171050)；遼寧省教育廳項(xiàng)目(項(xiàng)目編號(hào)：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