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 69
- 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...
E-MAIL FORENSICS: TECHNIQUES AND TOOLS FOR FORENSICINVESTIGATION OF ONE COURT CASE
E-mail has emerged as the most important application on the Internet for communication of messages, delivery of documents and carrying out transactions and is used not only from computers, but many other electronic gadge...
COMPARISON OF PERCEIVED INTERACTIVITY MEASURES OF ACTUAL WEBSITES INTERACTIVITY
Interactivity is a concept of enormous importance for digital marketing. It was recognized as a key feature of website, a hub of all digital marketing activities. But, almost all interactivity measures were conceptualize...
CUSTOMER SATISFACTION AS A SIGNIFICANT MEASURE OF SUCCESSFUL ERP IMPLEMENTATION
The measuring of implemented ERP system’s effi ciency is in any case multidimensional. Various researchers dedicated a lot of attention trying to fi nd the best way to measure the success or the effectiveness of ERP solu...
ANALYZING THE COST AND BENEFIT OF PAIR PROGRAMMING REVISITED
Pair programming has received a lot of attention from both industry and academia, but most paper focus on its technical aspects, while its business value has received much less attention. In this paper, we focus on the b...