一类固定工件排序问题算法研究  

Research on the Algorithm of One Class of Fixed Job Scheduling Problem

作　　者：汪瑜[1] 孙宏[1] 

机构地区：[1]中国民航飞行学院,广汉618307

出　　处：《电子科技大学学报（社科版）》2010年第3期19-22,共4页Journal of University of Electronic Science and Technology of China(Social Sciences Edition)

基　　金：国家自然科学基金资助项目(No.60776820);中国民航飞行学院自然科学基金(J2008-76);中国民航飞行学院自然科学基金(J2009-29)

摘　　要：针对一类"可用机器数有限,存在机器与工件间匹配约束,以机器-工件分配成本最小为目标"的固定工件排序问题,以固定工件的开始时刻、结束时刻为基准构建网络时序图,将"机器-工件"分配过程看成网络时序图中的网络流问题,并设计排序问题的模拟退火算法。通过算例发现:算法平均CPU时间为32.9秒,总成本最大误差为0.07%,时间复杂度为O(M(m3+mn)),空间复杂度为O(m2n)。结果表明:算法为多项式算法,且可行。For one class of fixed job scheduling problem,in which the available processors were limited,the processor matching-job had to be considered and minimized processor matching-job assigning cost were taken as objective.Firstly,based on the starting and completing time of the fixed job,this algorithm constructed a network time sequence figure.Secondly,the processor matching-job assigning were transformed into a netwok flow problem.Thirdly,the simulated annealing was used to design the scheduling problem algorithm.The solid example shows that the average CPU time is 32.9 seconds,the maximum error of total cost is 0.07%,the time complexity is O（M（m3＋ mn））,and the space complexity is O（m2n）.The results indicate that this algorithm is polynomial and feasible.

关 键 词：固定工件排序 网络时序图 模拟退火 多项式算法 

分 类 号：F273[经济管理—企业管理]