-
题名最小基数箱子覆盖问题及其启发式算法
被引量:3
- 1
-
-
作者
孙春玲
李建平
-
机构
云南大学数学系
-
出处
《云南大学学报(自然科学版)》
CAS
CSCD
2004年第B07期8-11,共4页
-
基金
国家自然科学研究基金资助项目(10271103)
云南省自然科学研究基金资助项目(2003F0015M).
-
文摘
研究了一个新颖的装箱问题,即最小基数箱子覆盖问题(MinimumCardinalityBinCoveringProblem),证明了该问题是强NP-完备的;在物件大小满足一定的条件下,给出了一个时间复杂度为O(n)的启发式算.
-
关键词
最小基数箱子覆盖问题
强np-完备
启发式算法
最优值
-
Keywords
bin covering
np-hard
heuristic algorithm
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
-
题名执行时间可变的任务在多处理机上的排序问题
被引量:1
- 2
-
-
作者
李建平
-
机构
云南大学数学系
-
出处
《云南大学学报(自然科学版)》
CAS
CSCD
2003年第3期197-201,共5页
-
基金
国家自然科学研究基金资助项目(10271103).
-
文摘
研究一类有实际价值的网页下载问题,把其抽象成一类有n项独立任务在m台不同处理机上执行的排序问题,这里,每项任务在不同处理机上可以有不同起始时间和不同的执行时间.文章指出该问题是强NP-完备的,该问题在特殊情形下能够转化为图论中的最大匹配问题,从而给出了在此情形下的一个完全解决方案.
-
关键词
多处理机
排序问题
网页下载问题
起始时间
执行时间
图论
最大匹配问题
强np-完备性
解决方案
-
Keywords
information-gathering
np-hard in a strong sense
sequencing
makespan
matching
-
分类号
O223
[理学—运筹学与控制论]
O157.5
[理学—基础数学]
-