HYBRID OF HILL CLIMBING AND SAT SOLVING FOR AIR TRAFFIC CONTROLLER SHIFT SCHEDULING
Journal Title: Journal of Information Technology and Application (JITA) - Year 2015, Vol 5, Issue 2
Abstract
Modern computers solve many problems by using exact methods, heuristic methods and very often by using their combination. Air Traffi c Controller Shift Scheduling Problem has been successfully solved by using SAT technology (reduction to logical formulas) and several models of the problem exist. We present a technique for solving this problem that is a combination of SAT solving and meta-heuristic method hill climbing, and consists of three phases. First, SAT solver is used to generate feasible solution. Then, the hill climbing is used to improve this solution, in terms of number of satisfi ed wishes of controllers. Finally, SAT solving is used to further improve the found solution by fi xing some parts of the solution. Three phases are repeated until optimal solution is found. Usage of exact method (SAT solving) guarantees that the found solution is optimal; usage of meta-heuristic (hill climbing) increases the effi ciency in fi nding good solutions. By using these essentially different ways of solving, we aim to use the best from both worlds. Results indicate that this hybrid technique outperforms previously most effi cient developed techniques.
Authors and Affiliations
Stojadinović Mirko
Keywords
Related Articles
- EP ID EP230965
- DOI 10.7251/JIT1502081S
- Views 73
- Downloads 0
COMPARATIVE IMPLEMENTATION ANALYSIS OF AES ALGORITHM
Advanced Encryption Standard (AES) is the fi rst cryptographic standard aroused as a result of public competition that was established by U.S. National Institute of Standards and Technology. Standard can theoretically be...
DIGITAL SIGNAL PROCESSING APPLICATIONS WITH ITERATIVE LOGARITHMIC MULTIPLIERS
Many digital signal processing applications demand a huge number of multiplications, which are time, power and area consuming. But input data is often corrupted with noise, which means that a few least signifi cant bits...
TRENDS IN EDUCATIONAL GAMES DEVELOPMENT
In this paper we will give a literature review related to game-based education, in the fi rst place at university, as well as the analysis of existing solutions which should enable this type of eLearning. The main topic...
ONLINE EVALUATION OF RECOMMENDER SYSTEM WITH MOVIELENS DATASET
The purpose of this paper is to explore the advantages of recommender systems based on the matrix factorization in respect to classical first neighbor recommender systems to real users through A/B test, as these studies...
ON INTRUSION DETECTION IN A NEIGHBOURHOOD AREA NETWORK IN THE SMART GRID
Smart grid, which is an upgrade of power electric system, mainly relies on powerful communication networks to provide a secure, reliable and effi cient information delivery. Updating a system as complex as the electrical...