Simulated annealing-based ant colony algorithm for tugboat scheduling optimization.

*(English)*Zbl 1264.90189Summary: As the “first service station” for ships in the whole port logistics system, the tugboat operation system is one of the most important systems in port logistics. This paper formulated the tugboat scheduling problem as a multiprocessor task scheduling problem (MTSP) after analyzing the characteristics of tugboat operation. The model considers factors of multianchorage bases, different operation modes, and three stages of operations (berthing/shifting-berth/unberthing). The objective is to minimize the total operation times for all tugboats in a port. A hybrid simulated annealing-based ant colony algorithm is proposed to solve the addressed problem. By the numerical experiments without the shifting-berth operation, the effectiveness was verified, and the fact that more effective sailing may be possible if tugboats return to the anchorage base timely was pointed out; by the experiments with the shifting-berth operation, one can see that the objective is most sensitive to the proportion of the shifting-berth operation, influenced slightly by the tugboat deployment scheme, and not sensitive to the handling operation times.

##### MSC:

90C59 | Approximation methods and heuristics in mathematical programming |

90B90 | Case-oriented studies in operations research |

90B35 | Deterministic scheduling theory in operations research |

PDF
BibTeX
XML
Cite

\textit{Q. Xu} et al., Math. Probl. Eng. 2012, Article ID 246978, 22 p. (2012; Zbl 1264.90189)

Full Text:
DOI

##### References:

[1] | K. C. Ying and S. W. Lin, “Multiprocessor task scheduling in multistage hybrid flow-shops: an ant colony system approach,” International Journal of Production Research, vol. 44, no. 16, pp. 3161-3177, 2006. · Zbl 1159.90409 · doi:10.1080/00207540500536939 |

[2] | H. Xuan and L. X. Tang, “Dynamic hybrid flowshop scheduling problem with multiprocessor tasks,” Computer Integrated Manufacturing Systems, vol. 13, no. 11, pp. 2254-2288, 2007. |

[3] | Z. Liu, “Hybrid evolutionary strategy optimization for port tugboat operation scheduling,” in Proceedings of the 3rd International Symposium on Intelligent Information Technology Application (IITA ’09), pp. 511-515, November 2009. · doi:10.1109/IITA.2009.490 |

[4] | Z. Liu, “Port tugboat operation scheduling optimization considering the minimum operation distance,” Journal of Southwest Jiaotong University, vol. 46, no. 5, pp. 875-881, 2011. · doi:10.3969/j.issn.0258-2724.2011.05.027 |

[5] | S. Wang and B. Meng, “Resource allocation and scheduling problem based on genetic algorithm and ant colony optimization,” in Proceedings of the 11th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD ’07), vol. 4426 of Lecture Notes in Computer Science, pp. 879-886, Nanjing, China, 2007. |

[6] | S. Wang, I. Kaku, G. Chen, and M. Zhu, “Research on the modeling of Tugboat Assignment Problem in container terminal,” Advanced Materials Research, vol. 433-440, pp. 1957-1961, 2012. · doi:10.4028/www.scientific.net/AMR.433-440.1957 |

[7] | Z. X. Liu and S. M. Wang, “Research on bi-objectives parallel machines scheduling problem with special process constraint,” Computer Integrated Manufacturing Systems, vol. 11, no. 11, pp. 1616-1620, 2005. |

[8] | L. C. Dong, Z. Q. Xu, and W. J. Mi, “The dynamic tugboat schedule based on particle swarm algorithm combined with genetic operators,” Mathematics in Practice and Theory, vol. 42, no. 6, pp. 122-133, 2012. |

[9] | Z. X. Liu and S. M. Wang, “Research on parallel machines scheduling problem based on particle swarm optimization algorithm,” Computer Integrated Manufacturing Systems, vol. 12, no. 2, pp. 183-296, 2006. |

[10] | H. R. Boveiri, “ACO-MTS: a new approach for multiprocessor task scheduling based on ant colony optimization,” in Proceedings of the International Conference on Intelligent and Advanced Systems (ICIAS ’10), pp. 175-179, June 2010. · doi:10.1109/ICIAS.2010.5716203 |

[11] | M. Dorigo, G. DiCaro, and L. Gambardella, “Ant algorithm for discrete optimization,” Artificial Life, vol. 5, no. 2, pp. 137-172, 1999. |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.