陳耀寧，柳秉昉

(1.重慶師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，重慶401331；2.重慶師范大學(xué)教育科學(xué)學(xué)院，重慶401331)

帶有維修活動和加工時間有關(guān)的單機排序

陳耀寧1，柳秉昉2

(1.重慶師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，重慶401331；2.重慶師范大學(xué)教育科學(xué)學(xué)院，重慶401331)

討論帶有維修活動區(qū)間且與時間有關(guān)的單機排序問題.工件的實際加工時間是關(guān)于這個工件開始加工時間的線性函數(shù)，其在加工工件的過程中需要進行維修，維修過程中及不能加工工件，且維修與時間有關(guān).維修過后機器加工工件的速度也發(fā)生變化.目標(biāo)是確定維修的位置及排序，從而使目標(biāo)函數(shù)最小.

單機排序；維修活動；加工時間

一般的排序問題中，工件的加工時間都是可控的，Nowicki等[1]和Shabtay等[2]研究了加工時間可控的排序問題.Panwalkar等[3]研究了單機加工時間的可控性.Cheng等[4]、Yang等[5]和Zhao等[6]研究了工件的加工時間與開始加工時間呈線性相關(guān)的單機排序問題.另一方面，單機排序問題中加入了具有維修活動，這樣更符合實際問題.Cheng等[4]、Yang等[5]、Zhao等[6]、Yang等[7]和Ang S－J等[8]研究了具有維修活動的單機排序，并提出了相關(guān)的算法.在單機排序理論的不斷發(fā)展中，漸漸加入了工期窗口.Cheng等[4，9]討論了共同工期窗口的單機排序問題，Yang等[5]、Zhao等[6]和Mosheiov等[10]討論了時間窗口的單機排序，Yang等[7]在單機排序中加入了松弛工期窗口，Ang S－J等[8]在此基礎(chǔ)上研究工期指派問題，Shabtay等[11－12]研究了開放的工期窗口指派問題.

本文考慮的是帶有維修活動區(qū)間且與時間有關(guān)的單機排序問題.目標(biāo)是確定維修的位置及排序，從而使目標(biāo)函數(shù)最小.

1 問題描述

有n個工件{J1，J2，…，在同臺機器上加工，所有工件零時間到達(dá)，同一時間機器只能加工一個工件.工件Jj的基本加工時間為Pj.但實際加工過程中工件的加工時間與開始加工時間呈線性函數(shù)，表示工件的實際加工時間，且＝Pj＋bSj，Sj為工件Jj的開始加工時間，且＝Pj＋bSj，Sj為工件Jj的開始加工時間.機器在加工完成第i個工件后需要進行一次維修，花費時間為t＝aci，ci表示第i個工件的完工時間，維修過后工件Jj的基本加工時間為SjPj，實際加工時間＝SjPj＋bSj.工件Jj的工期dj＝＋q.Cj，Ej＝max{ 0，dj－cj}.Tj＝max{ 0，cj－dj}.分別表示工件的完工時間、提前時間、誤工時間.一般地，工件在完工時會產(chǎn)生一定的費用，包括基本加工費用，提前完工費用，沒有完工費用.要確定維修位置以及工件的加工順序，從而小化總費用目標(biāo)函數(shù)(αEj＋βTj＋γq)＋D.用三參數(shù)表示為1 γm，Pj＋bSj∑αEj＋βTj＋γq＋D.

2 問題的分析

工件在不同加工位置上的工期時間和完工時間:

引理1 如果Cj≤dj，則Cj－1≤dj－1，j＝1，2，…，n；如果Cj≤dj，則Cj＋1≤dj＋1，j＝1，2，…，n.

定理1 對于問題1 γm，Pj＋bSj∑(αEj＋βTj＋γq)＋D，最優(yōu)排序有q＝Ck－1，1≤k≤n，且

證明 設(shè)Ck－1≤q≤Ck.不妨設(shè)k

由引理1可知，在第k個工件之前工件都是提前的，在第k個工件之后工件都是誤工的，用Zj表示第j個工件的提前或誤工費用，有:

很顯然，A和B都獨立于Δ，且B>0.若使Z最小，則有:

所以有q＝Ck－1，且

由以上分析可知，在1≤i

3 問題的算法

由上述分析不難看出，該問題用指派算法可以求出:

Step2:將工件接觸PT規(guī)則排列并選前k－1個工件排在前k－1個工件上；

Step3:將后面的工件按SPT規(guī)則排序.

例1 假設(shè)n＝6，α＝6，β＝9，γ＝2，a＝b＝0.1，D＝10，各工件的加工時長與開始時間如表1所示.

表1 各工件的加工時長與開始時間Tab.1 Processing time and start time of each job

Step2:當(dāng)k－1個2件順序為[J1，J2，J3，J4].

Step3:工件的加工順序為J6→J5→J1→J2→J3→J4，且維修發(fā)生在工件J5加工完，Z＝732.88561.

4 結(jié)論

本文討論了依賴時間的維修活動.需要確定最佳的維修位置，工件的加工順序從而極小化目標(biāo)函數(shù).分別從不同的維修位置考慮從而證明這個問題是多項式可解，并且在此基礎(chǔ)上提出算法，例子使用Matlab軟件編程進行運算的，這樣極大的提高了運算速度.進一步的問題可以考慮其他單機問題或者平行機問題，或者考慮多次維修的情形.

[1] NOWICKI E，ZDRZALKA S.A survey of result for sequencing problems with controllable processing times[J].Discrete Applied Mathematics，1990，26(2/3):271－287.

[2] SHABTAY D，STEINER G.A survey of scheduling with controllable processing time[J].Discrete Applide Mathematics，2007a，155(13):1634－1666.

[3] PANWALKAR SS，RAJAGOPALAN R.Single－machine sequencing with controllable processing times[J].European Journal of Operational Research，1992，59(2):298－302.

[4] CHENGT C E，YANGS J，YANG D L.ommon due－window assignment and scheduling of linear time－dependent deteriorating jobs and a deteriorating maintenance activity[J].International Journal of Production Economics，2010，135:154－161.

[5] YANG S J，YANG D L，YANG Q Y，et al.Single machine due window assignment and scheduling with job－depend aging effects and deteriorating maintenance activities[J].Computers and Operations Research，2010，37:1510－1514.

[6] ZHAO C L，TANG H Y.A note to due－window assignment and single machine scheduling with deteriorating jobs and a rate－modifying activity[J]. Computers and Operations Research，2012，39:1300－1303.

[7] YANG S－J，HSU C－J，YANG D－L.Single－machine scheduling and slack due－date assignment with aging effect and deteriorating maintenance[J]. Optimization Letters，2012，6(8):1855－1873.

[8] AANG 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 Science，2010(b)，21(12):177－195.

[9] SHABTAY D，STEINER G.Optimal due date assignment and resource allocation to minimize the weighted number of tardy jobs on a single machine [J].Manufacturing and Service Operations Management，2007b，9(3):332－350.

[10] CHENG T C E.Optimal single machine sequencing and assignment of common due－date，Computers and Industrial Engineering，1992，22:115－120.

[11] MOSHEIOV G，ORON D.Job－dependent due－window assignment based on a common flow allowance[J].Foundations of computing and Decision Sciences，2010，35:185－195.

[12] SHABTAY D，STEINER G.The single－machine earliness－tardiness scheduling problem with due date assignment and resource－dependent processing times[J].Annals of Operations Research，2008，159(1):25－40.

[13] WU Y B，WAN L，WANG X Y.Study in due－window assignment scheduling based in common flow allowance[J].International Journal of Production Economics，2015，165:155－157.

責(zé)任編輯:時 凌

Single Machine Scheduling with Maintenance Intervals for Processing Time

CHENG Yaoling1，LIU Bingfang2
(1.School of Mathematics Science，Chongqing Normal University，Chongqing 401331，China；2.School of Educational Science，Chongqing Normal University，Chongqing 401331，China)

This paper considers single－machine scheduling a dereriorating maintenance activity with time. The actual processing time is a linear function of the starting time.The workpiece needs to be maintained in the process of maching，and can not be processed during maintenance.After maintenance，the processing speed of the machine is changed.The goal is to determine the location of the maintenance，so that the objective function is minimized.

single machine scheduling；maintenance；proccessing time

O223

A

1008－8423(2017)01－0056－03

10.13501/j.cnki.42－1569/n.2017.03.013

2016－11－15.

陳耀寧(1992－)，男，碩士生，主要從事系統(tǒng)理論的研究.