EVENT SCHEDULING

Abstract

In the present day’s fast-paced world, there is a great emphasis on organized and efficient use of resources and scheduling has become an important part of daily life; be it work, education, transport or entertainment. In many real-world cases, particularly where resources are not in abundance, and domain-specific requirements are complex, the construction of usable and effective schedules can be a very challenging task. Due to its importance and complexities involved in its construction, automation of scheduling is an imperative task for every sizable organization, to enable it to make the most out of its time and resources. Event scheduling is a combinational optimization problem which belongs to a class of NP-complete problems along with other ‘difficult-to-solve’ problems like Traveling Salesman Problem, Bin-packing and Graph-coloring. In these problems, only surety to find best solution is by checking all the possible solutions using bruteforce/exhaustive search, which is not practically possible due to very high computational costs. Being an NP-Complete problem, a time-bound solution for Scheduling problems can not be guaranteed by any of the algorithms. Therefore, new ideas and approaches for the solution provide new opportunities towards more complete and better working algorithms. In addition, different scenarios have different constraintsets, which need different approaches towards solution; therefore, devising a general framework which can cater for different scenarios may be helpful in many application areas. In this thesis, a hybrid two-stage framework has been presented. The approach is inspired by the mutual-aid and persistent/die-hard behavior of ants exhibited when faced with difficult scenario while collecting food, thus named “Die-Hard Co-Operative Ant Behavior Approach” (DCABA). An initial assignment of events is obtained with the help of a set of heuristics and it is evolved by searching promising areas of searchspace by finding the problematic events instead of random search. The search space is limited by defining some more heuristics. In the first stage, a feasible solution is constructed and in the second stage, optimizer functions improve quality of the vi obtained solution. Many different heuristics and techniques may be used within this framework. The approach has been applied on a set of University Course Scheduling Instances and promising results have been obtained. This approach may also be used for the solution of job shop scheduling, traveling salesman problem and vehicle route scheduling problem. This research work is useful for a host of scenarios where automation of scheduling can help improve performance, efficiency and time management.