摘要
为解决计算网格中有向无环图表示的截止期约束下的工作流时间费用优化问题,提出了一个新的启发式优化算法——相对效费比算法。该算法首先根据调度系数得到初步方案,再逐步调整,当方案完工时间小于截止期时,用时间换成本,选择成本消减最快的节点进行调整,中选服务有最大的正相对效费比值;当方案完工时间超过截止期时,用成本换时间,调整成本增加最慢服务的节点,中选服务有最大的负相对效费比值,该方法在保证截止期约束的同时能有效降低总成本。通过大量模拟实验和与最小关键路径、正向分层费用优化算法、逆向分层费用优化算法的比较,证明了相对效费比的有效性。
In order to solve the workflow time-cost optimization problem under deadline restrictions represented by directed acyclic graph（DAG） in computation grids,a novel heuristics algorithm called relative time-cost rate（RTCR）was proposed.Firstly the preliminary program was obtained by scheduling coefficient,then the scheduling was optimized gradually：when the deadline exceeded,the node with the slowest cost-decreased service was rescheduled,the selected service had the maximum positive RTCR value,otherwise the node with the fastest cost-increased service was rescheduled,the selected service had the maximum negative RTCR value.The proposed method simultaneously guaranteed deadline restrictions and reduced total cost.,the RTCR＇s effectivenss was revealed by comparing with minimum critical path（MCP）,deadline top level（DTL） and deadline bottom leve（DBL l）.
出处
《计算机集成制造系统》
EI
CSCD
北大核心
2010年第3期589-597,共9页
Computer Integrated Manufacturing Systems
基金
国家自然科学基金资助项目(60703020)
北京市教委基金资助项目(JJ007011200901)
北京工业大学211基金资助项目(007000548108)~~
关键词
网格
工作流
有向无环图
启发式算法
相对效费比
grid
workflow
directed acrylic graph
heuristics
relative time-cost rate
