基于任务分配与调度的GSAT算法求解3-SAT问题

• 作者: 付慧敏 何星星 宁欣然 徐扬
• 来源期刊: 计算机工程与科学
• 学科: 工学
• 关键词: GSAT算法 贪心搜索 任务分配与调度 3-SAT问题 分配策略 调度策略
• 年，卷（期）: 2018,（8）
• 所属期刊栏目: 高性能计算
• 页码范围: 1366-1374
• 页数: 9页
• 分类号: TP301.5|TP301.6
• 字数: 8507字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-130X.2018.08.005

摘要

基于不同分配策略的云计算任务调度以及任务分配与调度的主要目的,提出了一种新的算法-求解3-SAT问题的基于任务分配与调度的GSAT算法.该算法将3-SAT问题中的每一个变量形成一个任务,在GSAT算法的基础上,引入任务分配与调度指导贪心搜索;同时,在保留原有贪心搜索的前提下,根据任务分配与调度的思想和3-SAT问题的特点,设计了两种新的策略-分配策略和调度策略共同完成整个贪心搜索过程.以标准的SATLAB库中变量个数从20～250的3 700个不同规模的标准Uniform Random-3-SAT问题对新的算法的性能进行了合理的测试,并与高效和普通性能改进的GSAT算法的结果作了比较,结果表明,该算法具有更高的成功率和更少的翻转次数.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	徐扬	西南交通大学系统可信性自动验证国家地方联合工程实验室	186	1462	15.0	32.0
2	宁欣然	西南交通大学信息科学与技术学院	6	6	2.0	2.0
6	何星星	西南交通大学系统可信性自动验证国家地方联合工程实验室	12	35	3.0	5.0
7	付慧敏	西南交通大学信息科学与技术学院	2	0	0.0	0.0