Improving Computational Performance of Simulation-based Heuristic Algorithms for Job Sequencing

摘要

In many simulation-based optimization algorithms, substantial amount of time is often required in the simulation experiments to evaluate the solutions to the problem. In some heuristic or metaheuristic algorithms a significant number of revisits to the same solutions are made when the search converges. We use the ATCRSS heuristic for job sequencing problems as an example to investigate two ways of implementing a dictionary to memorize the simulation results. The objective is to eliminate repeated simulations to improve the computational performance of the algorithm. Our experiments show that the saving in computational time is comparable between hash table and TRIE. For sequencing 10 to 60 jobs the saving is between 20% and 30%. In addition, hash table is more efficient in memory usage than TRIE in our tested cases. We also suggest that hash table is a more general way of implementing the dictionary for other heuristic algorithms.