计算机工程与设计
計算機工程與設計
계산궤공정여설계
COMPUTER ENGINEERING AND DESIGN
2014年
7期
2407-2411
,共5页
多处理机%任务调度%近似算法%贪心策略%任务分配
多處理機%任務調度%近似算法%貪心策略%任務分配
다처리궤%임무조도%근사산법%탐심책략%임무분배
multiprocessor%task scheduling%approximate algorithm%greedy strategy%task allocation
为提高某建筑设计院工作流管理项目的开发效率、降低开发成本，针对项目任务分配过程中出现的一类多处理机调度R Cmax问题，分析了这类问题的特点，综合考虑任务的工作量及难易程度、开发团队的人员数量及个人能力，建立了这类问题的数学模型，利用贪心算法思想，设计了一种适合求解这类问题的近似算法MFTM。该算法遵循的主要思想是使最大完成时间的任务最快完成。给出了实施的具体步骤，验证了该算法的界。分别采用现实项目调度过程中的数据及仿真数据进行大量实验，实验结果表明了该算法的有效性。
為提高某建築設計院工作流管理項目的開髮效率、降低開髮成本，針對項目任務分配過程中齣現的一類多處理機調度R Cmax問題，分析瞭這類問題的特點，綜閤攷慮任務的工作量及難易程度、開髮糰隊的人員數量及箇人能力，建立瞭這類問題的數學模型，利用貪心算法思想，設計瞭一種適閤求解這類問題的近似算法MFTM。該算法遵循的主要思想是使最大完成時間的任務最快完成。給齣瞭實施的具體步驟，驗證瞭該算法的界。分彆採用現實項目調度過程中的數據及倣真數據進行大量實驗，實驗結果錶明瞭該算法的有效性。
위제고모건축설계원공작류관리항목적개발효솔、강저개발성본，침대항목임무분배과정중출현적일류다처리궤조도R Cmax문제，분석료저류문제적특점，종합고필임무적공작량급난역정도、개발단대적인원수량급개인능력，건립료저류문제적수학모형，이용탐심산법사상，설계료일충괄합구해저류문제적근사산법MFTM。해산법준순적주요사상시사최대완성시간적임무최쾌완성。급출료실시적구체보취，험증료해산법적계。분별채용현실항목조도과정중적수거급방진수거진행대량실험，실험결과표명료해산법적유효성。
To improve the efficiency of the development of an architectural design institute’s workflow management proj ect and to reduce development costs,characteristics of R Cmax that was a multiprocessor scheduling problem found in task allocation process of the proj ect were analyzed,and factors such as workload,difficulty of the task,the number of personnel development team and individual capabilities were also taken into consideration.A mathematical model of this kind of problem was construc-ted.An approximation algorithm based on greedy algorithm,which was suitable for solving such problems was designed.The fastest machine was chosen to finish the task with max-completion time.Detailed operation steps were given and the bound was proved.A large number of experiments using realistic project schedule data and simulation data were done,and the calculated re-sults showed that the algorithm was effective.
