调度问题及其解空间的特征分析

摘要

目前,在组合优化领域中,评判近优算法的性能尚缺乏统一的标准和有效的依据,而算法的效率与所要解决问题之间的关系密不可分.本文以JSP问题为例,研究了调度问题本身的结构特征,分析了调度问题可行解空间的属性,提出了分割因子的概念.研究表明,分割因子影响调度问题可行解空间的规模,而各工序加工时间的分布则影响解空间的"崎岖”状况;分割因子和工件加工时间的分布在一定程度上可以反映调度问题的复杂程度.这对近优算法的设计具有一定的指导意义,并为建立统一的近优算法效率衡量标准迈出了探索性的一步.