Leong Hon Wai, School of Computing, National University of Singapore
UROP (Computing) Projects for 1997
(Leong Hon Wai)

Supervisor:     Leong Hon Wai
Student:        Li Shuaicheng   (lishuaic)
Leave Period:   In China from 20 Nov 97 to 17 Dec 1997
Project Title:  Vessel Packing using Mathematical Programming
Course:         CS2288
Description:    
   In this project, we study the use of mathematical programming methods
   in solving the problem of "packing" vessels into a section of the harbour.
   This problem arises as a sub-problem of a larger R&D project on
   berth allocation of ships in a container port.

   We are given a collection of ships (vessels) that have to be berthed 
   in a section (of the harbour) consisting of a set of berths.
   We are also given all other pertinent information such as the lengths,
   the arrival and departure times, and the berthing times (length of time
   that a vessel has to be berth) of the vessels.
   We want to assign the vessels to berths (long vessels may occupy more
   than one berth) so as to satisfy (as much as possible) the departure
   times of the vessels.

Reference: 
   1. Swee Nam's Honours Project Report
   2. BAPS V1.0 System Manual
  *3. Some information on Packing Algorithms



Supervisor:     Leong Hon Wai
Student:        Xu Degui        (xudegui)
Leave Period:   In China from ?? Nov 97 to ?? Dec 1997
Project Title:  Simulated Annealing for the Berth Allocation Problem
Course:         CS2288
Description:    
   In this project, we study the berth allocation problem (BAP).
   This problem arises as a sub-problem of a larger R&D project 
   investigating the BAP.

   The BAP is described as follows:
   Vessels arriving at a container port are berthed in a section of a
   wharf, and the containers they ferry are then transferred to the port
   or to other vessels. We are interested in finding good berth allocations
   so as to minimize the overall movement of the containers.

   We currently have one solution to the BAP that uses genetic algorithm.
   In this project, we want to explore the use of simulated annealing for
   solving the Berth Allocation Problem.
   
Reference: 
   1. Swee Nam's Honours Project Report
   2. BAPS V1.0 System Manual
   3. Chapter on Simulated Annealing from book



Supervisor:     Leong Hon Wai
Student:         -- initially by Lim Chee Kiong
Project Title:  Tabu Search for the Berth Allocation Problem
Course:         CS2288
Description:    
   In this project, we study the berth allocation problem (BAP).
   This problem arises as a sub-problem of a larger R&D project 
   investigating the BAP.

   The BAP is described as follows:
   Vessels arriving at a container port are berthed in a section of a
   wharf, and the containers they ferry are then transferred to the port
   or to other vessels. We are interested in finding good berth allocations
   so as to minimize the overall movement of the containers.

   We currently have one solution to the BAP that uses genetic algorithm.
   In this project, we want to explore the use of tabu search for solving
   the BAP.
   
Reference: 
   1. Swee Nam's Honours Project Report
   2. BAPS V1.0 System Manual
  *3. Chapter on Tabu Search from book



Supervisor:     Leong Hon Wai
Student:        Zou Min         (zoumin) 
Leave Period:   Will be in China from 18 Nov 97 to 2 Jan 1998
Project Title:  The Airport Gate Assignment Problem using Tabu Search
Course:         CS2288
Description:    
   In this project, we study the Gate Assignment Problem (GAP)
   of allocating gates to planes arriving at the airport terminal.
   This problem arises as a sub-problem of a larger R&D project 
   investigating the GAP and related problems.

   The GAP is described as follows:
   Planes arriving at an airport are assigned gates in the terminals
   of the airport and the passengers either go into the airport or
   are transferred (connected) to other flights.  We are interested
   in finding good gate assignments so as to optimize resources and
   minimize the overall passenger movement.

   We currently have a solution to a related problem, the BAP (see 
   my other project proposal). In this project, we want to explore
   the use of TABU search in the solution of the GAP.
   
Reference: 
   1. Swee Nam's Honours Project Report
   2. BAPS V1.0 System Manual
  *3. Some information on Genetic Algorithms



Supervisor:     Leong Hon Wai
Student:        Ho Ngai Lam      (hongaila) 
Project Title:  The Airport Gate Assignment Problem 
                using Mathematical Programming
Course:         CS2288
Description:
   In this project, we study the Gate Assignment Problem (GAP)
   of allocating gates to planes arriving at the airport terminal.
   This problem arises as a sub-problem of a larger R&D project 
   investigating the GAP and related problems.

   The GAP is described as follows:
   Planes arriving at an airport are assigned gates in the terminals
   of the airport and the passengers either go into the airport or
   are transferred (connected) to other flights.  We are interested
   in finding good gate assignments so as to optimize resources and
   minimize the overall passenger movement.

   We currently have a solution to a related problem, the BAP (see 
   my other project proposal). In this project, we want to solve
   the GAP using mathematical programming.
   
Reference: 
   1. Swee Nam's Honours Project Report
   2. BAPS V1.0 System Manual
   3. Paper on GAP

Some Info:
   Will get GAP data (arrival/departure/flight-no) from internet



Supervisor:     Leong Hon Wai
Student:        Leong Hoe Wai   (leonghoe)
Project Title:  Empirical Study of Shortest Path Algorithms on Road Networks
Course:         CS2288
Description:    
   The objective of this project is to study the performance of various
   shortest path algorithms (with different implementations) on actual
   road networks. The result of this empirical research will be used
   to make recommendations for approapriate algorithm for a related
   project on the Route Advisory System.

Reference: 
  1. A book on Navigation System



Supervisor:     Leong Hon Wai
Student:        [incomplete] -- initially by Shih Chih Chuan
Project Title:  Some Applications of Clustering Systems 
Course:         CS2288
Description:    
   This project aims to investigate the use of clustering methods to 
   (i) improve network design and reliability, and (ii) obtain
   clusters of ships for a container port berth allocation problem.
   For the second application, clustering will be based on the 
   container movement matrix.

   Note: In a previous research project, we have developed a general
   Clustering System (in C on UNIX) that encompasses several well-known
   clustering methods.

Reference: 
   1. Steven Quek's MSc Thesis
   2. Book on Computer Network
  *3. Third Year Project Report



Supervisor:     Leong Hon Wai
Student:        [partial]   -- by Desmond Cheong
Project Title:  Song Arrangement Problem for a Radio Station
Course:         CS2288
Description:    
   Most of the playlist of radio staions in Singapore is now being generated
   by computer. However, the generation of these playlist does not take into
   account the mood of the program (eg. 1st song of every timeslot shld be
   fast for afternoon programms and late-nite songs can't be fast). Hence,
   evolve a rather insensitive method of generating the playlist. The program
   also does not take into consideration the popularity of certain songs and
   it also does not take into consideration the different styles of the
   different DJs. Hence... very active DJs end up playing very 'dead' songs.
   And late-nite programs end up playing a few selections of fast rocks.
   Which disturb the listening pleasure and the mood of the listeners. the
   recent songlist also does not take into account advertising time. Hence
   sometimes it will 'under-generate' songs or 'over-generate' songs..

   In my project, i would like to propose alternative algorithms to make the
   generation of playlist more personal. And hence more effective. 



Supervisor:     Leong Hon Wai
Student:        [partial] -- initially by Neo Chee Wee
Project Title:  Design of Low Power Multiplexor (MUX) 
Course:         CS2288
Description:    
   This project deals with discrete optimization algorithms for a
   binary tree decomposition problem.  This problem has application
   in the practical problem of low power design of digital circuits.
   Specifically, we want to decompose a large n-to-1 multiplexor (MUX)
   into a binary tree of 2-to-1 MUXes. The problem is to find a
   decomposition that optimizes the overall power consumption.
   (A paper describing our research work on this problem is available.)

   In this project, student will give *efficient* implementations of the
   some heuristic algorithms for the problem.
   Extensive experimental evaluation of these algorithms will be carried out.
   Possible extensions of this problem will also be explored.

Reference: 
   1. Our MUX paper