The effects of event selection based on soft constraint violation (ESSCV) in a modified PSO algorithm to solve class scheduling problems

摘要

Generating an initial solution and then iteratively improve the solution are common initial steps in solving class scheduling problems. In this improvement process, the re-assignment of events to a new time slot and the selection of event to be reassigned play a significant role in reducing the soft constraint violation and finally improving the quality of the timetable. This paper proposes a local search heuristic which handle an event selection namely Event Selection based on Soft Constraint Violation (ESSCV) applied in a modified PSO algorithm to solve class scheduling problems. This technique was based on the idea of re-assignment of event which contributes to soft constraints violation, hoping the new assignment will alleviate the violation. The performance of the proposed technique was measured based on percentage penalty reduction (%PR) and execution time. Five sets of data from International Timetabling Competition were used in the experiment. The experimental results shows that ESSCV managed to reduce the event contributed to soft constraint violation, thus increases the %PR even though also demonstrated a small increase in execution time.