系统工程理论与实践
繫統工程理論與實踐
계통공정이론여실천
Systems Engineering—Theory & Practice
2014年
2期
485~493
,共null页
拖轮调度 混合流水车间 下界值 模拟退火 启发式规则
拖輪調度 混閤流水車間 下界值 模擬退火 啟髮式規則
타륜조도 혼합류수차간 하계치 모의퇴화 계발식규칙
tugboat scheduling; hybrid flow shop; lower bound; simulated annealing; heuristic rules
在对拖轮调度问题进行分析的基础之上,将拖轮调度问题归结为一类具有多阶段共用机器特征的混合流水车间调度问题+建立了针对多停泊基地不同作业模式下、且考虑靠泊与停泊两阶段的拖轮调度优化模型,推导了基于混合流水作业组织的港口拖轮调度优化问题的理论下界值,并设计了启发式规则与模拟退火相结合的混合算法(HSA)求解该模型.通过运用该算法求解仿真算例,并将其结果与模型理论下界值、三种基于现行调度规则及基于Johnson规则的调度方案进行比较.结果表明,运用HSA求解的结果与理论下界值的平均偏差值为5.39%,且该结果远小于基于现行调度规则及Johnson规则的求解值,验证了模型与算法的高效性,可以为拖轮作业模式的选择以及调度方案的制订提供决策支持.
在對拖輪調度問題進行分析的基礎之上,將拖輪調度問題歸結為一類具有多階段共用機器特徵的混閤流水車間調度問題+建立瞭針對多停泊基地不同作業模式下、且攷慮靠泊與停泊兩階段的拖輪調度優化模型,推導瞭基于混閤流水作業組織的港口拖輪調度優化問題的理論下界值,併設計瞭啟髮式規則與模擬退火相結閤的混閤算法(HSA)求解該模型.通過運用該算法求解倣真算例,併將其結果與模型理論下界值、三種基于現行調度規則及基于Johnson規則的調度方案進行比較.結果錶明,運用HSA求解的結果與理論下界值的平均偏差值為5.39%,且該結果遠小于基于現行調度規則及Johnson規則的求解值,驗證瞭模型與算法的高效性,可以為拖輪作業模式的選擇以及調度方案的製訂提供決策支持.
재대타륜조도문제진행분석적기출지상,장타륜조도문제귀결위일류구유다계단공용궤기특정적혼합류수차간조도문제+건립료침대다정박기지불동작업모식하、차고필고박여정박량계단적타륜조도우화모형,추도료기우혼합류수작업조직적항구타륜조도우화문제적이론하계치,병설계료계발식규칙여모의퇴화상결합적혼합산법(HSA)구해해모형.통과운용해산법구해방진산례,병장기결과여모형이론하계치、삼충기우현행조도규칙급기우Johnson규칙적조도방안진행비교.결과표명,운용HSA구해적결과여이론하계치적평균편차치위5.39%,차해결과원소우기우현행조도규칙급Johnson규칙적구해치,험증료모형여산법적고효성,가이위타륜작업모식적선택이급조도방안적제정제공결책지지.
Based on the analysis of the tugboat scheduling problem, it is formulated as a multistage hybrid flow shop scheduling problem (MHFSSP) that has the characteristics of sharing common machine sets in all stages. Combined with the scheduling theory, a tugboat scheduling model with multi-anchorage bases, different operation modes and two stages of operations (berthing/unberthing) is presented. The lower bound (LB) of the flowtime is derived from the special MHFSSP. The algorithm based on the heuristic rules and simulated annealing (HSA) is developed to solve the special MHFSSP. By the comparison of the results obtained from the algorithm with the LB and those based on three existing scheduling rules in practice and Johnson rules, the average deviation between the HSA solved results with LB is 5.39%, and the HSA solved results are far less than those from the existing scheduling rules and the Johnson rules. Thus the effectiveness and efficiency of the proposed approach were verified, which can provide supports for the decision-making on operation modes selection and operation scheduling.