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

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

Analysis of Characteristics of Scheduling Problem and Its Solution Space

There are no universal criteria and foundations to evaluate approximate algorithms in combinatorial optimization fields at present,however,the focusing problems make great difference to the efficiency of algorithms.In this paper,we take the Job-shop problem as an example ,analyze the characteristics of the scheduling problem and its solutions space,and propose a concept:cutting-factor.Our research shows that cutting-factor can decide the size of the solution space,and processing time of the operations can influence the roughness of the solution space;cutting-faiter and processing-time's distribution can indicate the complexity of the scheduling problem.Our study is an exploring step towards establishing universal criteria for approximate algorithms,and can guide the design of algorithms to some extent.