• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看

      ?

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

      2017-06-23 12:44:23陳光亭
      關鍵詞:誤工近似算法單機

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

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

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

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

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

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

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

      0 引 言

      現(xiàn)代工業(yè)生產中,為提高機器的工作效率或防止機器因持續(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,首先在多項式時間內構造排序問題P1的實例I′,接著調用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

      猜你喜歡
      誤工近似算法單機
      熱連軋單機架粗軋機中間坯側彎廢鋼成因及對策
      新疆鋼鐵(2021年1期)2021-10-14 08:45:36
      審計誤工補貼背后的故事
      宇航通用單機訂單式管理模式構建與實踐
      水電的“百萬單機時代”
      能源(2017年9期)2017-10-18 00:48:22
      警惕村集體誤工支出亂象
      試論農民工誤工賠償?shù)臉藴实倪m用范圍爭議
      法制博覽(2017年30期)2017-01-27 14:08:06
      應用自適應交叉近似算法快速計算導體RCS
      求投影深度最深點的近似算法
      考試周刊(2016年88期)2016-11-24 13:32:14
      村集體誤工支出管理與賬務處理
      無壓流六圓弧蛋形斷面臨界水深近似算法
      嘉荫县| 肇东市| 马尔康县| 福建省| 宣化县| 濮阳市| 雅安市| 开江县| 榆树市| 通许县| 昌乐县| 建阳市| 通化县| 安平县| 聂荣县| 唐海县| 五华县| 台湾省| 成武县| 梁平县| 巧家县| 南皮县| 天峨县| 林甸县| 安阳市| 龙州县| 布拖县| 荥经县| 平和县| 武夷山市| 南安市| 常山县| 萝北县| 法库县| 宁津县| 通州市| 延庆县| 沙洋县| 定襄县| 比如县| 扶沟县|