李 丹，張 安，陳 永，陳光亭

(杭州電子科技大學(xué)理學(xué)院，浙江 杭州 310018)

具有柔性維護(hù)周期的單機(jī)誤工排序問(wèn)題

李 丹，張 安，陳 永，陳光亭

(杭州電子科技大學(xué)理學(xué)院，浙江 杭州 310018)

主要研究了具有柔性維護(hù)周期的單機(jī)誤工排序問(wèn)題.首先證明了極小化誤工工件數(shù)目標(biāo)是不可近似的，即不存在具有常數(shù)界的多項(xiàng)式時(shí)間近似算法，接著設(shè)計(jì)了求解問(wèn)題的偽多項(xiàng)式時(shí)間動(dòng)態(tài)規(guī)劃算法.

排序；誤工工件；柔性維護(hù)周期；動(dòng)態(tài)規(guī)劃

0 引 言

現(xiàn)代工業(yè)生產(chǎn)中，為提高機(jī)器的工作效率或防止機(jī)器因持續(xù)運(yùn)行而發(fā)生故障，一種常見(jiàn)的策略就是對(duì)機(jī)器進(jìn)行定期維護(hù)[1].學(xué)者們主要研究了機(jī)器具有固定維護(hù)周期(Periodic Maintenance，PM)的單機(jī)排序問(wèn)題.當(dāng)目標(biāo)函數(shù)為極小化誤工工件數(shù)時(shí)，文獻(xiàn)[2]利用分支定界法獲得最優(yōu)解，并在Moore算法基礎(chǔ)上設(shè)計(jì)了啟發(fā)式算法，數(shù)值實(shí)驗(yàn)表明該啟發(fā)式算法是有效的.文獻(xiàn)[3]給出了混合整數(shù)規(guī)劃模型，并提出了一個(gè)改進(jìn)啟發(fā)式算法，通過(guò)數(shù)值實(shí)驗(yàn)說(shuō)明改進(jìn)啟發(fā)式算法要比文獻(xiàn)[2]中的啟發(fā)式算法更為有效.文獻(xiàn)[4]給出了兩個(gè)偽多項(xiàng)式時(shí)間動(dòng)態(tài)規(guī)劃算法和一個(gè)完全多項(xiàng)式時(shí)間近似方案，并通過(guò)大量數(shù)值實(shí)驗(yàn)驗(yàn)證了提出的算法是有效的.文獻(xiàn)[5]為了改進(jìn)現(xiàn)有水平的精確算法，基于有效的下界程序和若干新的主要性質(zhì)，提出了新的分支定界算法，數(shù)值實(shí)驗(yàn)表明該精確算法是有效的.與上述文獻(xiàn)不同，本文主要研究具有柔性維護(hù)周期(Flexible Periodic Maintenance，F(xiàn)PM)的單機(jī)誤工排序問(wèn)題.

1 問(wèn)題陳述及符號(hào)說(shuō)明

圖1 固定維護(hù)周期(PM)

圖2 柔性維護(hù)周期(FPM)

2 不可近似性證明與動(dòng)態(tài)規(guī)劃算法

2.1 問(wèn)題P1的不可近似性

通過(guò)多項(xiàng)式時(shí)間歸約法來(lái)證明排序問(wèn)題P1是不可近似的，即不存在具有常數(shù)界的多項(xiàng)式時(shí)間近似算法.

構(gòu)造排序問(wèn)題P1的一個(gè)實(shí)例I′：n個(gè)工件J1，…，Jn，工件的加工時(shí)間pj=aj(稱為整數(shù)aj對(duì)應(yīng)的工件)，工期dj=d=2T+N，1≤j≤n,機(jī)器的維護(hù)周期為T，每次維護(hù)的時(shí)長(zhǎng)為N.令F*表示排序問(wèn)題P1的實(shí)例I′的最優(yōu)值.

引理1 若劃分問(wèn)題實(shí)例I的答案為“是”，則對(duì)應(yīng)排序?qū)嵗齀′的最優(yōu)值F*=0.

引理2 若劃分問(wèn)題實(shí)例I的答案為“否”，則對(duì)應(yīng)排序?qū)嵗齀′的最優(yōu)值F*≥1.

定理1 對(duì)任意r≥1，排序問(wèn)題P1不存在最壞情況界為r的多項(xiàng)式時(shí)間近似算法.

證明 反證法.假設(shè)P1存在最壞情況界為r的多項(xiàng)式時(shí)間近似算法A，則對(duì)任意劃分問(wèn)題的實(shí)例I，首先在多項(xiàng)式時(shí)間內(nèi)構(gòu)造排序問(wèn)題P1的實(shí)例I′，接著調(diào)用P1的多項(xiàng)式時(shí)間算法A，根據(jù)算法A的目標(biāo)值FA的情況：

情形1FA≤0.由0≤F*≤FA≤0可得F*=0.由引理1和引理2，劃分問(wèn)題實(shí)例I的答案為“是”.

綜上，算法A可以用來(lái)求解劃分問(wèn)題.因?yàn)閺膭澐謫?wèn)題的實(shí)例構(gòu)造排序問(wèn)題實(shí)例的過(guò)程和算法A都是多項(xiàng)式時(shí)間的，所以劃分問(wèn)題就存在多項(xiàng)式時(shí)間的最優(yōu)算法，即證明了劃分問(wèn)題屬于P類問(wèn)題，這與劃分問(wèn)題屬于NP-完全類問(wèn)題矛盾(除非P=NP).故P1不存在最壞情況界為r的多項(xiàng)式時(shí)間近似算法.證畢.

2.2 問(wèn)題P1的動(dòng)態(tài)規(guī)劃與可解情形

本節(jié)給出求解問(wèn)題P1的動(dòng)態(tài)規(guī)劃算法.不失一般性，假設(shè)工件工期滿足d1≤d2≤…≤dn,即最早交工期優(yōu)先(Earliest Due Date First,EDD)，且不妨假定任一合理排序由兩部分組成：不誤工工件按EDD序排在前面加工；誤工工件以任意順序排在后面加工.

(1)

3 結(jié)束語(yǔ)

本文研究了具有柔性維護(hù)周期的極小化誤工工件數(shù)的單機(jī)排序問(wèn)題，證明了該問(wèn)題是不可近似的，并給出了該問(wèn)題的動(dòng)態(tài)規(guī)劃算法.下一步將在柔性維護(hù)周期條件下，研究加工與運(yùn)輸協(xié)同的一體化運(yùn)輸排序等問(wèn)題.

[1]ARTSR,KNAPPGM,MANNJRL.Someaspectsofmeasuringmaintenanceperformanceintheprocessindustry[J].JournalofQualityinMaintenanceEngineering, 1998,4(1):6-11.

[2]CHENWJ.Minimizingnumberoftardyjobsonasinglemachinesubjecttoperiodicmaintenance[J].Omega, 2009,37(3):591-599.

[3]LEEJY,KIMYD.Minimizingthenumberoftardyjobsinasingle-machineschedulingproblemwithperiodicmaintenance[J].Computers&OperationsResearch, 2012,39(9):2196-2205.

[4]YINY,XUJ,CHENGTCE,etal.Approximationschemesforsingle-machineschedulingwithafixedmaintenanceactivitytominimizethetotalamountoflatework[J].NavalResearchLogistics(NRL), 2016,63(2):172-183.

[5]LIUM,WANGS,CHUC,etal.Animprovedexactalgorithmforsingle-machineschedulingtominimisethenumberoftardyjobswithperiodicmaintenance[J].InternationalJournalofProductionResearch, 2016,54(12):3591-3602.

Minimizing the Number of Tardy Jobs on a Single Machine with Flexible Periodic Maintenance

LI Dan, ZHANG An, CHEN Yong, CHEN Guangting

(SchoolofScience,HangzhouDianziUniversity,HangzhouZhejiang310018,China)

This paper studies the problem of scheduling jobs on a single machine that requires flexible periodic maintenance. The objective is to minimize the number of tardy jobs. it proves that the problem cannot be approximated within a constant worst case ratio. Then a pseudo-polynomial time dynamic programming algorithm is proposed.

scheduling; tardy jobs; flexible periodic maintenance; dynamic programming

10.13954/j.cnki.hdu.2017.03.017

2016-12-01

國(guó)家自然科學(xué)基金資助項(xiàng)目(11571252，11401149)；浙江省自然科學(xué)基金資助項(xiàng)目(LY16A010015)

李丹(1991-)，女，甘肅蘭州人，碩士研究生，組合優(yōu)化.通信作者：陳光亭教授，E-mail：gtchen@hdu.edu.cn.

O221.7

A

1001-9146(2017)03-0084-03