陳耀寧

（重慶師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，重慶401331）

帶有多次維修的多窗口單機(jī)排序

陳耀寧

（重慶師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，重慶401331）

討論了工件加工時(shí)長(zhǎng)退化及維修區(qū)間與加工時(shí)間有關(guān)的多次維修的單機(jī)排序.工件的實(shí)際加工時(shí)間與其所在組前面工件的加工時(shí)長(zhǎng)有關(guān)，維修區(qū)間長(zhǎng)度與前一組的加工時(shí)長(zhǎng)線性相關(guān).每次維修后機(jī)器都能恢復(fù)到最原始的狀態(tài).目標(biāo)是極小化最大完工時(shí)間，并在此基礎(chǔ)上極小化時(shí)間費(fèi)用函數(shù).最后給出該問題的多項(xiàng)式時(shí)間算法.

單機(jī)排序；多次維修；組平衡原則；多窗口

退化效應(yīng)或者學(xué)習(xí)效應(yīng)［1］是因?yàn)楣ぜ膶?shí)際加工時(shí)間與工件的開始加工時(shí)間或者加工位置相關(guān).退化效應(yīng)多是因?yàn)闄C(jī)器在加工工件的過程中逐漸磨損而使得位置越靠后的工件的加工時(shí)間越長(zhǎng)，學(xué)習(xí)效應(yīng)與之正好相反，是因?yàn)樵诩庸すぜ倪^程中效率越來越高.

實(shí)際的工業(yè)生產(chǎn)中，機(jī)器加工一段時(shí)間后，為了保持機(jī)器的工作效率需要對(duì)機(jī)器進(jìn)行維修，維修期間機(jī)器將不能進(jìn)行加工任何工件，而且維修不止一次.Lee和Leon［2］首先將維修活動(dòng)引入到排序問題中，并且討論了單機(jī)排序中一些經(jīng)典的目標(biāo)函數(shù).Sidney［3］首先提出了帶有工期窗口指派的單機(jī)排序問題，其目標(biāo)是找到工件的最優(yōu)排序和提前與誤工的最小費(fèi)用.Yang和Lai［4］討論了具有多窗口以及加工時(shí)間可變的單機(jī)排序.Fan和Zhao［5］研究了在退化維修活動(dòng)下具有多工期及退化效應(yīng)的單機(jī)排序問題，目標(biāo)是得到最優(yōu)工期、最優(yōu)維修位置，是使工件的提前、誤工、工期費(fèi)用之和最小.謝秋蓮和張新功［6］研究了帶有線性位置退化及多維修區(qū)間的單機(jī)排序問題，目標(biāo)是極小化最大完工時(shí)間和總完工時(shí)間的和.筆者在此基礎(chǔ)上，討論了具有多窗口以及加工時(shí)間可變的多次維修的單機(jī)排序問題.

1 問題描述

設(shè)有n個(gè)獨(dú)立的工件｛J1，J2，…，Jn｝在單機(jī)上加工，工件在零時(shí)刻到達(dá)且加工過程不可中斷.工件Jj的正常加工時(shí)間為pj.機(jī)器在工件的加工過程中由于老化因素需要進(jìn)行多次維修，每次維修都能使單機(jī)恢復(fù)到最開始狀態(tài)，即每次維修后機(jī)器的工作效率都和剛開始一樣.由于單機(jī)在加工過程中存在磨損，所以工件的實(shí)際加工時(shí)間與工件的開始加工時(shí)間或者機(jī)器維修后到開始加工該工件的時(shí)長(zhǎng)成線性關(guān)系.單機(jī)的維修時(shí)長(zhǎng)與加工前面一組工件的運(yùn)行時(shí)間也呈線性關(guān)系.以每次維修為一個(gè)節(jié)點(diǎn)，設(shè)維修次數(shù)為k，則將所有工件分為k＋1個(gè)組，每組工件都有一個(gè)共同的工期窗口［di，wi］，di和wi分別表示第i個(gè)工期窗口的開始時(shí)間與結(jié)束時(shí)間，i＝1，2，…，k＋1，Di＝wi－di表示工期窗口的大小.進(jìn)一步假設(shè)任一個(gè)工期窗口不包含另外一個(gè)工期窗口.第i組工件記為Ii，該組工件個(gè)數(shù)記為ni，則，Mi表示第i次維修活動(dòng)，相對(duì)應(yīng)的維修時(shí)長(zhǎng)為ti，則該單機(jī)排序的序列π＝［I1，M1，I2，M2，…，Ik，Mk，Ik＋1］，Gij表示第i組前j個(gè)工件的加工時(shí)間和，則第i次維修時(shí)間ti＝a Gini，a＞0為維修率，Gini為第i組前ni個(gè)工件的加工時(shí)長(zhǎng).工件Jj排在第i組第j個(gè)位置的實(shí)際加工時(shí)間pAij＝pj＋b Gij－1.Cj，Ej＝max｛0，di－Cj｝，Tj＝max｛0，Cj－wj｝分別表示工件Jj的完工時(shí)間，提前時(shí)間和誤工時(shí)間.α，β，γ，δ分別表示提前，誤工，工期開始時(shí)間，工期大小的時(shí)間費(fèi)用，先考慮極小化最大完工時(shí)間Cmax，再考慮在此維修次數(shù)k和維修位置上，使得以下費(fèi)用函數(shù)最?。?/p>

筆者研究的單機(jī)排序模型用三參數(shù)法可以表示為：

2 極小化最大完工問題

本節(jié)主要介紹1｜ma，pAij＝pj＋b Gij－1，M＝k，ti＝a Gini｜Cmax的主要結(jié)論.

則

引入記號(hào)wl，則當(dāng)k確定時(shí)，

引理1 對(duì)于問題1｜ma，pAij＝pj＋b Gij－1，M＝k，ti＝a Gini｜Cmax，如果沒有維修，則所有工件按照SPT規(guī)則得到的排序是最優(yōu)的.

證 若π是最優(yōu)的工序，且所有的工件不是按照SPT規(guī)則排列得到的，則有兩個(gè)相鄰的工件Jj和Ji，有Pj＞Pi，交換兩個(gè)工件的位置得到工序π‘，設(shè)工件Jj的開始加工時(shí)間為t0，工件Ji在工序π中的完工時(shí)間記為Ci，工件Jj在工序π‘中的完工時(shí)間記為C‘j，則：

工序π‘的工件Jj的完工時(shí)間與工序π的Ji的完工時(shí)間之差為：C‘j－Ci＝b（pi－pj）＜0與π為最優(yōu)工序矛盾.

引理2 對(duì)于問題1｜ma，pAij＝pj＋b Gij－1，M＝k，ti＝a Gini｜Cmax，如果維修次數(shù)k確定，則每組的工件個(gè)數(shù)滿足組平衡原則，即n／（k＋1）#ni#n／k＋1（）＋1

證 由謝秋蓮和張新功［6］定理2可知，如果維修次數(shù)k確定，每組工件個(gè)數(shù)滿足組平衡原則.

引理3 對(duì)于問題1｜ma，pAij＝pj＋b Gij－1，M＝k，ti＝a Gini｜Cmax，如果維修次數(shù)確定，則每組工件按SPT規(guī)則排列得到的序列最優(yōu).

證 顯然，由引理1和引理2可直接得出該結(jié)論.

引理4 假設(shè)存在兩個(gè)數(shù)列xi和yi，當(dāng)xi和yi的大小序列正好相反時(shí)，乘積之和∑xiyi取得最小值.

證 Hardy等［7］首次對(duì)匹配算法進(jìn)行闡述并給予之證明.

定理1 對(duì)于問題1｜ma，pAij＝pj＋b Gij－1，M＝k，ti＝a Gini｜Cmax，如果k確定，則存在最優(yōu)序，其工件的序列按照SPT規(guī)則排列，將排好的工件依次排到每組最早的位置上，即第1個(gè)工件排到第1組第一個(gè)位置，第2個(gè)工件排到第2組第一個(gè)位置，……，第k＋1個(gè)工件排在第k＋1組第1個(gè)位置，第k＋2個(gè)工件排在第1組第2個(gè)位置，依此類推，但是將最后一個(gè)工件放在第k＋1組最后一個(gè)位置.

證 可以把wl當(dāng)成工件在每個(gè)位置的加工時(shí)間權(quán)重，將其作為一個(gè)固定的序列，根據(jù)引理4，利用數(shù)學(xué)歸納法可以證明.

3 問題 1 ma，＝pj＋b Gij－1M＝k，ti＝a Ginimin Cmax：Z

引理5 給出一個(gè)排序，最優(yōu)的工期窗口的開始時(shí)間di和結(jié)束時(shí)間wi都和某個(gè)工件的完工時(shí)間一致.

證 Mosheiov and Saring［8］證明了所有工件有一個(gè)共同工期時(shí)，存在最優(yōu)的工期窗口的開始時(shí)間和結(jié)束時(shí)間都與某個(gè)工件的完工時(shí)間是一致的，且所有的加工過程是相互獨(dú)立的.對(duì)于本問題該證明同樣成立.

引理6 對(duì)于給定的I1，I2，…，Ik，Ik＋1，存在最優(yōu)的工期窗口，使得di＝Cki［］，wi＝Ck‘i［］.其中，，i＝1，2，…，k＋1.且［x］表示大于或等于x的最小整數(shù).

證 根據(jù)Mosheiov and Saring［9］的一個(gè)擾動(dòng)技巧可以證明得到.

算法1：

Step1：將所有工件按SPT規(guī)則排列；

Step2：根據(jù)組平衡原則分組，按照定理1的規(guī)則將每個(gè)工件分配到對(duì)應(yīng)的組里；

Step3：計(jì)算Cmax（π（k）），k＝1，2，…，n－1；

Step4：取Cmax（π（k＊））＝min｛Cmax（π（k））｜k＝1，2，…，n－1｝，則k＊為最佳維修次數(shù).

Step5：確定每組工件工期的開始時(shí)間di和結(jié)束時(shí)間wi；

Step6：按照以上公式求Z值.

定理2 算法1的時(shí)間復(fù)雜度為O（n2log n）.

證 在step1的時(shí)間復(fù)雜性為O（nlog n），k從1到n－1的時(shí)間復(fù)雜度為O（n），所以其時(shí)間復(fù)雜度為O（n2log n）.

算例：求下列工件的最佳維修次數(shù)及其極小化最大完工時(shí)間，并在此基礎(chǔ)上使費(fèi)用函數(shù)最小.

p1＝6，p2＝4，p3＝1，p4＝4，p5＝8，p6＝10，p7＝7，p8＝9

a＝0.2，b＝0.3，α＝6，β＝9，γ＝2，δ＝4

算例分析：按SPT規(guī)則得到的排序?yàn)镴3→J4→J2→J1→J7→J5→J8→J6，

此時(shí)

4 結(jié)論

研究的工件加工時(shí)間具有線性惡化效應(yīng)，維修區(qū)間長(zhǎng)度與前一組工件的加工時(shí)間和呈線性關(guān)系.找到最佳的維修次數(shù)使得工件的最大加工時(shí)間最小，并在此基礎(chǔ)上求得最小費(fèi)用函數(shù).進(jìn)一步的研究可以將維修活動(dòng)與資源約束相結(jié)合，或者考慮在平行機(jī)上的多次維修問題.

［1］Bachman A，Janiak A.Scheduling jobs with position-dependent processing times［J］.The Journal of the Operational Research Society，2004，55：257－264.

［2］Lee C Y，Leon V.Machine scheduling with a rate-modifying activity［J］.European Journal of Operational Research，2001，128：119－128.

［3］Sidney J.Optimal single machine scheduling with earliness and tardiness penalties［J］.Oper.Res，1977，25：62－69.

［4］Dar-Li Yang，Chien Jung Lai，SuhJenq Yang.Scheduling problems with multiple due windows assignment and controllable processing times on s single machine［J］.Int.J.Production Economics，2014，150：96－103.

［5］Yan-Peng Fan，ChuanLI Zhao.Single machine scheduling with multiple common due date assignment and aging effect under a deteriorating maintenance activity［J］.Appl Math Comput，2014，46：51－66.

［6］謝秋蓮，張新功.帶有線性位置惡化及維修區(qū)間的單機(jī)排序問題［J］.重慶師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2015，32（5）：32－37.

［7］Hardy G H，Littlewood J E，Polya G.Inequalities［M］.London：Cambridge University Press，1934.

［8］Mosheiov G，Saring A.A duewindow assignment problem with position dependent processing times［J］.Oper.Res.Soc，2008，59：997－1003.

［9］Mosheiov G，Saring A.Scheduling a maintenance activity and due-window assignment on a single machine［J］.Comout.Oper.Res，2009，36：2541－2545.

Single machine scheduling with multiple maintenance and multiple windows

CHEN Yaoning
（School of Mathematics Science，Chongqing Normal University，Chongqing 401331，China）

The single machine sequencing of repairing and repairing interval and processing time is discussed.The actual machining time of the workpiece is related to the machining time of the workpiece in front of the group，and the length of the maintenance interval is linearly related to the processing time of the former group.After each repair the machine can be restored to the most primitive state.The goal is to minimize the maximum completion time and minimize the time cost function on this basis.Finally，the polynomial time algorithm of the problem is given.

single machine；multiple maintenance；group balance principle；multiple windows

O223

A

1671-9476（2017）02-0028-04

10.13450／j.cnkij.zknu.2017.02.007

2016-10-09；

2016-11-11

陳耀寧（1992－），男，山西晉城人，碩士研究生，研究方向：物流與供應(yīng)鏈管理.