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

• 作者: 刘民 吴澄 孙元凯
• 来源期刊: 电子学报
• 学科: 工学
• 关键词: JSP 调度 复杂性 原空间 可行解空间 分割因子
• 年，卷（期）: 2001,（8）
• 所属期刊栏目: 学术论文
• 页码范围: 1042-1045
• 页数: 4页
• 分类号: TP20
• 字数: 4897字
• 语种: 中文
• DOI: 10.3321/j.issn:0372-2112.2001.08.009

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	吴澄	清华大学自动化系	125	4840	34.0	67.0
2	刘民	清华大学自动化系	54	1195	17.0	33.0
3	孙元凯	清华大学自动化系	4	84	3.0	4.0