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

针对一类＂可用机器数有限,存在机器与工件间匹配约束,以机器-工件分配成本最小为目标＂的固定工件排序问题,以固定工件的开始时刻、结束时刻为基准构建网络时序图,将＂机器-工件＂分配过程看成网络时序图中的网络流问题,并设计排序问题的模拟退火算法。通过算例发现：算法平均CPU时间为32.9秒,总成本最大误差为0.07%,时间复杂度为O（M（m3＋mn））,空间复杂度为O（m2n）。结果表明：算法为多项式算法,且可行。

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

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.