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

计算机工程与科学

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

付慧敏1,2,徐扬2，何星星2,宁欣然1,2

(1.西南交通大学信息科学与技术学院，四川成都 610031；

2.西南交通大学系统可信性自动验证国家地方联合工程实验室,四川成都 610031)

收稿日期:2017-04-14 修回日期:2017-05-27 出版日期:2018-08-25 发布日期:2018-08-25
基金资助:
国家自然科学基金(61673320);中央高校基本科研业务费项目(2682017ZT12,2682018ZT10,2682018CX59,2682018ZT25)

GSAT algorithm based on task allocation and

scheduling for solving the 3-SAT problem

FU Huimin1,2,XU Yang2,HE Xingxing2,NING Xinran1,2

(1.School of Information Science and Technology,Southwest Jiaotong University,Chengdu 610031;

2.NationalLocal Joint Engineering Laboratory of System Credibility Automatic Verification,

Southwest Jiaotong University,Chengdu 610031,China)

Received:2017-04-14 Revised:2017-05-27 Online:2018-08-25 Published:2018-08-25

摘要/Abstract

摘要：

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

关键词: GSAT算法, 贪心搜索, 任务分配与调度, 3-SAT问题, 分配策略, 调度策略

Abstract:

Based on different allocation strategies for cloud computing task scheduling and task allocation and scheduling, a new algorithm—a GSAT algorithm based on task allocation and scheduling for solving the 3SAT problem is proposed.The algorithm forms a task for each variable in the 3SAT problem. Based on the GSAT algorithm,task allocation and scheduling is introduced to guide the greedy search. Meanwhile, under the premise of keeping the original greedy search, according to the idea of task allocation and scheduling and the characteristics of the 3SAT problem, two new strategies (allocation strategy and scheduling strategy) are designed to complete the whole greedy search process together.In the experiments, 3700 standard Uniform Random3SAT problems with the variable number from 20 to 250 in SATLAB library were used to evaluate the performance of the new algorithm.Moreover, the new algorithm was compared with the improved GSAT algorithms with high performance and common performance.Experimental results show that the new algorithm has a higher success rate and fewer changes.

Key words: GSAT algorithm, greedy search, task allocation and scheduling, 3SAT problem, allocation strategy, scheduling strategy

付慧敏1,2,徐扬2，何星星2,宁欣然1,2. 基于任务分配与调度的GSAT算法求解3-SAT问题[J]. 计算机工程与科学.

FU Huimin1,2,XU Yang2,HE Xingxing2,NING Xinran1,2.

GSAT algorithm based on task allocation and

scheduling for solving the 3-SAT problem

[J]. Computer Engineering & Science.

[1]	陈聪, 洪中, 陈杨杨, 张仕, 蒋建民, . 移动系统的实时调度与可调度性分析[J]. 计算机工程与科学, 2020, 42(09): 1544-1555.
[2]	郑小红, 龙军, 蔡志平. 关于网约车订单分配策略的综述[J]. 计算机工程与科学, 2020, 42(07): 1267-1275.
[3]	梁倬骞1,2，付丹龙2，邓原1. 级联过程中基于动态信息的负载重分配策略[J]. 计算机工程与科学, 2017, 39(09): 1638-1644.
[4]	王晓峰,许道云,唐瑞雪. 基于DPLL的混合遗传算法求解SAT问题[J]. J4, 2010, 32(5): 54-56.
[5]	孙文胜, 李小磊. IPv6环境下的网关负载均衡策略的研究与实现[J]. J4, 2010, 32(3): 14-16.
[6]	韩宗芬吴敏娜董志金海. VoD系统中基于优先级的准入控制和带宽分配策略[J]. J4, 2005, 27(5): 1-2.
[7]	刘晓建钟海荣吴明巧. 大规模分布式仿真中实体分配策略研究[J]. J4, 2005, 27(2): 85-89.
[8]	谢长生马进德黄浩. 基于μC_OS-Ⅱ的任务调度策略研究[J]. J4, 2004, 26(8): 70-33.
[9]	张理论赵军等. 全球气象资料质量控制的一种粗粒度并行计算调度策略[J]. J4, 2000, 22(6): 5-7.
[10]	谭支鹏胡金柱. 分布式数据库的对象调度策略[J]. J4, 2000, 22(4): 71-73.