Revamping the current SCE-FYP allocation system using Pseudo-Boolean SAT solver and hungarian algorithm

Abstract

The Final Year Project (FYP) process in Nanyang Technological University involves the use of FYP Student Allocation System (StudSYS) and the FYP Staff Allocation System (StaffSYS). The StudSYS handles project allocation to students while StaffSYS allocates projects to examiners and timeslots to projects for oral presentation. Although the current two systems are able to perform their tasks, several problems do exist. Thus, four algorithms, PB SAT Solver, Hungarian Algorithm, and 2 personally created algorithms, were explored in this report to compare and gauge their effectiveness in solving the existing problems.

The two improved systems were developed in Java using NetBeans IDE 6.9.1. PB SAT Solver was incorporated in both systems using a Java library, called the Sat4j[1], to perform all allocation tasks through formulation of PB equations. In contrast, the Hungarian Algorithm was integrated using a Java implementation from Kevin Stern[2] and utilized only for solving the basic allocation task in StudSYS. The 2 personally created algorithms were used for the allocation tasks in StaffSYS. Eventually, the performance of all the algorithms in performing their respective allocation tasks was then evaluated.

Favorable results were obtained through tests on several datasets done on all the allocation tasks which indicated that the adopted algorithms were capable of performing their respective allocation tasks. For the basic allocation task in StudSYS, Hungarian Algorithm was a winner with its fast processing speed that edged out PB SAT Solver. On the other hand, the allocation tasks in StaffSYS were handled well by the PB SAT Solver and the alternative algorithms.

In conclusion, the adopted algorithms are suitable candidates for improving the current FYP systems. In future, focus could be placed to combine the essence of Hungarian Algorithm and PB SAT Solver in coming up with a more efficient and effective solution.