□汪 瑜 孙 宏 [中国民航飞行学院 广汉 618307]

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

□汪 瑜 孙 宏 [中国民航飞行学院 广汉 618307]

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

固定工件排序；网络时序图；模拟退火；多项式算法

引 言

固定工件排序问题是指对拥有明确加工时间的若干待加工工件，将其按照一定的加工顺序分配给机器加工，实现最小化工件的最大完工时间。而作为一类特殊的固定工件排序问题，即有机器数目限制，开始时刻与结束时刻明确，存在“机器-工件”约束关系的问题同样在经济管理、生产调度、工程技术和军事方面有着广泛的应用背景：如在学校课程表的制定过程中，所有的待授课程（即固定工件）有着明确的开始时刻与结束时刻，而教室（即机器）数目是有一定限制的，并存在待授课程的学生数目与教室可容纳人数之间的限制问题，要求合理安排待授课程与教室之间的关系；又如航空公司飞机调度问题，在已有的航班计划基础上，航班（即固定工件）的起飞时刻与结束时刻等因素明确，待使用飞机（即机器）数目有限，另外航班上的旅客人数与飞机最大容量之间存在着一定的约束，要求合理的将飞机分配安排到航班上；……