Hybrid Evolutionary Strategy Optimization for Port Tugboat Operation Scheduling

Tugboat operation is an important part of port operation system, and efficient tugboat operation scheduling and planning has a direct and significant impact on which vessels come in or out of the port in time. It exits in the tugboat operation that more than one tugboat simultaneously provide one vessel with the service of tug at the same moment of time, so tugboat operation scheduling is a kind of unconventional scheduling problem. Optimization of tugboat operation scheduling is studied, both tugboat operation process and the characteristic of tugboat scheduling are analyzed, and combined with multiprocessor tasks scheduling theory, a kind of general set multiprocessor tasks scheduling based on identical processors is presented. This scheduling problem has the characteristic of both parallel processors and dedicated processors of multiprocessor tasks scheduling problem. Tugboat operation scheduling is optimized by a hybrid evolutionary strategy algorithm, in which a kind of encoding based on multi-dimension integer is used to represent the mapping relation between the tugboat assignment and the coming vessels. Moreover, a local search strategy based on crossing-over is employed to improve the search performance of hybrid evolutionary strategy algorithm. The computational results prove that hybrid evolutionary strategy algorithm can effectively solve the tugboat operation scheduling problem.