英语原文共 5 页，剩余内容已隐藏，支付完成后下载完整资料

2009年第三次国际研讨会的智能信息技术应用

混合进化策略优化港口拖轮作业调度

刘志雄

机械与自动化学院

武汉科技大学

中国武汉

博士后研究中心

天津港（集团）有限公司

中国天津

运输安全工程研究中心（教育部）武汉理工大学

中国武汉

电子信箱：lzx_brad@126.com

摘要

拖轮作业是港口作业系统的重要组成部分，高效的拖轮作业和规划对船舶即是进出港口有着直接而显著的影响。它存在于一个以上拖轮同时为一艘船舶提供拖轮服务的拖轮作业之中，因此港口拖轮作业调度是一种非常规的调度问题。本文对港口拖轮作业调度优化进行了研究，对两拖轮作业过程和拖轮调度的特点进行了分析，并结合多处理器任务调度理论，提出了一种于相同的处理器的通用多处理器任务调度模式。这种调度问题兼有并行处理器和多处理器任务调度问题的专用处理器的特点。港口拖轮作业调度的混合进化策略算法的优化，即将一种基于多维整数编码用来代表拖轮作业和即将到来的船只之间的映射关系。此外，一个局部搜索策略的基础上跨越的混合进化策略算法，以提高搜索性能。计算结果表明，混合进化策略算法可以有效地解决了拖轮作业调度问题。

关键词：进化策略算法；多处理器任务；拖轮作业；调度；优化

1. 引言

随着港口运输业的发展，港口之间的竞争也越来越强，港口的需求越来越高。为了吸引更多的船舶停泊港口，提高港口的经济效益，港口经理需要调整港口作业系统和提高作业效率。港口拖轮作业系统是港口生产系统的重要组成部分，它是在港船舶的第一个服务站，并直接影响到船舶码头是否及时装卸货物。

在港口，拖船提供的拖轮服务包括移动船舶，船舶靠离泊码头等。根据船舶吨位和长度，分配到船舶的拖轮在数量和马力上必须满足船舶的需求。例如，如果船舶较小，一艘较低马力的拖轮就足够拖动船舶。如果船舶较大，所需要的大马力拖轮不止一个。这样的作业有一个以上的拖轮同时同步工作并且具有多处理器任务的特性。在港口拖轮的数量和类型是有限的，因此有效的调度和规划港口所有的拖轮是非常重要的，这将直接影响到船舶在港的时间。

目前，研究港口拖轮作业不多，已有的研究大多集中在拖轮配置仿真与优化^{[ 1 ] [ 2 ] [ 3 ] [ 4 ]}。拖轮配置问题应该包含拖轮调度问题本身，拖轮优化配置应根据拖轮调度优化。然而，以往的研究没有考虑拖轮调度优化问题。拖轮调度问题是一类特殊的非常规的调度问题，并基于拖轮作业的特点，它是一种多处理器任务调度问题。在本文中，我们对拖轮调度问题进行了研究并分析了拖轮作业的特点。文章结合多处理器任务调度理论，介绍了一种基于相同处理器的多处理器任务调度集合。使用进化策略算法（ES）来优化拖轮调度问题，即一种基于多维整数编码是用来描述拖船和容器之间的关系的算法。同时，提出了一种基于交叉互换的局部搜索策略，以提高进化策略算法的优化性能。

论文的其余部分是组织如下：第2节分析了拖轮调度的特点，提出了一种基于相同处理器调度的通用多处理器任务集合。第3节介绍了拖轮调度混合进化策略算法。第4节介绍了混合进化策略算法的实验结果。一些结论性的评论是在第5节。

二、拖轮调度问题分析

A、一般多处理器任务调度集合

多处理器任务调度问题是在同一时刻，同一任务同时处理多个处理器。它也被称为1-job-on-r-machine模式调度（r是一个正整数）^{[ 5 ]}和1-job-on-multiple-machine模式^{[ 6 ]}调度。多处理器任务调度问题主要包括两种类型，并行处理器和专用处理器。对于并行处理器，每个处理器都能够处理任何任务。在一般情况下，也就是说，所有的处理器是相同的。此外，每一个任务需要同时工作的处理器的数量是固定的。在专用的处理器环境中，每一个处理器可以有不同的能力，并且一个多处理器的任务可以由一组同时执行的处理器执行。对于专用处理器，如果每一个处理器对应于每一个任务的子集，包括处理器的子集并且每个处理器的子集都可以处理任务，它的存在使得一个任务可以对应于几个处理器子集。在那时，这个调度问题是类似于作业车间调度的柔性路径。在多处理器任务调度的文献中，这个问题被称为一般的多处理器任务调度问题^{[ 7 ] [ 8 ]}。同时，这个调度问题也被称为专用处理器的动态分配问题^{[ 9 ]}。目前，很少有研究集中在这个调度问题方面。

在一般的多处理器任务调度问题集合中，通常假定每个处理器是不同的，每个处理器的数量是唯一的。如果上面的假设项是广义的，每个处理器是多重的，相同的处理器可以是几个。在本文中，这个问题被称为基于相同处理器和隶属于它的拖轮调度问题的一般多处理器任务集合。

B、基于通用多处理器任务集合的拖轮调度

1）拖轮调度的特性

一般来说，对于港口拖轮作业，拖轮的数量和类型是根据船舶的长度尺寸分配到船舶。例如，一个港口有六种类型的拖船，包括1200马力，2600马力，3200马力，3400马力，4000马力和5000马力的拖船。各种拖轮的数量如表1所示，拖轮和船舶长度尺寸的映射关系如表2所示。

表格 1: 拖轮类型和数量

表格 2：拖轮和船舶长度尺寸的映射关系

从以上拖轮作业特点可知，如果将拖轮作为处理器而将船舶作为任务，拖轮调度问题属于基于相同处理器的通用多处理器任务集合。

1. 通用多处理器任务的特点

从表2中可知，首先，除了长度小于100米的船舶只需要一艘拖轮，其他种类的船舶也只同时需要两艘拖轮。所以港口拖轮作业具有多任务的特性。其次，不同长度的船舶对应的拖轮集合也是不同的，对于一艘船舶，指派拖轮的数量应多于表2中映射关系规定的数量，所以一艘船舶可以对应多个不同拖轮子集，并且拖轮作业有通用多处理器任务集合的特性。

(2)相同处理器的特点

从表1中可知，因为拖轮的数量都大于1，所以拖轮调度具有相同处理器的特点。对于一艘船舶，相应的拖轮集合有多个相同的拖轮。当一艘船舶需要两艘拖船时，当拖轮马力满足船舶的要求时，两艘拖轮可以是相同的或是不同的。

通过多处理器任务调度理论可知，通用多处理器任务调度集合是在专用的处理器基础上建立的。对于专用的处理器，每个处理器是不同的，唯一的。此外，每个任务都由不同的处理器同时执行。然而，对于并行处理器，所有的处理器是相同的，所需的处理器的数量是固定的。因此，拖轮调度同时具有并行处理器和专用处理器的多处理器任务调度特点。

2）基于相同处理器的多处理器任务调度描述

基于相同处理器的多处理器任务调度可以描述如下。有m个不同的处理器M₁，hellip;， M_m和N个任务，处理器Mi（i=1,2,hellip;m）的数量记为l i（i=1,2,hellip;m）,所有处理器数量和记为。每个专用处理器集可以记为，所有处理器的整体处理器集可以记为。每一个任务i（i=1,2,hellip;n）对应于一个处理器集set_i，设定的集set_i包括多个子集set_ij。子集set_ij包括set_i里的部分或者所有处理器。任务i必须同时被子集set_ij里面的所有处理器处理。因此，。多个任务不能同时被一个处理器处理。优化目标是为了最大限度地减少所有任务的最大完工时间，相同处理器在多个任务之中不采取计划时间。任务i的处理时间记为t_i ，等候时间记为W_i，任务的完成时间记为C_i，所有任务的完成时间记为f。所以f可以表示如下。

(1)

如果F代表优化目标，那么F可以表示如下。

(2)

多处理器任务调度的复杂性已经有Maciej drozdowski ^{[ 9 ]}介绍，他指出，几乎没有多处理器任务调度问题使用伪多项式时间算法。大多数多处理器任务调度问题是NP—完全问题，特别是当处理器的数量大于或等于3时。

因此，基于以上对拖轮调度问题的分析，船舶采取第一服务第一的原则解决拖轮子集的分配问题，（mu; lambda;）—基于多维整数编码的进化策略算法是用来优化拖轮调度问题的。此外，方程（2）可以被视为拖轮调度以及所有船舶最大完工时间最小时拖轮调度优化目标的适用函数。

1. 混合进化策略算法的拖轮调度
2. 编码表示

对于拖轮调度问题，需要解决分配不同船舶不同类型和数量的拖轮的问题。本文中采用了一种基于多维整数的编码方法。

在表1中，六种拖船，包括1200马力，2600马力，3200马力，3400马力，4000马力和5000马力，分别记为整数1，2，3，4，5，6。不同种类的船舶根据表格1的船舶长度分别记为S1，S2，S3，S4和S5。因此，表格2中船舶和拖轮的映射关系约束条件可以描述为表格3。

表格 3：约束条件

如果假定所有船舶需要分配拖轮的指定数量是n，则编码显示如表4。

表格 4：基于多维整数编码

在表格

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[147965]，资料为PDF文档或Word文档，PDF文档可免费转换为Word