计算机集成制造系统
計算機集成製造繫統
계산궤집성제조계통
COMPUTER INTEGRATED MANUFACTURING SYSTEMS
2014年
5期
1070-1077
,共8页
并行分层%工作流调度%有向无环图%启发式%优化算法
併行分層%工作流調度%有嚮無環圖%啟髮式%優化算法
병행분층%공작류조도%유향무배도%계발식%우화산법
concurrent level%workflow scheduling%directed acyclic graph%heuristics%optimization algorithm
针对给定截止时间约束下用有向无环图描述的工作流时间费用优化问题,逆向分层算法未考虑工作流中各个任务在实际执行过程中的并行性而带来相对较多的时间碎片,提出一种基于并行分层的工作流调度算法——并发级别工作流调度算法.该算法将工作流在实际执行过程中的某个任务和其他一个(或具有依赖关系的相邻多个)并行执行的任务尽量划分到同一层,并根据各层的并行度分配冗余时间,对每层中存在具有依赖关系的多个相邻任务采用Markov决策过程算法进行时间费用优化.对平衡结构和非平衡结构的有向无环图所描述的工作流进行大量模拟实验,对比最小临界路径算法、逆向分层算法和期限顶级算法,实验结果表明所提算法具有较显著的优势.
針對給定截止時間約束下用有嚮無環圖描述的工作流時間費用優化問題,逆嚮分層算法未攷慮工作流中各箇任務在實際執行過程中的併行性而帶來相對較多的時間碎片,提齣一種基于併行分層的工作流調度算法——併髮級彆工作流調度算法.該算法將工作流在實際執行過程中的某箇任務和其他一箇(或具有依賴關繫的相鄰多箇)併行執行的任務儘量劃分到同一層,併根據各層的併行度分配冗餘時間,對每層中存在具有依賴關繫的多箇相鄰任務採用Markov決策過程算法進行時間費用優化.對平衡結構和非平衡結構的有嚮無環圖所描述的工作流進行大量模擬實驗,對比最小臨界路徑算法、逆嚮分層算法和期限頂級算法,實驗結果錶明所提算法具有較顯著的優勢.
침대급정절지시간약속하용유향무배도묘술적공작류시간비용우화문제,역향분층산법미고필공작류중각개임무재실제집행과정중적병행성이대래상대교다적시간쇄편,제출일충기우병행분층적공작류조도산법——병발급별공작류조도산법.해산법장공작류재실제집행과정중적모개임무화기타일개(혹구유의뢰관계적상린다개)병행집행적임무진량화분도동일층,병근거각층적병행도분배용여시간,대매층중존재구유의뢰관계적다개상린임무채용Markov결책과정산법진행시간비용우화.대평형결구화비평형결구적유향무배도소묘술적공작류진행대량모의실험,대비최소림계로경산법、역향분층산법화기한정급산법,실험결과표명소제산법구유교현저적우세.
