作业车间含工期约束的离散时间成本权衡问题的关键路径法.pdfVIP

作业车间含工期约束的离散时间成本权衡问题的关键路径法水 口郭颖楠 口孙树栋 西北工业大学机电学院 西安710072 摘要：针对作业车间舍工期约束的离散时阅成本权衡问题，提出一种改进的基于关键路径的精确求解方法。该方 法在保证交货期的前提下，通过优化选择需要压缩的活动及压缩量，最小化总成本。最后，给出一个算例阐释该方法求解 过程，通过与枚举方法比较，验证了关键路径法的有效性。 关键词：作业车间 离散时间成本权衡关键路径法工期 中图分类号：THl62+．2；TP301．6文献标识码：A 在离散时间成本权衡问题(DiscreteTime—Cost On 用的AOE(ActivityEdge)模型并不适合描述含时 Tradeoff Problem，DTCTP)中，活动的持续时间是离散 间一成本权衡的JSP问题，因而，该方法无法直接用于 的，是关于此项活动单一不可更新资源数量的非增函 数。按照目标不同，DTCTP问题可以分为3类Ⅲ[5]：(1)(deadlineDiscreteTime-CostTradeoff 工期问题。即满足限定的工期，使工程总成本最小。 c“3的 (2)预算问题。限定预算成本，使工程的工期最短。(3) 算法，求解作业车间d～DTCTP。 效能问题。在可行的工程工期内．构建完整而有效的 1 问题建模 时间一成本曲线。DTCTP是NP—hard问题…，求解 DTCTP问题的方法包括枚举法Ⅲ、割平面法[3]、整数规 考虑到每个活动都需要设置执行时间与成本， 划‘4][5]、动态规划‘“、基于网络分解及约减的分支定DTCTP的目标是选择一组加工模式．在满足工期的条 界刚，3等精确算法．以及近似算法㈦和启发式算法㈧等。 件下最小化总成本。作业车间d—DTCTP问题通过有向 On Node)无环图形式G=(y，A)描述，节点集y表示所有活动， Hindelang和Muth【lo]基于AON(Activity 网络，首次建立限定工期DTCTP的动态规划模型。圆弧集A代表活动之间的前后约束关系，表示为AON Prabuddha等…对Hindelang和Muth的方法进行改进 得出最优解。基于AON网络分解，Akkan等n¨提出使两个虚活动分别代表加工活动的开始与结束。(i，．i)∈ 用列生成技术的上下界法求解工期底线DTCTP。A表示活动i是活动，的前置活动。每种活动i∈V都 Demeulemeester等[】21提出分支定界法求解问题。刘士有执行模式尬。由于活动的持续时间是关于此活动单 新等(13 ～不可更新资源数量(如成本)的非增函数，因而对于 3提出一种遗传算法求解工程底线问题，并绘制 出有效的工期／成本曲线。Siemens【，41提出了求解工期 DTCTP的基于关键路径法的算法；然而，该方法所采 执行模式r和k的时间，而c—c矗分别表示活动i在执 +国家自然科学基金资助项目(编号 收稿日期：2012年4月 行模式r和k的成本。 a 挖 Sahin M a1．Fault for Celeux A，et rL 1J F’YavuzC，AmavutZ，et p， G，CometF，Lannoya1．DesigningBayesian Diagnosis