An efficient genetic algorithm for solving the quay crane scheduling problem

摘要

This paper addresses the quay crane scheduling problem (QCSP), which has been shown to be NP-complete. For this reason, a number of studies have proposed the use of genetic algorithm (GA) as the means to obtain the solution in reasonable time. This study extends the research in this area by utilizing the GA that is available in the latest version of Global Optimization Toolbox in MATLAB 7.13 to facilitate development. It aims to improve the efficiency of the GA search by (1) using an initial solution based on the S-LOAD rule developed by Sammarra, Cordeau, Laporte, and Monaco (2007), (2) using a new approach for defining the chromosomes (i.e., solution representation) to reduce the number of decision variables, and (3) using new procedures for calculating tighter lower and upper bounds for the decision variables. The effectiveness of the developed GA is tested using several benchmark instances proposed by Meisel and Bierwirth (2011). Compared to the current best-known solutions, experimental results show that the proposed GA is capable of finding the optimal or near-optimal solution in significantly shorter time for larger problems.