• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

Computer Engineering & Science

Previous Articles     Next Articles

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. (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:

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