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

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

具有柔性維護周期的單機誤工排序問題

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

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

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

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

0 引 言

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

1 問題陳述及符號說明

圖1 固定維護周期(PM)

圖2 柔性維護周期(FPM)

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

2.1 問題P1的不可近似性

通過多項式時間歸約法來證明排序問題P1是不可近似的，即不存在具有常數(shù)界的多項式時間近似算法.

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

引理1 若劃分問題實例I的答案為“是”，則對應排序實例I′的最優(yōu)值F*=0.

引理2 若劃分問題實例I的答案為“否”，則對應排序實例I′的最優(yōu)值F*≥1.

定理1 對任意r≥1，排序問題P1不存在最壞情況界為r的多項式時間近似算法.

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

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

綜上，算法A可以用來求解劃分問題.因為從劃分問題的實例構造排序問題實例的過程和算法A都是多項式時間的，所以劃分問題就存在多項式時間的最優(yōu)算法，即證明了劃分問題屬于P類問題，這與劃分問題屬于NP-完全類問題矛盾(除非P=NP).故P1不存在最壞情況界為r的多項式時間近似算法.證畢.

2.2 問題P1的動態(tài)規(guī)劃與可解情形

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

(1)

3 結束語

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

[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

國家自然科學基金資助項目(11571252，11401149)；浙江省自然科學基金資助項目(LY16A010015)

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

O221.7

A

1001-9146(2017)03-0084-03