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 77
- Downloads 0
Computer Control Systems With Critical Safety Applications: Problems And Some Solutions
Safety Critical Systems (SCS) are defined as systems controlling critical technological processes, on the proper functioning of which depends human safety. The taxonomy of concepts related to SCS is presented as a dendri...
USING KERBEROS PROTOCOL FOR SINGLE SIGN-ON IN IDENTITY MANAGEMENT SYSTEMS
Today, identity management systems are widely used in different types of organizations, from academic and government institutions to large enterprises. An important feature of identity management systems is the Single Si...
AUTOMATIC TEMPERATURE REGULATION SYSTEM OF LOCOMOTIVE TRACTION INDUCTION MOTORS WITH POWER LOSSES MINIMIZATION
The air cooling systems are shown to be used to provide required temperature condition of traction induction motors on locomotives. The automatic temperature regulation system is developed for its using to solve such a t...
OBJECT-ORIENTED ANALYSIS AND DESIGN FOR ONE ALGORITHM OF COMPUTATIONAL GEOMETRY: FORWARD, REVERSE AND ROUND-TRIP ENGINEERING
Triangulation of the polygon is a fundamental algorithm in computational geometry. This paper considers techniques of object-oriented analysis and design as a new tool for solving and analyzing convex polygon triangulati...
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...