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

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 proj...

Full description

Saved in:
Bibliographic Details
Main Author: Chia, Yong Sheng.
Other Authors: Chia Liang Tien
Format: Final Year Project
Language:English
Published: 2013
Subjects:
Online Access:http://hdl.handle.net/10356/52126
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-52126
record_format dspace
spelling sg-ntu-dr.10356-521262023-03-03T20:36:24Z Revamping the current SCE-FYP allocation system using Pseudo-Boolean SAT solver and hungarian algorithm Chia, Yong Sheng. Chia Liang Tien School of Computer Engineering Centre for Multimedia and Network Technology DRNTU::Engineering 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. Bachelor of Engineering (Computer Engineering) 2013-04-23T08:19:34Z 2013-04-23T08:19:34Z 2013 2013 Final Year Project (FYP) http://hdl.handle.net/10356/52126 en Nanyang Technological University 94 p. application/pdf
institution Nanyang Technological University
building NTU Library
continent Asia
country Singapore
Singapore
content_provider NTU Library
collection DR-NTU
language English
topic DRNTU::Engineering
spellingShingle DRNTU::Engineering
Chia, Yong Sheng.
Revamping the current SCE-FYP allocation system using Pseudo-Boolean SAT solver and hungarian algorithm
description 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.
author2 Chia Liang Tien
author_facet Chia Liang Tien
Chia, Yong Sheng.
format Final Year Project
author Chia, Yong Sheng.
author_sort Chia, Yong Sheng.
title Revamping the current SCE-FYP allocation system using Pseudo-Boolean SAT solver and hungarian algorithm
title_short Revamping the current SCE-FYP allocation system using Pseudo-Boolean SAT solver and hungarian algorithm
title_full Revamping the current SCE-FYP allocation system using Pseudo-Boolean SAT solver and hungarian algorithm
title_fullStr Revamping the current SCE-FYP allocation system using Pseudo-Boolean SAT solver and hungarian algorithm
title_full_unstemmed Revamping the current SCE-FYP allocation system using Pseudo-Boolean SAT solver and hungarian algorithm
title_sort revamping the current sce-fyp allocation system using pseudo-boolean sat solver and hungarian algorithm
publishDate 2013
url http://hdl.handle.net/10356/52126
_version_ 1759856742993231872