Reducing simulation costs of embedded simulation in yard crane dispatching in container terminals

• Main Author: Tang, Jiuyun
• Other Authors: Huang Shell Ying
• Format: Final Year Project
• Language: English
• Published: 2015
• Subjects: DRNTU::Engineering::Electrical and electronic engineering
• Online Access: http://hdl.handle.net/10356/63076
• Institution: Nanyang Technological University

For an NP-hard simulation-based, optimization problem, the computational costs of the embedded simulation in the corresponding optimization algorithm are likely to be substantial.The computation costs include the time and memory usage of the simulation program. The Yard Crane(YC) dispatching problem is one of the NP-hard problems which require substantial computation in order to find the optimal result. Therefore it is important to minimize the simulation costs in YC dispatching algorithms. In the MT-RBA* dispatching algorithm proposed by Xi Guo, simulation of YC operations of the entire (partial) sequence of YC jobs are carried out each time the tardiness of a (partial) sequence needs to be evaluated. In this project, two approaches proposed by Ong [4] will be examined and the main objective of this project is to reduce memory usage in the embedded simulations in the optimization algorithm for those 2 approaches. Two major problems were identified, namely excessive simulations due to problem bug and excessive use of vectors for recursive backtracking. The proposed solutions fixed the program bug, and reduced the use of vectors by replacing them with arrays. The bug-fix greatly improved the time and memory performance of both approaches in Ong’s programs. The vector reduction worsened memory performance for approach 1 but improved memory performance for approach 2. It had no time performance impact on both approaches. In conclusion, the proposed solutions in this project had overall improved the time and memory performance of Ong’s programs.