基于改进DP算法的具有优先序的变速机最小化成本调度.pdf

第3l卷第2期 系统工程理论与实践 Vbl．3LNo．2 2011年2月 Feb．，2011 SystemsEngineering—Theory＆Practice 文章编号：1000-6788(201 中图分类号：0221；F406．2；TP301文献标志码：A 1)02·0276—07 基于改进DP算法的具有优先序的变速机最小化成本调度 柳春锋·，一，李凯·，杨善林- (1．合肥工业大学管理学院，合肥230009；2．浙江旅游职业学院酒店管理系，杭州311231) 摘要研究了工件具有任意标准优先序、一台机器在同一时间只可加工一个工件、最小化工件加 工成本与机器使用成本之和的变速机调度问题．为该问题建立了DP模型，通过启发式规则和常规 动态规划方法相结合、引入工件完工时间界限并保存每一步函数值，得到改进的DP算法，数值实 验显示该算法具有较强的寻优能力和稳定性． 关键词变速机调度；优先序约束；动态规划；加工成本 ofunrelatedmachinestominimizecostswith Scheduling constraintsbasedonamendedDP precedence algorithm LIU Shan-linl Chun-fen91，一，LIKail，YANG of of (1．SchoolManagement，HefeiUniversityTechnology,Hefei230009，China； ofHotel of 31 2．DepartmentManagement，TourismCollegeZhejiang，Hangzhou1231，China) Abstract ofunrelatedmachinestominimizetotalcostsof and machines Scheduling processingjobs using to standard constraintsisconsideredinthis underthe arbitrary precedence paper assumption subject that one is ononemachineatthesametime．ADPmodelisconstructedforthe only job processed anamendedDP isderived heuristicrulewithconventional problem．and algorithm throughcombining theboundof timeand function dynamicprogramming，introducingeveryjobcompletion savingevery value．Numericalareconductedtoshowthatthe has experiments algorithm optimiz