趙崴羽，羅成新

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

?

具有公共流、退化效應與維護和資源分配的單機窗口排序問題

趙崴羽，羅成新

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

考慮具有公共流、退化效應與維護和資源分配的單機窗口排序問題，所有任務都具有松弛窗口。在實際加工過程中，為提高生產(chǎn)效率，提供給每個任務不同的資源，資源總量有限，并適時對機器進行維護，一旦維護活動結束，機器恢復到最初狀態(tài)并且任務的退化效應更新。機器維護持續(xù)的時間取決于維護活動的開始時間。假定任務的實際加工時間是關于任務排序位置及資源分配的凸函數(shù)，目標是確定任務的窗口、資源分配、任務排序使得提前懲罰、延誤懲罰、窗口位置、窗口寬度、時間表長、任務完工時間之和懲罰及資源消耗費用之和最小。給出一個最優(yōu)算法求解該問題。

排序；退化效應；退化維護；資源分配；窗口；公共流

經(jīng)典排序中，任務的加工時間是固定的常數(shù)，但在實際生產(chǎn)中，任務等待或機器等原因都會引起任務加工時間的增長，即任務的實際加工時間與該任務的開始加工時間有關[1]，因此，適時地對機器進行檢修能提高機器的生產(chǎn)效率。通常情況下，給任務分配一定額度資源，任務的加工時間變小。任務獲得的資源與其加工時間成反比[2-5]。

由于準時生產(chǎn)概念的出現(xiàn)，具有工期的排序問題引起廣泛關注。工期問題包括所有任務共用一個工期(CON)、不同的任務具有不同的工期(DIF)、不同的任務具有不同的松弛工期(SLK)等。Mosheiov和Oron將具有公共流的松弛工期問題推廣到具有公共流的松弛窗口問題。不同的任務具有不同的窗口，但所有窗口的長度相同，每個任務窗口的開始時間和結束時間分別等于任務的實際加工時間加上公共流和。如果任務在窗口之前加工完成會引起提前懲罰，如果任務在窗口之后加工完成將導致延誤懲罰，只有任務在窗口內(nèi)加工完成才不會引起懲罰。根據(jù)準時生產(chǎn)理論，任務的提前完成或者延誤完成都是不被鼓勵的。文獻[4]研究具有公共流q1和q2可控加工時間的單機窗口問題，文獻[5]研究了具有公共流、學習效應和資源分配的單機窗口排序問題，目標是得到最優(yōu)公共流、最優(yōu)窗口長度、最優(yōu)資源分配和最優(yōu)排序使得提前懲罰費用、延誤懲罰費用、窗口的開始時間和長度費用、時間表長和加權資源費用之和最小。文獻[6]研究帶有凸資源加工時間模型的排序問題，目標是得到最優(yōu)排序和資源分配使得提前懲罰費用、延誤懲罰費用和窗口開始時間費用之和最小。

本文將文獻[5]研究的問題拓展到具有維護活動和資源約束的環(huán)境下，考慮具有公共流、退化效應與維護和資源分配的單機窗口排序問題，目標是確定最優(yōu)公共流、最優(yōu)窗口長度、最優(yōu)資源分配、最優(yōu)維護位置、最優(yōu)排序使得提前懲罰、延誤懲罰、窗口位置、窗口寬度、時間表長、任務完工時間之后懲罰及資源消耗費用之和最小，并給出了多項式時間算法。

1 問題描述

給定n個獨立任務J={J1,J2,…,Jn}，在零時刻已全部到達，所有任務加工不可中斷，在一臺機器上進行加工?？紤]凸函數(shù)模型：

(1)

(2)

2 預備知識

顯而易見，最優(yōu)排序π*中，第一個任務從零時刻開始加工，在兩個相鄰的加工任務中間無空閑時間。

引理 3 任意給定排序π及資源u=(u1,…,un)，存在最優(yōu)的q1、q2分別為第k個、第l個任務的完工時間(l≥k)，即q1=p[1]+…+p[k]，q2=p[1]+…+p[k]+…+p[l]。

證明 與文獻[13]中證明相似，證完。

引理 4 在最優(yōu)排序中，q1=C[k]，k=?n(δ-γ)/α」；q2=C[l]，l=?n(β-δ)/β」；這里?x」表示不大于x的最大整數(shù)。

3 最優(yōu)解

當維護活動在第k個任務之前的某一位置進行，1≤i≤k，由引理3和引理4，得到

當維護活動在第k個任務與第l個任務之間的某一位置進行，k

當維護活動在第l個任務之后的某一位置進行，l≤i≤n，得到

當1≤i≤k時，記W=αib+γnb+ηb+λ(n-i)b，

(3)

當k

(4)

當l≤i≤n時，記W=β(n-i)b+ηb+λ(n-i)b，

(5)

(6)

φ為拉格朗日乘子。求上式關于變量(u[j],φ)的一階偏導數(shù)，令其為零有

(7)

(8)

(9)

(11)

(12)

通過(7)、(10)、(11)和(12)，得到最優(yōu)資源分配為

(13)

將(13)帶入到目標函數(shù)Z中，得到

(14)

為了得到所求問題的最優(yōu)排序，將所求問題轉(zhuǎn)化為指派問題，令yjr為0/1變量，當任務Jj排在第r個位置上加工時，yjr=1，否則，yjr=0。指派問題如下

算法1

第一步 通過引理4，計算q1和q2的最優(yōu)位置。

第三步 由(13)計算最優(yōu)資源分配，由(1)計算最優(yōu)加工時間。

定理1 利用算法1該排序問題可在O(n4)時間內(nèi)求出最優(yōu)解。

證明 上述分析保證了結論的正確性。第一步、第三步和第四步均可在O(1)時間內(nèi)求解，第二步可在O(n3)時間內(nèi)求解，維護位置i固定后，該排序問題轉(zhuǎn)化為指派問題求解，故該排序問題可在O(n3)時間內(nèi)求解該問題。維護可以在n個位置上進行，因此該問題可在O(n4)時間內(nèi)可解。證完。

4 實例

某次生產(chǎn)中有3個任務待加工，任務的正常加工時間和退化因子如表1所示。

表1 任務數(shù)據(jù)表

j123pj451830aj0．30．50．25

其他參數(shù)分別為：α=12，β=10，γ=5，δ=6，η=1，λ=0.5，θ=0.8，k=1，b=18，c=0.8。求最優(yōu)流容量、最優(yōu)窗口長度、最優(yōu)資源分配、最優(yōu)排序使得(2)最小。

[1]PINEDO M.Scheduling:Theory,Algorithms and Systems[M].Englewood cliffs,NJ.2012,Prentice hall.

[2]YIN Y,CHENG T C E,WU,et al.Single-machine common due-date scheduling with batch delivery costs and resource-dependent processing times[J].International Journal of Production Research,2013,51(17):5083-5099.

[3]YANG D L,CHENG T C E,YANG S J.Parallel-machine Scheduling with controllable processing times and rate-modifying activities to minimise total cost involving total completion time and job compressions[J].International Journal of Production Research,2014,52(4):1133-1141.

[4]Y YIN,TCE CHENG,C C WU,et al.Single-machine due window assignment and scheduling with a common flow allowance and controllable job processing time[J].Journal of the Operational Research Society,2014,65(1):1-13.

[5]GANG LI,MEILING LUO,WENJIE ZHANG,et al.Single machine due-window assignment scheduling based on common flow allowance,learning effect and resource allocation[J].International Journal of Production Research,2015,53(4):1228-1241.

[6]JIBO WANG,JIANJUN WANG.Research on scheduling with job-dependent learning effect and convex resource-dependent processing times[J].International Journal of Production Research,2015,53(19):5826-5836.

[7]MOSHEIOV G,D ORON.Job-dependent due-window assignment based on a common flow allowance[J].Foundations of Computing and Decision Sciences,2010,35:185-195.

[8]MOR B,G MOSHEIOV.Scheduling a maintenance activity and due-window assignment based on common flow allowance[J].International Journal of Production Economics,2012,135(1):222-230.

[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]YANG S J,YANG D L,CHENG T C E.Single-machine due-window assignment and scheduling with job-dependent aging effects and deterioration maintenance[J].Comput.Oper.Res,2010，37(8):1510-1574.

[11]MIN JI,JIAOJIAO GE,KE CHEN,et al.Single-machine due-window assignment and scheduling with resource allocation,aging effect,and a deteriorating rate-modifying activity[J].Computers&Industrial Engineering,2013,66:952-961.

[12]MOSHEIOV G,SARIG A.Scheduling a maintenance activity and due-window assignment on a single machine[J].Comput.Oper.Res,2009,36(9):2541-2545.

[13]WANG J B,L LIU,C WANG.Single machine SLKDIF due window assignment problem with learning effect and deteriorating jobs[J].Applied Mathematical Modelling,2011,35(8):4017-4022.

[14]YANG S J,YANG D L,CHENG T C E.Single-machine due-window assignment and scheduling with job-dependent aging effects and deterioration maintenance[J].Comput.Oper.Res,2010,37(8):1510-1574.

[15]WANG J B,M Z WANG.Single-machine scheduling to minimize total convex resource consumption with a constraint on total weighted flow time[J].Computers & Operations Research,2012,39(3):492-497.

(責任編輯：吳萍 英文審校：劉勇進)

A Single-machine due-window assignment scheduling based on common flow allowance with deteriorating effect,maintenance activity and resource allocation

ZHAO Wei-yu,LUO Cheng-xin

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

This paper considered a single-machine due-window assignment scheduling problem based on a common flow allowance.In order to improve production efficiency,a budget of resource is assumed to be finite.Once the maintenance activity has been completed,the machine will revert to its initial condition and the aging effect will start anew.The maintenance duration depends on its starting time.We assumed the actual processing time of a job was a convex function of its position and resource allocation.The objective was to find the common flow allowance,the due-window size,the resource allocation and the job sequence which minimizes the total cost of earliness,tardiness,the starting time of due-window,the size of due-window,makespan,the total of completion time of all jobs,and resource allocation.We introduce an efficient algorithm to solve the problem.

scheduling；aging effect；maintenance activity；resource allocation；due-window；common flow allowance

2016-06-28

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

趙崴羽(1992-)，女，遼寧朝陽人，碩士研究生，主要研究方向：組合最優(yōu)化與隨機運籌學，E-mail:zwy_house@qq.com；羅成新(1958-)，男，遼寧新賓人，教授，主要研究方向：組合最優(yōu)化與隨機運籌學，E-mail:luochengxin@163.com。

2095-1248(2016)05-0082-06

O223

A

10.3969/j.issn.2095-1248.2016.05.015