第一篇 绪论

第1章 绪论

1.1 生产调度管理问题

1.1.1 现代生产特点

生产是指组织将其投入转换为产出的过程,即投入一定的资源,经过一系列或多种形式的转换,增加附加价值并产生效用,最后以某种形式的产出提供给社会的过程。生产既包括有形产品的形成过程(Production & Manufacturing),也包括提供服务的过程(Operation)。根据不同的生产目的,不同的生产企业应投入不同的资源,包括劳动力、资金、土地、建筑物、机器设备、工艺装备、原材料、燃料、信息等。企业要通过自身的努力,使生产产出大于生产投入才能真正实现企业的赢利目标。为此,企业应尽可能采用最经济的生产方式提供优质的产品和服务,以消耗最少的人力、物力、财力和时间,降低成本,缩短交货期。

随着世界经济和生产的全球化,市场竞争越来越激烈,具体表现为产品和服务更新换代加快,技术含量提高,并向多样化和个性化方向发展,对产品和服务的要求也越来越高。现代生产企业具有生产环节多、协作关系复杂、生产连续性强、外部环境多变等特点。为了适应市场和行业的发展需求,在竞争中立于不败之地,生产企业就要提高生产效率、柔性和可靠性,在生产和提供高质量产品和服务的同时节约资源、降低成本、获取更高效益。企业生产的精细化与集约化管理是达到上述要求的必由之路,而其核心是生产调度管理。

1.1.2 生产调度问题

所谓生产调度(Scheduling),是以生产进度计划为依据,在现有生产设备、工艺条件和能力约束下,对生产资源在时间和空间上的调度和规划,从而确定生产路线,以达到所追求的生产目标。大部分生产调度是组合优化问题,以车间作业调度为例,其需要解决的是作业次序(工件或和加工机器的次序)和时间分配问题。

生产调度的性能指标大致可以归结为三类:

(1)最大能力指标,包括最大生产率、最短生产周期等;

(2)成本收益指标,包括最大利润、最小运行费用、最小投资、最大收益等;

(3)客户满意度指标,包括最短延迟、最小提前或者拖期惩罚等。

影响生产调度问题的因素很多,正常情况下有产品投产期、交货期(完成期)、生产能力、加工顺序、加工设备和原料可用性、批量大小、加工路径、成本限制等,这些都可称为约束条件。

现代生产调度问题主要有以下特点。

(1)复杂性:实际生产调度问题通常较为复杂,模型求解往往是NP完全问题,使得一些常规的最优化方法无能为力。

(2)动态不确定性:由于生产过程是动态的,生产环境的变化,如订单任务的改变、制造设备的异常、人员的误操作等,都会影响原先已经制定好的生产调度计划,如果继续执行原有调度计划,其效率往往会下降,有时甚至是不可完成的。因此,必须对原有的加工计划进行修订,以使其适应新的生产环境。

(3)多约束、多目标性:生产调度受生产能力、工艺条件、生产任务等多种条件约束,需要考虑资源利用率、生产成本、客户满足度、收益等多目标。

传统的调度问题有Job Shop调度、Flow Shop调度和并行机调度,这三类调度问题虽然以机械加工为背景,并且在模型的描述上经过简化,但在许多实际生产调度问题中得到了体现,有些生产调度问题实质上是由这几类调度模型混合组成的。这三类基本调度问题忽略了工件准备时间和交货期要求,假设每道工序有且只有一台机器,一台机器只能同时加工一个工件,然而实际的生产调度问题往往突破了这些假设条件,形成非传统的调度问题。如码头生产作业中的很多设备调度问题就属于非传统调度问题,以码头泊位调度为例,由于码头通常有多个泊位为船舶提供靠泊服务,因此,泊位调度问题首先属于并行机调度问题,如果考虑泊位水深及泊位长度与船舶吃水深度和船型匹配的问题,那么泊位调度问题又属于带工艺约束的并行机调度问题。另外,如果再考虑船舶柔性靠泊,即一个泊位可同时靠泊多艘船舶(船舶总长只要不超过泊位长度),这时的泊位调度问题更是突破了一台机器同一时刻只能加工一个工件的假设条件,可称为multiple-job-on-one-processor-pattern调度问题。另外,当船型较大而泊位较小时,就可能产生一艘船舶占用两个或者以上泊位的情况,此时的调度问题突破了一个工件只需一台机器加工的假设条件,可称为one-job-two-machine-pattern调度问题。码头岸桥调度问题通常也是多设备同时服务于一个作业任务的情况。

生产调度问题是一个传统研究课题,应用数学、运筹学、工程技术等领域的学者对调度问题进行了大量研究工作,20世纪50年代后逐渐形成了独立分支研究方向。生产调度的核心是建立调度模型和设计求解算法,前者包括问题建模、调度规则、目标函数等问题,后者包括问题可解性、计算复杂性、有效算法等。目前生产调度方法主要有如下几类。

(1)数学规划方法:主要包括数学规划、分支定界法等。这类方法通常基于某些简化的假设,并能产生一个最优的调度方案。其中绝大多数调度问题是NP问题,随着调度问题规模的增大,上述方法的求解难度将急剧增加,因而最优化方法往往不能适应生产实际对实时性的要求。此外,该方法大多基于理想化的假设,远不能反映实际生产环境的复杂性,而且要充分表达实际生产环境的随机性和动态性也极为困难,所以不能单独使用此类方法来解决实际的生产调度问题。

(2)启发式方法:启发式方法针对生产调度问题的NP特性,并不企图在多项式时间内求得问题的最优解,而是在计算时间和调度效果之间进行折中,以较小的计算量来得到最优解或近似最优解。比较经典的启发式方法有模拟退火算法、遗传算法、人工神经网络、禁忌搜索等。由于该方法计算量小、效率高、实时性好,因此在动态调度研究中被广泛采用。

(3)基于人工智能的方法:近年来,基于知识的智能调度系统方法和研究取得了很大发展,如针对具体问题的专家系统。专家系统作为一种较好的调度方法也存在着不容忽视的缺点:对新调度环境的适应性差,由于生产环境的高度不确定,调度目标常常是变化、动态甚至是冲突的,使得专家系统只能适应于相对稳定的系统;开发周期长,费用高;专家系统是基于知识的系统,但是人们对经验和知识的获取受到了历史条件的限制。

随着对生产调度问题研究的不断深入以及精细化生产要求的不断提高,实际生产中不确定因素及其对生产调度的影响越来越受到人们的关注。不确定条件下的生产调度也逐渐成为该领域的研究热点,目前成熟的不确定生产调度主要有适应性调度、鲁棒性调度等[1]。1.2节将重点阐述不确定生产调度的策略和方法。

1.1.3 码头生产调度

“港口是经济前瞻指标”,而码头是港口的前沿部分,是港口主要功能实现的生产单位。随着改革开放的不断深化,经济的飞速发展,我国与世界各国的贸易往来得到了长足发展,港口吞吐量也随之出现了高速增长的势头。近30年来,我国集装箱运输业发展迅猛,其吞吐量稳居世界首位。世界吞吐量前10位的港口中国占了6个席位,上海港已稳居第二的位置,并且在不久的将来有望超过新加坡港成为世界第一大集装箱港口。随着港口吞吐量的持续增长,货运需求与码头能力缺口的矛盾凸显,我国优良码头的岸线资源有限。在现有生产资源条件下如何挖掘潜力,改进码头的管理水平,提高港口吞吐能力,是码头生产调度所面临的问题。

合理的码头生产调度管理可以提高船舶的装卸效率、加速车船周转、降低货运成本、缩短货运时间。目前船舶发展逐渐走向大型化和高速化,例如,马士基海陆运输班轮公司(Maerisk Sea-land)、丹麦航运集团公司(Dannis Carrier)等世界著名集装箱运输公司经营的第七代集装箱船舶的装载能力达到了7000标准箱(TEU)以上,有些甚至高达10000TEU以上;船速达到25节(kn),有些甚至达到了40kn。船舶大型化和高速化的发展为码头生产带来了巨大的压力。同时,随着码头的建设和发展,港口间的竞争也变得越来越激烈。港口的竞争优势除来自港口的地理位置和腹地经济条件之外,港口的技术条件、作业效率和管理水平也是体现其竞争力的重要因素。要在新一轮的港口竞争中取得优势,必须使港口生产作业系统化、合理化,为船舶的装卸提供一个良好的作业平台,而实现这一目标的唯一有效途径是优化港口资源的分配与调度管理(见图1-1)。

图1-1 集装箱码头

作为物流链条上的重要节点,集装箱码头既是水运系统的集散站,又是转换运输方式的缓冲池,码头生产的主要任务是完成集装箱装卸、临时堆存、集装箱交接等基本功能。围绕这些基本功能,集装箱码头系统可分为闸门检验、堆场作业、岸边作业、港内运输等子系统。图1-2给出了集装箱码头系统的作业示意图,其中岸边作业子系统完成船舶的停靠、装卸等任务,堆场作业子系统负责集装箱的核查、堆码、提取以及暂存等任务,闸口检验子系统负责对进出港车辆和集装箱进行检验、登记等作业,港内运输子系统完成集装箱在堆场与岸边间的搬运。码头主要生产资源包括泊位(Berth)、岸边吊装设备(Quay Crane)、港内运输设备(Container Vehicle)、堆场空间(Container Yard Space)、堆场吊装设备(Container Yard Crane)、闸口检验车道(Gate Lane)以及人力资源等。集装箱码头企业可以看成一类特殊的生产企业,其生产调度是在集装箱码头作业工艺约束下,以到港船、箱、车任务计划为依据,合理分配和规划其资源的使用,完成船、箱、车的在港周转服务,获取最大效益。本书应用部分主要探讨集装箱码头泊位、岸桥、拖车、堆场空间、场桥等生产资源的调度管理问题。

图1-2 集装箱码头作业示意图

集装箱码头生产调度具有以下特点:

(1)协调性。由于码头是多种运输方式的衔接点,其生产组织涉及多个部门和机构。从外部看,码头既要和船东、货主、集疏运部门保持联系,又要同海关、港监等机构协作;从内部看,码头要协调交接箱、装卸、搬运和理箱等多工种,形成有机体,码头生产需要多部门、多工种、多环节的内外协作。

(2)动态性。码头生产组织要基于船公司、船代、货主、集疏运等部门的计划安排,而这些计划信息是动态变化的,如船期会因天气变化等改变。

(3)不确定性。码头调度涉及多种不确定因素,如船期、岸桥作业、拖车行驶时间等[2]

1.2 生产调度方法研究

生产调度管理涉及多种事先无法预料的不确定因素,必须考虑多种不确定因素才能保证生产的顺利进行,同时获取满意的调度方案。针对不确定因素和调度管理的策略主要有鲁棒性调度、适应性调度和智能性调度。

1.2.1 鲁棒性调度方案

不确定因素对生产调度目标的影响不同,调度方案对不确定因素的灵敏度也不同。针对生产中出现的不确定因素,综合考虑目标与调度方案鲁棒性之间的矛盾,制定满足实际需求的调度方案,称为鲁棒(Robust)调度,制定的方案称为鲁棒调度方案。鲁棒性调度方案在执行的时候,可以使干扰或各种不确定因素对最初计算性能指标的影响最小。如文献[3,4]采用情景分析方法,或者基于最坏情景建模,求取最优的性能指标。很显然这是一种保守或风险厌恶的做法,但很多人证明保守的方法在生产调度问题上是有益的。

生产鲁棒性调度的研究较多,如李明切等[5,6]用随机变量描述不确定作业时间,基于随机规划建立鲁棒调度模型,采用遗传算法进行寻优。Pistikopoulos[7]分析了不确定性条件下生产过程设计和调度的一体化,在生产过程最优设计中考虑了调度问题,建立了设计和调度关联的二级随机规划模型,增加生产过程的操作柔性,使生产过程在不确定环境下调度获得满意解。一般来说,对于变化频繁但幅度较小的不确定因素,只要不出现大的扰动,可考虑采用鲁棒调度方案,能获得比较满意的效果。码头生产中面临着天气、机器故障等诸多不确定性,如船舶抵港延迟、计划外船舶靠泊、装卸箱量变化、岸桥作业效率波动与故障等。Moorthy和Teo[8]利用时间约束图(Time-constrained Graph)模型估计船舶在锚地的等待时间,求解鲁棒预调度方案。周鹏飞[2] 较全面地分析了面向不确定环境的集装箱码头优化调度方案选择和不确定因素的处理方法,针对船舶抵港时间和装卸时间的随机性建立了面向随机环境的集装箱码头泊位-岸桥分配模型,旨在获得鲁棒性较强的泊位岸桥分配方案。

1.2.2 适应性调度方案

适应性调度是早期处理不确定性因素主要采用的方法,就是当不确定的事件发生之后再决定应该怎么做,根据实际情况对初始调度进行动态修改,也可以称为在线调度,这也曾经被认为是处理调度中不确定情况的最好方法,是由Maeehietto[9] 最先提出的。适应性调度可以分为重调度(Rescheduling)、滚动调度(Rolling Scheduling)、动态调度(Dynamic Scheduling)、在线调度(On-line Scheduling)等[10]。重调度又可分为连续性和周期性两类:连续性重调度要求在引起系统状态变化的事件发生时就立即进行重调度,能极快地跟踪系统变化,但其计算量极大,对于复杂系统难于满足实时性要求[11,12,13];周期性重调度是在一定生产时间间隔后进行重调度,但在时间间隔内对突发事件不敏感,时间间隔内的偏差积累可能导致系统整体性能的恶化,其优点是计算量较小,易于实现在线重调度。

滚动调度是利用滚动优化的思想,可分为Time-based(基于时间窗)和Job-based(基于工作窗)的滚动调度。针对柔性制造系统(FMS)中突发事件多采用重调度和滚动调度[14,15,16]。吴受章等[17]基于自适应控制思想,提出了一种FMS自适应调度模型。王朝晖等[18]针对缓冲库存约束调度问题,采用模糊变量处理不确定因素,建立了模糊规划模型,并提出了Lagrangian松弛求解算法。由于流程工业的复杂性和任务间的强关联性,对于突发事件的调度无法照搬FMS的动态调度方法。Time-based滚动调度很难处理存在不稳定中间产品的生产过程,但可借鉴Job-based重调度策略,如有学者提出Product-based重调度策略、实时在线调度和Reactive调度等方法[18~21] 。Honkomp等[19,20]采用动态调度系统监测生产过程中调度方案执行,并将其反馈给调度器,一旦发生参数变化(如处理时间),调度器将及时修正调度方案,从而实现鲁棒性调度。

1.2.3 智能性调度方案

基于人工智能原理来处理不确定因素,产生了智能调度,主要有专家调度系统、智能优化调度等[22]。由于智能调度可以模拟人处理生产中的不确定因素,并进行推理,做出调度决策,因而该方法在处理不确定因素方面有独特优势。人工智能和专家系统可以产生比优先规则更复杂的基于整个调度系统的启发式,并能从特殊数据结构中获取大量信息。在20 世纪80 年代后期,学者们先后开展了基于不同调度规则策略动态调度方法的研究,其共同特点是:在支持某些活动发生的资源条件具备时(称为决策点),根据系统当时所处的属性状态,决定采取何种规则(策略),确定或选择活动发生的顺序和时间,即所谓状态指导的智能调度方法。以智能调度的推理控制策略特征来划分智能调度方法,可将其分为如下几个基本类别:约束指导的搜索、启发式规则、基于计算智能技术的搜索策略、模式匹配驱动的调度等。对大规模问题限于单个专家系统的有限知识和能力,加入资源代理、任务代理及代理间的协作机制,出现了分布式调度系统。万宁[23]分析了集装箱堆场作业模式,建立了集装箱进出场智能模拟模型,分别提出了进出口箱箱位自动分配算法、基于智能模糊时间段的提箱优化策略。智能调度要解决日益复杂的调度问题,应当解决的关键问题有:

(1)调度系统的结构问题;

(2)调度问题的知识表示及有效的求解策略;

(3)调度知识获取问题;

(4)有效的调度优化算法的研究。

每种调度方法都有其优缺点。随着分布式人工智能的深入研究,基于多Agent技术的分布式生产调度方法被提出。它通过在一系列具有各自目标和自治行为能力的智能单元(Agent)之间进行协商与合作来解决复杂的生产调度问题。其优点是响应速度快、动态适应能力强、可靠性高、可扩展性强,能够处理具有分布式特点的问题且对不确定数据和知识有较好的容错能力。

1.3 不确定优化研究

具有清晰定义结构/行为系统[有时称为“硬”系统(Hardy System)]的优化方法称为确定型或清晰型优化方法,其基础是清晰的数字模型和精确的数学方法。然而随着问题的复杂,系统行为精确性和有效性随之下降,超过一定阈值,其精确性和有效性几乎变成互相排斥[24]。社会、生产和经济中的很多问题都非常复杂,常涉及多种不确定性,如事件发生的随机性、数据的非精确性、语言的模糊性等。这些不确定性因素来源于多种方式,包括测量误差、缺乏足够统计数据和理论支持、知识表达式以及人类的主观性判断或偏好等[25,26]。这些不确定性问题很难用精确清晰的数学模型或方法来分析和求解。不确定优化理论正是在这种背景下建立和发展起来的[27]

不确定优化是在不确定条件下(包括随机性、模糊性、粗糙性、模糊随机性以及多重不确定性等)优化决策的总称,随机性条件是最早开展研究的,相关学科有概率论、数理统计、信息论等,其发展较为成熟且应用广泛。随着科技发展和实际需求的增加,由于定义不清等原因造成的模糊性逐渐得到关注。1965 年L.A.Zadeh提出用模糊集理论来处理模糊不确定,模糊集合论为含糊不确定性或资料缺乏的不确定性问题的建模提供了理论基础,模糊优化理论和方法源于20 世纪70 年代Bellman和Zadeh提出的模糊决策概念和模糊建模。在传统可能性测度和必要性测度[28]的基础上,Liu等[29]进一步提出了可信性测度(Credibility)用于模糊规划决策问题。1982年,波兰数学家Pawlak提出了粗糙集理论,已被成功应用于数据挖掘、决策分析等领域。Liu[30]将粗糙变量定义为从粗糙空间到实数集的可测函数,引入了粗糙事件的信任测度Tr(Trust)丰富了粗糙规划决策理论。20世纪80年代初,邓聚龙教授提出了灰色系统理论,“灰”是指部分已知、部分未知。与随机性和模糊性相比,灰性的已知成分更少,或者说它的不确定性更高。20世纪90年代初,王光远[31]院士基于长期工程决策研究实践提出了不同于随机性、模糊性和灰性的“未确知性”。这种不确定性不在于事物本身,而在于决策者对事物真实状态和数量关系的把握程度,是主观认识上的不确定性。如果把仅含一种不确定性的信息称为一元不确定信息,那么随机信息、模糊信息、灰信息和未确知信息都是一元不确定信息。对一元不确定信息的数学表示和处理目前已有较多的研究成果。在实际系统中常存在两种甚至更多种不确定信息,对多元不确定信息的表示和处理是当今的重要研究课题,且越来越引起学者们的关注,如为描述随机性和模糊性并存问题,Kwakernaak[32,33]提出了模糊随机变量概念,并定义为从概率空间到模糊集类的可测函数。刘宝碇及其学术团队[30] [34~36] 的研究成果较有代表性。上述不确定理论与处理方法在实际领域已得到了广泛应用,也是不确定信息处理的主要依据。下面从不确定优化建模、算法及其应用的研究进行回顾。

1.3.1 不确定优化建模

对于不确定复杂问题建模的一般过程包括:首先,理解问题本身,分析问题中存在的不确定性信息以及形式(如目标、可行集和参数)和方式(如非精确的量化形式);其次,采用适当的方式描述和表达不确定信息,在此应体现出决策者的主观性(Subjection)和偏好(Preference);最后,以适当的数学工具和方法建立不确定模型。

从不确定建模的信息来看,不确定优化可有随机、模糊、粗糙、灰色、未确知、模糊随机、随机模糊等单、双重甚至多重的不确定。目前对于单重不确定优化研究和应用相对较多,而双重不确定问题的研究成果较少,且大多停留在研究层面。自从20世纪70年代模糊建模方法提出后,许多学者相继对模糊线性优化[37]、模糊动态优化[38]等进行了研究。Alvatore等[39]对粗集理论在多目标优化建模问题上进行了较为系统的研究。近年来学者们[40~42] 对灰色优化问题也逐渐开展了研究;刘开第等[43~45] 较全面地介绍了未确知数学及其建模方法,文献[46,47]探讨了未确知建模的理论和方法;刘宝碇对双重不确定优化建模问题做了部分研究[48,49]

从不确定建模的理念来看,不确定函数处理的基本途径有:

(1)从期望值角度出发,用不确定期望函数来处理原目标函数和约束中的不确定量,建立期望值模型;

(2)从机会测度角度出发,当约束中含有不确定变量且须在其确定前做出决策时,可采用允许所做决策在一定程度上不满足约束条件的原则,即只要求约束条件得到满足的机会测度不小于预先给定的置信水平;

(3)从目标机会角度出发,极大化事件实现的机会(如概率测度、可能性测度、必要性测度、可信性测度、信任测度等)。

Kall和Wallance[50]分析了随机期望值规划建模及其应用。机会约束规划由Charnes和Cooper在1959年提出,并应用到随机规划中。运用随机机会约束规划的思想,Liu等人提出了一系列模糊机会约束规划[51,52]、带模糊决策的模糊机会约束规划[53]等模型。相关机会规划由Liu[54~56] 提出,类似的研究还有模糊相关机会规划[48] 、模糊随机相关机会规划[49] 、粗糙相关机会规划[58][30]、灰色机会约束规划[40]。杨志民等[46]对未确知机会约束规划进行了较深入的探讨。

从不确定建模的结构来看,不确定优化有单目标、多目标、动态、多层等模型。单目标优化问题简单,但实际问题多为多目标[40],41]。实际动态决策问题需要用不确定优化,Liu[30]较系统地研究了不确定动态规划的三种模型(期望值动态规划模型、机会约束动态规划模型和相关机会动态规划模型)。罗党[42]深入地探讨了灰色动态建模的理论和方法。Liu[30] 探讨了多层不确定规划问题(MLP)的建模。

其他建模问题的相关研究:对于子系统间耦合较强的系统,Serrano[57]提出了一种图论方法来评价约束集合的接近程度;Lewis等人[58] 采用鲁棒性思想处理子系统之间的耦合关系,在子系统间的约束条件发生冲突时利用博弈论模型加以平衡;Lottaz[59]提出解空间一致性的概念,采用解空间代替单个设计解,可以在一定程度上避免冲突,但是它只能处理代数形式的约束条件;张少彤等[60]基于约束网络协调模型对一种在产品设计中的多学科协调问题进行了建模,采用区间形式描述参数的不确定性信息,将区间算法与基因算法相结合实现了通用的一致性模型的求解框架。但上述方法都不适合处理过于复杂的约束耦合关系,真正的多系统协同运作方法应体现为一个“十”字交叉模式,即从优化管理早期开始,不仅需要按并行思想考虑以时间先后顺序划分的各种“或”之间的影响,还需要考虑某一时刻所涉及的多领域间的耦合关系,不断检测运作中的潜在冲突,避免出现大的失误,在一定程度上缓和部门之间计划的矛盾。

1.3.2 不确定优化算法

不确定优化模型的求解思路是将其转化为清晰模型或易于求解的形式。模型转化首先要考虑模型解的形式和特性(如最优解和满意解),通常取决于决策者对问题的理解和要求;然后,基于数学原理和方法将其转化为等价或近似的模型;最后根据等价模型设计合适的算法,如启发式算法(Heuristic Algorithm)、智能优化算法、遗传算法(Genetic Algorithm,GA)、模拟退火算法(Simulation Annealing,SA)、禁忌搜索(Tabu Search,TS)等。

常用模型转化方法有两种:

(1)将不确定函数按照转化规则(如最不利规则)用近似确定性函数来代替;

(2)利用神经网络等方法逼近不确定函数,将其代入模型来求解。

近似神经网络产生的基本步骤如下:利用不确定变量相应的模拟(Monte Carlo模拟、模糊模拟、粗糙模拟、模糊随机模拟等)产生神经网络训练的样本;利用样本训练神经网络,产生不确定函数的近似神经网络。刘宝碇[61]探讨了不确定函数的模拟方法。

通常不确定优化问题都较为复杂,且在模型转化和模拟时常伴有非线性、非连续性等问题,因此不确定优化求解常须采用启发式算法以及一些智能算法。王文平[41] 研究了灰线性规划问题的满意度求解方法。学者们[40],[62~69] 分别讨论了基于遗传算法求解不同的模糊规划问题。罗党[42] 探讨了灰色动态规划求解方法。

1.3.3 不确定优化应用

一种理论与实际应用结合得愈紧密则其生命力愈强,不确定优化在理论上涵盖了经典规划、随机规划、模糊规划等研究内容,其应用范围宽广。事实上,现实世界中绝大多数优化问题或多或少含有不确定因素,只是由于处理上的困难和不便在很多场合下不得不将其简化,化多重不确定性为单重不确定性,化不确定性为确定性。从辩证的观点来讲,不确定性是绝对的,确定性是相对的。[70]

不确定优化有着广阔的应用前景和现实意义,不确定优化已被应用到诸多领域,如水库调度[27] 、生产过程[27] 、存储系统[71]、资金预算[72,73]、网络优化[74]、车辆调度[175]、作业排序[76,77]、关键路径问题[27] 等;顾幸生[66]对具有不同交货期窗口的Flowshop提前/拖期调度建立了模糊模型;文献[78]系统地分析了不确定条件下的生产调度建模和优化方法;李文华等[79]给出了不确定网络优化原则及一般方法,建立了PERT网络工期压缩、最优工期灰色线性规划模型;Alvatore等[39] 系统地分析了粗集理论在多标准优化决策中的应用。灰色关联分析在水利水电规划方案选择[80]、质量综合评判[81]等领域也得到了广泛的应用,李炜[82]将未确知规划方法应用到了采购优化问题中。

1.4 码头生产调度研究

集装箱码头优化调度研究[83~91] 可分为闸门及港内车辆调度、泊位及岸桥调度、堆场箱位及场桥调度和码头资源协调管理。

1.4.1 闸门及拖车调度

码头闸门车道分配问题相对简单,对其研究也较少,Lai和Leung[92]对闸门资源分配问题有过相关研究,运用随机排队模型来模拟车道分配策略以减少车辆通闸时间。

港内搬运是岸边作业与堆场作业的衔接。港内车辆调度是港内搬运畅通的关键,及时准确完成港内搬运任务,减少空驶率和保持交通顺畅是其主要目标。集装箱码头常用港内搬运机械有铲车、集车、跨越车、自动导航车辆(AGV)等。港内车辆调度研究包括车辆分配和路径选择。学者们[93,94]针对港内车辆调度问题建立了网络优化模型,通过组合运输任务最小化空驶距离。此外,学者们[89,[95~97] 分别从交通控制、网络优化等角度利用整数规划和启发式算法等来优化车辆分配和路线选择,Baker[98]分析了跨运车作业对堆场装卸设备运作效率的影响,Kim和Bae利用整数规划和启发式算法以船舶延误时间和AGV车辆消耗时间最小为目标为待托运箱分配AGV车辆,Vi s等利用网络优化模型来确定任务要求约束下的自动导航车辆量,吕显强等[100]利用整数规划来优化港内车辆调度。

1.4.2 泊位及岸桥分配

泊位是码头重要资源,其分配管理是码头服务性能改善的关键。泊位分配的主要影响因素有:

(1)船舶相关信息,如船期计划、吨位、装卸箱量等;

(2)岸边资源情况,如水深、泊位数量、起吊设备配置等。

由于来港船舶数量及装卸需求的不均衡性和装卸效率等因素的不确定性使得来港船舶较多时,船舶不可避免地要排队等候,导致船舶滞港和压箱;当来港船舶较少时,造成泊位空闲、设备利用不足。如果泊位分配不合理将会造成巨大的经济损失,通常泊位分配标准有最小化船舶等待、最小化泊位相应堆场距离、最大化泊位利用率等。针对泊位分配问题,Edmond等[101]较早利用排队论模型来优化码头泊位分配。基于先来先服务(FCFS)的策略,Lai和Shih[102]提出了一个泊位分配的启发式算法,并对不同分配标准(船舶平均等待最小、平均停靠最小和平均泊位利用率最大)下的分配方案进行分析。针对军港泊位分配的特权舰和停泊换位特点,Brown等[103,104]以最大化船舶在港效益为目标为到港船舶分配泊位。Chen和Hsieh[105]利用时空网络模型辅助优化泊位分配,模型考虑了船舶在港、到港和离港时间,将问题转化为边约束的网络模型,并开发了分支定界的求解算法。Legato[106]建立了船舶到港和离港、泊位作业的排队网络模型以优化分配码头泊位。Imai等[107,108]以最小化船舶等待为目标,用非线性整数规划模型来模拟静、动态码头的泊位分配问题。Nishimura等[109]进一步扩展了上述模型到不同水深泊位的情形,并设计了遗传算法来求解模型。Imai等[110]研究了不同服务优先级船舶的泊位分配问题。前面提到的泊位分配研究都将码头岸线划分成若干独立泊位,另一类泊位分配方法则将码头岸线看成连续的水边线,只要有满足到港船舶物理条件(水深和长度)限制的位置就安排靠泊,该问题类似“背包”问题。Lim[111]将其转化为“背包”问题,并基于图论提出一种启发式算法,该研究假设船舶停靠时间固定。Kim等[112]用混合整数规划模型模拟了船舶在岸线的停靠位置和时间,并用模拟淬火算法求解近似最优解。另外,Li等[113]将泊位分配问题看成一个可同时处理多任务的处理机调度问题,并假定所有船舶已在港等候靠泊,建立了以船舶在港时间最小为目标的模型,提出了启发式算法。类似地,Guan等[114]也将泊位分配问题看成处理机调度问题,其优化目标是最小化带权重的任务完成时间。

岸边起吊设备(岸桥)分配和起吊计划直接影响船舶装卸效率,其影响因素有:

(1)船舶相关信息,如停靠泊位、船舶计划等;

(2)设备相关信息,如桥吊数量、港内集卡等。

Daganzo[115]将船舶的装卸任务划分成若干吊装区,并用整数规划模型求解静态桥吊分配问题,其目标是船舶等待时间最小。Peterkofsky和Daganzo[116]将岸桥分配作为开放生产计划问题来研究,建立了整数规划模型,并用分支定界法求解模型。Bǒse等[117]以岸桥等待时间最小为目标,针对岸边有缓冲区的集装箱码头建立了仿真模型,在给定装卸箱序列要求下为桥吊配备跨越车确定其作业序列。

1.4.3 堆场箱位场桥分配

码头通常要求船舶抵港前出口箱要进港以待装船,船舶离港后才允许提进口箱。因此,码头堆场实际上是船舶装卸与内陆提交箱的缓冲区和装卸船与提交箱的组织区,是码头协调作业的关键环节。堆场箱位分配影响因素较多,包括船舶停靠位置、堆场分块密度、堆场内箱分布以及进出场计划等。通常可将堆场箱位分配分两阶段:阶段1 是堆场区段级分配,又包括①确定分配给船舶的堆场区段和②确定堆存到堆场区段的箱;阶段2 是箱位级分配,即为进场箱确定具体箱位。针对阶段1 问题,Kim等[118]考虑出口箱分组堆垛策略,以水平运输距离和堆场吊装成本最小为目标建立了问题②的二次规划模型。Kim和Park[119]以装船后释放的堆场空间最大和箱位到船距离最小为目标,建立了出口箱流问题①的混合整数规划模型,并设计了拉格朗日松弛求解算法。

集装箱堆场常用起吊设备有轮胎式龙门吊、轨道式龙门吊、叉车等。由于堆场起吊设备投资大和使用率高,是堆场优化调度的瓶颈。堆场起吊设备调度包括:

(1)确定起吊设备在堆场区段内作业序列;

(2)起吊设备在堆场区段间的调度。

针对出口箱流,Kim[120]研究了起吊设备在堆场区段作业序列的问题。Kozan和Preston[121]利用整数规划模型来减少起吊设备的最大作业时间。

1.4.4 码头资源协调管理

码头资源协调优化研究主要通过模拟方法对系统运行参数和资源分配策略进行优选。Gambardella等[122]、Ramani[123]、Yun和Choi[124]、Merkuryev等[125]分别利用模拟技术分析了集装箱码头系统的运行参数和资源分配策略;相对于要消耗大量CPU时间的模拟方法,也有学者利用分析模型对码头作业流程进行评价,为码头资源协调调度管理服务;Kozan[127]对比了模拟与系统分析方法,结果显示这两种方法结果具有95%的相似性,但系统分析法需要较长期的数据积累;Kozan[128] 建立了集装箱码头的仿真模型,并以箱在港处理和周转用时最小为目标分析了不同类型的码头系统,模型可用于集装箱码头的投资分析;杨静蕾等[91]分析了上海外高桥集装箱码头作业系统,建立了锚地、泊位、桥吊、龙门吊和集卡的动态多级排队网络,运用仿真技术模拟了集装箱码头作业系统,通过输出指标分析了最优机械配比和桥吊台数;刘建军等[129]探讨了枢纽港集装箱运输的广义费用函数,提出了基于广义费用的集装箱运输组织优化模型。

武汉交通科技大学开发了集装箱码头装卸系统的模拟仿真模型。真虹[130]开发了港口生产调度和评价的动态图形仿真系统,针对码头的前沿部分对调度方案进行了比较分析。彭传圣等[131,132]基于排队论构建了天津港集装箱码头的模拟模型和天津港改扩建集装箱码头的计算机模拟模型,利用面向对象仿真语言AUDITION开发了集装箱码头模拟系统。