带有安全距离约束的无交叉岸桥调度问题

港口码头连续泊位-岸桥-集卡调度建模研究黄恺（中交上海航道勘察设计研究院有限公司，上海 200120）摘　要：本文基于港口码头连续泊位-岸桥-集卡调度构建研究模型，目标为降低物流作业总成本，以某码头实际运行情况为例进行分析，构建整数线性规划数学模型，运用ILOG CPLEX对码头实际运行数据进行求解，得出三者综合作用下最优解，并将其与实际运行情况对比，证明了该模型运行的准确性、有效性。

关键词：集装箱码头；连续泊位；岸桥；集卡；ILOG CPLEX中图分类号：U651 文献标识码：A 文章编号：1006—7973（2021）02-0119-02集装箱码头是当前海上运输的重要依托工具，码头运行的基础资源主要为泊位、岸桥和集卡。

为了提升集装箱码头的运行效率，要求优化泊位、岸桥和集卡，实现三个作业环节中的有效调度，促进三项资源的协同调度，提升港口的综合运行效率。

1集装箱码头连续泊位-岸桥-集卡调度建模研究研究中将时间类优化目标转化为以作业形式呈现的目标，构建数学模型，目的在于实现作业成本最优化。

模型构建中运用码头运行周期、码头可用集卡总数、集卡运输集装箱一次的往返时间、船舶最晚离港时间、船舶等待泊位单位作业时间成本、集卡单位作业时间成本等。

本次研究选取我国某码头为例进行分析，以48h为一个周期进行研究[1]。

目标函数构建中要求考虑船舶在港时间成本、单位岸桥单位作业时间成本、单位岸桥等待集卡单位时间成本、单位集卡单位作业时间成本、单位集卡等待岸桥单位时间成本、船舶到港时间、延误船期单位时间成本、船舶实际离港时间、岸桥为船舶服务时间、集卡为船舶服务时间、服务于船舶岸桥等待集卡时间、船舶待卸集装箱数量、船舶待装集装箱数量等[2]。

结合集装箱船舶长度以及集装箱装载量设置相应的安全距离。

为了达到最佳的物流运行效果，在规定的时间内设置集装箱装卸量、集装箱船舶的在港时间、集卡作业效率、岸桥作业效率等参数，使得不同的参数能够达到最佳配比[3]。

基于改进粒子群算法的岸桥调度问题孙思韵【期刊名称】《物流工程与管理》【年(卷),期】2015(000)007【摘要】岸桥调度作为集装箱码头生产作业的一个核心环节，其工作效率将直接影响集装箱船舶的船期。

合理安排岸桥作业，不仅能减少作业时间，保证船舶船期，更能提高码头装卸效率，提升码头竞争力以及维护船东与货主的利益。

文中针对集装箱码头岸桥调度问题进行研究，根据现有文献以及调研结果建立符合实际的混合整数规划模型，考虑到岸桥的干扰约束以及作业单元的作业顺序约束，并利用改进的粒子群算法进行求解。

%Quay crane scheduling at the quay side is a crucial operational process in container terminals,whose efficiency can directly affect the entire navigation time of containerships.The feasible allocationof quay cranes ( QC) can not only decrease the operational time and guarantee ship's navigation requirement but improve handling efficiencyas well, thus upgrading port competitiveness and ensure the legal rights of ship owners and cargo holders.This paper focused on the study on quay crane scheduling problem ( QCSP) .The related research and surveys are carried out in this paper on quay crane operation,and a mixed-integer programming model is presented,which satisfies the actual operational situation.Herein,various practical constraints are carefully taken into account such as the QC interference constraint and the task precedencerule.And the improved particle swarm optimization ( PSO) is proposed in this paper.【总页数】4页(P205-207,166)【作者】孙思韵【作者单位】上海海事大学物流工程学院，上海 201306【正文语种】中文【中图分类】F253【相关文献】1.基于改进粒子群算法的大规模定制生产调度问题研究 [J], 杨文伟;樊蓓蓓;李聪2.基于改进粒子群算法的航班降落调度问题研究 [J], 马英钧;孙晓娜;赵东方3.基于改进粒子群算法的车间作业调度问题研究 [J], 乔佩利;马丽丽;郑林4.基于改进粒子群算法的岸桥调度问题 [J], 孙思韵5.基于改进粒子群算法求解分布式多工厂生产调度问题 [J], 王仕存;唐敦兵;朱海华;聂庆炜;潘俊峰;杨雷因版权原因，仅展示原文概要，查看原文内容请购买。

连续型泊位与岸桥配置的多目标问题求解汤齐;滑建辉【摘要】泊位和岸桥作为集装箱码头的紧缺资源,在港口实际运作中起着至关重要的作用,其能否高效率协调工作直接影响码头装卸作业效率和港口对外信誉. 针对集装箱码头连续型泊位和岸桥的协调调度以及如何缩短船舶在港中逗留的时间并减少港口岸桥总工作时间等问题,提出最小化各船舶在泊位中的装卸时间和最小化岸桥总工作时间的多目标函数的连续泊位和岸桥调度优化数学模型,采用多目标遗传算法对该优化模型进行求解,并通过数据实验验证了该模型的可行性和有效性.%As the scarce resource in container terminal, berth and shore bridge coordination scheduling quality directly af-fects the efficiency of terminal handling and port foreign credit.For container continuous berths and quay crane cooperative scheduling problem,shortening the time of stay in port in the ship, this paper put forward berth and quay crane scheduling optimization model in order to reduce the working of ships at berth quay handling time and total working time of the objec-tive function, moreover, proposing adaptive genetic algorithm to solve the mathematical model and to demonstrate the feasi-bility, effectiveness of the algorithm through the experimental data.【期刊名称】《天津大学学报（社会科学版）》【年(卷),期】2016(018)001【总页数】6页(P44-49)【关键词】连续型泊位;岸桥;多目标遗传算法;联合调度【作者】汤齐;滑建辉【作者单位】天津工业大学管理学院,天津300387;天津工业大学管理学院,天津300387【正文语种】中文【中图分类】TP391;U691集装箱码头是国际物流运输的重要节点，连接国与国之间的贸易往来，通过合理的配置港口自身的资源，可以减少船舶到港排队时间和装卸货物的时间，提高自身的核心竞争力。

第10卷 第4期 工程研究——跨学科视野中的工程10 (4): 373-3802018年8月JOURNAL OF ENGINEERING STUDIES Aug., 2018收稿日期: 2018-01-24; 修回日期: 2018-03-19基金项目:国家自然科学基金资助项目（71471110、61540045）；上海市科委创新项目（16040501500、16DZ1201402、14170501500）；上海市重点学科（J50604）；陕西省社会科学基金项目（2015D060）作者简介:陈 宁（1993-），男，硕士研究生，研究方向为物流运作与优化。

DOI: 10.3724/SP.J.1224.2018.00373基于混合流水车间调度的自动化码头调度研究陈 宁, 梁承姬(上海海事大学 物流研究中心，上海 201306)摘 要: 为提高自动化集装箱码头的装卸效率，合理高效地利用设备资源，针对双小车岸桥与AGV 的联合调度问题，综合考虑了岸桥作业过程中的不交叉作业、集装箱优先关系等现实约束，分析了中转平台的容量限制。

采用基于混合流水车间调度的方法，建立以作业完工时间最小化为目标的三阶段混合整数规划模型，运用遗传算法（GA ）对模型进行求解，获得集装箱任务的设备分配（QC 和AGV ）和处理顺序的调度方案。

最后，对比遗传算法（GA ）与粒子群算法（PSO ）对模型求解的优劣性，算例结果表明，遗传算法得到的调度结果在完工时间与运行速度上更优。

关键词: 双小车岸桥；中转平台；AGV 调度；混合流水车间调度；遗传算法中图分类号: U691.3 文献标识码: A 文章编号: 1674-4969(2018)04-0373-08引言在现代航运市场竞争日益激烈，全球化进程不断加快的情势下，为降低运营成本，集装箱船舶发展转向大型化趋势。

传统集装箱码头设备装卸效率较低，故障率高，无法有效满足超大型船舶的装卸要求，对班轮船期造成影响。

基于改进遗传算法的泊位岸桥协调调度优化杨劼;高红;刘涛;刘巍【摘要】针对集装箱码头资源调度不合理造成资源浪费的问题,在考虑岸桥装卸成本的基础上,以在港集装箱船总的作业成本最小为优化目标,建立了基于非线性混合整数规划的泊位岸桥协调调度优化模型.为使模型更加接近码头操作的实际情况,模型假设船舶装卸时间依赖于为其分配的岸桥数.采用基于可拓关联函数的改进遗传算法对模型进行求解.改进算法强调了不可行解的重要性,用可拓关联度来衡量种群中不可行解的优劣程度,通过在种群迭代中始终保持一定数量的不可行解来维持种群多样性,从而克服传统算法局部搜索能力较差的缺陷.数值实验验证了模型和算法的可行性和有效性,与不考虑岸桥装卸成本的模型相比,能够有效减少港口资源的浪费.%A strategy for integrated berth and quay-crane scheduling was proposed to cope with unreasonable allocation of port resources in container terminals.First,a nonlinear mixed integer programming model which aims at minimizing the port operational cost was presented.And the loading and unloading cost of quay-crane was considered in the objective of our model.To make the model more realistic,the handling time of a vessel was assumed to depend on the number of assigned quay-cranes.Second,an improved genetic algorithm based on extenics dependent function was used to solve this model.In thisalgorithm,infeasible solutions play an important role.They were evaluated by their extenics dependent degrees.Some infeasible solutions were always contained in the population to maintain the diversity of the population.This improved local search ability of traditional geneticalgorithm.At last,the effectiveness and efficiency of the proposed model and algorithm were testified by several test pared with the model without considering the loading and unloading cost of quay-crane,the waste of resource is effectively reduced.【期刊名称】《计算机应用》【年(卷),期】2016(036)011【总页数】5页(P3136-3140)【关键词】集装箱码头;泊位岸桥协调调度;遗传算法;可拓关联函数;非线性混合整数规划【作者】杨劼;高红;刘涛;刘巍【作者单位】大连海事大学交通运输管理学院,辽宁大连 116026;大连海事大学数学系,辽宁大连 116026;中北大学计算机与控制工程学院,太原 030051;大连海事大学数学系,辽宁大连 116026【正文语种】中文【中图分类】TP301.6;U691.3码头资源调度优化一直是集装箱码头管理的难点问题。

岸桥调度的三维空间建模方法研究张艳伟;周万;郭放【摘要】岸桥是集装箱港口岸边作业的主要设备，岸桥调度的优劣将直接影响到船舶在港的装卸作业时间，进而对集装箱港口的总体作业效率产生影响。

以时间序列、船舶舱位号，以及岸桥序号作为坐标轴建立正交三维空间，在该三维空间下可以建立岸桥调度的整数线性规划模型。

利用该岸桥调度模型及LINGO软件对实际算例进行求解。

结果表明，三维空间下建立的岸桥调度优化模型能够有效解决集装箱港口的岸桥调度问题。

%Quay cranes are the primary handling equipment on the wharf .The quay crane scheduling plan will affect the handling time of the arriving vessels directly ,and the efficiency of the whole con-tainer port will be affected .A three-dimensional space was established in this paper .And an integer linear programing model was formulated .The model was solved with LINGO ,and the experiment re-sults showed that the model formulated with the three-dimensional method can be used to solve the quay crane scheduling problem very effectively .【期刊名称】《武汉理工大学学报（交通科学与工程版）》【年(卷),期】2014(000)004【总页数】4页(P826-829)【关键词】集装箱港口;岸桥调度;三维空间;整数线性规划;LINGO【作者】张艳伟;周万;郭放【作者单位】武汉理工大学物流工程学院武汉 430063; 武汉新港发展研究院武汉430063;武汉理工大学物流工程学院武汉 430063;武汉理工大学物流工程学院武汉 430063【正文语种】中文【中图分类】U691+.310 引言集装箱港口日常经营决策主要包括以下几个问题［1］：Q1，为到达船舶分配泊位；Q2，为到达船舶分配岸桥；Q3，确定岸桥在不同舱位的作业顺序；Q4，确定外部集装箱卡车的到达时间；Q5，内集卡的分配、调度及租用计划；Q6，内、外集卡的路径选择问题；Q7，内、外集卡在大门和岸边的派工策略；Q8，集装箱的箱位分配问题；Q9，场桥的分配与调度问题.在以上9个问题中：Q1，Q2，Q3主要解决集装箱港口的岸边作业问题；Q4，Q5，Q6，Q7主要解决集卡调度问题（包括内集卡和外集卡），Q8，Q9主要解决堆场作业问题.在实际生产活动中，集装箱港口通常将岸边作业计划作为堆场作业问题及集卡调度问题的输入，因此在制定岸边作业计划时往往只需要考虑到港船舶的相关特性即可，而不用考虑集卡调度问题以及堆场作业问题对其可能产生的影响.在集装箱港口的岸边作业问题中，Q1确定集装箱船在哪一段时间内停泊在码头的什么位置［2］，Q2确定各集装箱船在靠泊时间内的岸桥分配情况，Q3在Q1和Q2问题的基础上确定岸桥在各集装箱船不同舱位间的作业顺序.由于岸桥的分配情况（Q2）将直接影响到不同集装箱船所需的作业时间，而不同集装箱船所需的作业时间又对泊位分配计划（Q1）的结果产生很大影响，因而Q1和Q2通常需要一起考虑，被称为泊位与岸桥的联合分配问题（Q1+Q2）［3］.由于Q1+Q2的结果是岸桥调度问题（Q3）的输入，因此Q3不需要与Q1和Q2问题同时考虑，可以单独研究.在岸桥调度问题的相关研究中，靳志红，李娜［4］研究了基于泊位计划的岸桥调度问题，并利用遗传算法对模型进行了求解.张亚辉，梁承姬［5］研究了离散舱位的岸桥调度问题.秦进，倪玲霖，王承娜等［6］研究了多船舶的岸桥调度问题，并利用模拟退火算法对建立的数学模型进行了求解.1 建立三维空间结合岸桥的实际工作情况，对岸桥调度问题做出如下假设.1）每条船舶的靠泊时间以及该时间段内分配的岸桥数量已知（由Q1+Q2确定），每台岸桥都受到最早可利用时间的制约，并且所有岸桥的装卸效率相同.2）集装箱船的每个舱位可以没有装卸任务，也可以包含多个装卸任务，每个装卸任务的工作量已知，同舱位的装卸任务之间存在作业顺序的制约，因为同贝位的装卸任务通常先进行卸船作业，再进行装船作业.每个装卸任务必须连续作业，同舱位的多个装卸任务之间可以连续作业，也可以不连续作业.3）由于岸桥之间必须保持一定的安全距离，因而2个相邻的岸桥之间必须间隔至少一个舱位.4）岸桥在固定轨道上运行，因而无论岸桥是否处于作业状态，岸桥之间都不能相互跨越.将岸桥调度问题抽象成三维空间中长方体的位置决定问题，这种做法使得建立的模型更加简单.岸桥调度的三维空间模型见图1.图1 岸桥调度的三维空间模型三维空间中的每一个长方体都代表了一个装卸任务.X 轴为时间序列；Y 轴为船舶舱位号；Z轴为岸桥序号.长方体在X 轴方向上的长度为装卸任务的作业量，在Y轴上的坐标为装卸任务所在的舱位，在Z 轴上的坐标为装卸任务由哪一个岸桥完成.XOZ 平面内的投影表示岸桥作业计划，即哪一个岸桥在哪一个时间段内为哪一个装卸任务服务；XOY 平面内的投影表示不同舱位上的作业状态，即哪一个舱位上的哪一个装卸任务在哪一段时间内正在被服务.通过对XOZ 平面，以及XOY 平面内的投影设置相关约束就能够使岸桥调度满足实际生产中的限制条件.2 变量定义和数学模型为了方便建立数学模型，定义变量如下：I 为装卸任务集合，i，j∈I；K 为岸桥集合，k∈K；wi为任务i的装卸作业量，任务量单位为自然箱；xi为任务i开始装卸作业的时间，文中所涉及的时间单位均设定为处理一个自然箱所需要的平均时间；yi，任务i所在的船舶舱位号；zi，为任务i提供装卸服务的岸桥序号；bi，任务i完成装卸作业的时间；vij，当任务i的完成作业时间早于在任务j 的开始作业时间，vij=1，否则vij=0.当同舱位的装卸任务之间存在先后顺序时，可以利用vij=1对装卸时间进行控制，这部分vij可以认为是已知量，其他的vij则为变量；uij，当uij=1时，任务i所在的船舶舱位号小于任务j 所在船舶舱位号，并且为任务i提供装卸服务的岸桥序号小于为任务j 提供装卸服务的岸桥序号.当uij=0时，舱位序号之间以及岸桥序号之间不需要满足大小关系的约束；Sik，当任务i由岸桥k提供装卸作业服务时，Sik=1，否则Sik=0；M 为一个较大的实数，本文中取1000.利用以上数学符号以及岸桥调度问题在三维空间中的几何意义，建立岸桥调度的整数线性规划模型如下.目标函数：约束条件：目标函数（1）表示最小化各装卸任务完成时间的最大值，因此该模型是一个最大、最小化问题.目标函数（2）表示最小化所有任务完成作业时间之和，为次目标函数.当目标函数（1）存在多个最优解时，可以利用目标函数（2）对岸桥调度问题进一步优化，得到更加合理的解.约束条件（3）～（6）用来实现岸桥调度问题中假设3）和假设4）的约束；约束（7）保证所有的任务有且仅有一个岸桥为其提供装卸服务；约束（8）表示岸桥作业状态与岸桥序号之间的关系；约束条件（9）表示所有的装卸任务都必须在对应岸桥的最早可利用时间后才能进行装卸作业.3 算例分析由于建立的模型是一个整数线性规划模型，因而该模型的求解比较容易，利用LINGO 软件可以方便地求解这一类问题.表1和表2给出了一个岸桥调度问题的算例，表示为一艘具有10个40in舱位，12个装卸任务的集装箱船分配了3台岸桥，需要确定岸桥在不同舱位间的作业顺序.假设岸桥装卸一个集装箱的作业时间为一个时间单位.对于本文建立的多目标最大最小化数学模型，可以先不考虑目标函数（2）的最优化，并将目标函数（1）转化为约束条件，使优化模型转化为一个只有约束条件的混合组模型.增加的约束条件为通过设定不同的L 值来寻找目标函数（1）的最小值.利用Lingo软件的分支定界求解器，可以在1s之内求出混合组的可行解.当L=162时，混合组具有可行解，而当L=161时，混合组不存在可行解，因此目标函数（1）在最优解条件下的函数值为162.由于L=161条件下的可行解存在多个，因此目标函数（1）达到最小值时的最优解也有多个.将L 值固定为162，把目标函数（2）作为惟一的目标函数，利用分支定界算法可以在6s内求出模型的最优解，目标函数（2）在最优解条件下的函数值为1198.在绝大多数情况下，模型的最优解惟一.利用LINGO 求得算例的最优调度方案见表3.利用Excel软件将表3中最优化的结果绘制成岸桥调度的计划图（见图2）.为了进一步检验模型的有效性，并分析任务数、舱位数以及岸桥数对模型求解时间的影响，需要编制多个不同算例实验并进行求解.假设船舶贝位数的取值分别为10（3），14（4），18（5），22（5），括号中的数字表示允许同时作业的最大岸桥数量，岸桥数取值为3，4，5，任务数取值为10～30之间，当任务数较多时，分配的岸桥数量往往也较多.总共设计了54个算例.表1 装卸任务数据表表2 岸桥工作数据表表3 算例最优解结果图2 岸桥调度求解结果当算例的规模比较大时，往往很难通过LINGO 快速得出最优解，因而考虑通过设置合适的L值，得到可以接受的较优解，并比较分析在不同舱位数，任务数以及岸桥数等条件下，LINGO 求得较优解所需要的时间.假设某集装箱船的装卸任务量为450，分配3台岸桥为其服务.若所有岸桥在初始时刻就可以进行作业，则最优解不会小于150m（即L 可以取得的最小值）.显然150 m为最优解可能达到的最小值（通常情况下最优解会大于这个值），令L 分别取该值的105%和110%，即L=158m 或者165m.若L=158m 时存在可行解，则该可行解可以视为较优解，较优解与最优解（最优解大于或等于150m）的差值最大为5%；若L=158m 时不存在可行解，而L=165m时存在可行解，则较优解与最优解（最优解大于或等于158m）的最大差值仍为5%.比较不同条件下，LINGO 求得满足该L 限制的较优解的时间，见表4～表6.从表中的实验结果可以看出，在大多数算例实验中，可以在60s以内得到模型的较优解.在极少数情况下，模型较优解的求解时间会超过2min，即便如此，求解时间依然在可以接受的时间范围内.综上所述，该整数线性规划模型能够有效解决岸桥调度问题.表4 算例实验的求解时间岸桥数＝3 s表5 算例实验的求解时间岸桥数＝4 s表6 算例实验的求解时间岸桥数＝5 s4 结束语本文针对集装箱港口实际生产中岸桥调度问题的特点，建立了以时间序列、船舶舱位号，以及岸桥序号为坐标轴的三维空间，并基于该三维空间建立了岸桥调度的整数线性规划模型.利用LINGO 软件可以求解出数学模型的最优解，当问题规模较小时，利用LINGO 软件求得模型最优解比较方便，当问题规模较大时，可以利用LINGO 软件在可以接受的时间内求得模型的较优解，通常情况下可以在1min左右求得与最优解差值在5%的较优解.算例实验结果表明，该三维空间建模方法能够有效解决岸桥调度问题.参考文献［1］MURTY K G，LIU JIYIN，WAN Yatwah，et al.A decision support system for operations in a container terminal［J］.Decision Support System，2005，39：309-332.［2］MOON K.Berth scheduling by simulated annealing［J］.Transportation Research，2003，37：541-560.［3］KIM P.A scheduling method for berth and quay cranes［J］.OR Spectrum，2003，25：1-23.［4］靳志红，李娜.基于泊位计划的集装箱码头岸桥动态调度优化［J］.交通运输工程与信息，2011，11（3）：58-64.［5］张亚辉，梁承姬.基于离散舱位的集装箱港口岸桥作业调度研究［J］.武汉理工大学学报，2012，34（5）：64-69.［6］秦进，倪玲霖，王承娜，等.集装箱码头岸桥调度优化模型及算法［J］.西南交通大学学报，2013，48（1）：184-192.。

收稿日期:20180320基金项目:国家自然科学基金资助项目(71672117);辽宁省自然科学基金资助项目(201602526);辽宁省高等学校杰出青年学者成长计划资助项目(L J Q 2014133).作者简介:谢 谢(1981),女,辽宁沈阳人,沈阳大学副教授,博士.第30卷第4期2018年8月沈阳大学学报(自然科学版)J o u r n a l o f S h e n y a n g U n i v e r s i t y (N a t u r a l S c i e n c e )V o l .30,N o .4A gu .2018文章编号:2095-5456(2018)04-0294-05钢铁生产中具有不干涉约束的双吊机调度问题谢 谢1,周 莉2,郑勇跃3(1.沈阳大学装备制造综合自动化重点实验室,辽宁沈阳 110044;2.中国标准化研究院,北京 100191;3.辽宁省标准化研究院,辽宁沈阳 110004)摘 要:通过探究钢铁企业精炼车间具有不干涉约束的双吊机调度问题的结构,设计了求解问题的有效的启发式算法,证明了该算法在2台吊机情况下的最坏性能比是4/3.进一步通过计算实验,并使用实际生产数据对所提出的算法进行测试,结果证明算法在可接受的时间内可以产生近优解.关 键 词:吊机调度;强N P 难;启发式算法中图分类号:T P301.6 文献标志码:A钢铁工业是世界经济中的核心工业,是工业化㊁现代化㊁经济发展的有力象征,引领着建筑业㊁造船业㊁机器制造㊁家电和汽车业等其他工业的发展.钢铁生产是包括炼铁㊁炼钢㊁连铸㊁精炼等多阶段的生产模式,有关钢铁生产不同阶段的详细描述见文献[1],其中精炼阶段是生产中最基本的模式.在精炼阶段,钢包内融化的钢水首先由台车运输,再经由共享同一空中轨道的,平行的吊机将钢包装载到精炼炉上(见图1).这个过程对于吊机来说可以看做装载移动.装载移动结束后,吊机空载移动到台车上实施下一个装载移动.一旦钢包内钢水精炼结束,吊机将钢包从精炼炉卸载到台车上.图1 精炼车间中两台吊机的布局示意图F i g .1 L a y o u tw i t h t w oc r a n e s i na r e f i n i n g s h o p吊机是钢铁企业实际生产中的稀缺资源,通常精炼区域上方有2台吊机共享同一跨.吊机移动时它的抓取设备(吊钩)不但沿跨方向移动,同时可以在跨间移动,这种方式可以使吊机移动到区域的各个位置.吊机间的工作是同步的,每次最多对1个钢包进行操作.精炼过程不允许任意两吊机的交叉或碰撞(吊机间的不干涉要求).图1以5台精炼炉为例,当1台吊机对1个精炼炉实施操作时,另1台吊机不能跨越当前的这台吊机,也就是吊机调度服从不干涉约束.2台吊机的调度影响着炼钢过程的完工时间.因此,该过程的主要目的就是确定吊机的装载移动顺序,以最小化需要精炼钢水的结束时间,也就是最小化最后1个钢包精炼结束的时间.迄今为止,受到多数关注的吊机调度问题的文献主要集中在装箱港口码头终端的背景,该类问题首先由D a g a n z o[2]提出,即使是优化吊机调度以最小化1艘船只的最大完工时间,问题已经被Z h u等[3],L i m等[4],L e e等[5]证明为N P完备的.当考虑多吊机同时调度时,吊机在同一跨上彼此不能交叉的约束首先由K i m和P a r k[6]提出,对于跨上具有任意数目的吊机,L e e等[7],L i m 等[8]提出并证明了一些最坏性能比为2的算法. Z h a n g等[9]改进了所提出算法的界,并证明了对于任意m个吊机,算法的最坏性能比为2-2/m+ 1<2.不同于以上的吊机调度及经典的生产调度问题,本文考虑的吊机调度问题需要满足钢铁企业实际生产的具体要求,问题集中在钢铁企业的精炼环节,而精炼过程伴随着大量的物耗和能耗,尤其是吊机间为避免相互干涉或碰撞,或经常出现不必要的等待,或延长了等待时间,或额外增加了空载移动时间,一台吊机调度不好往往造成资源㊁能源的消耗和环境的污染.此外,大多数文献只是考虑了吊机的装载㊁卸载,忽略了吊机的移动时间.虽然谢谢等[1011]考虑了吊机的移动时间,但与本文研究的问题不同,文献[1011]只考虑了吊机作为生产过程的唯一运输工具,并没有考虑与台车等工具的协调.由于吊机是稀缺资源,一般精炼车间内通常有2~3台吊机,本文主要研究2台吊机的调度,考虑吊机间的干涉时没有忽略吊机移动时间.此外,从吊机运作角度考虑适合钢铁实际生产的简单易行的方法.1问题定义和描述本文定义最大完工时间为需要精炼的钢水最大完工时间,为精炼结束后,最后1个钢包从精炼炉卸载到台车上的时间.本文考虑的问题是调度2台吊机,且避免交叉最小化需求精炼钢包的最大完工时间.给定L个钢包在台车上等待精炼.为了方便表达,文中余下的部分定义台车的位置就是钢包的初始位置及最终位置.由于该位置固定,可以预先计算出吊机在任意两位置间的距离.给定从左至右沿跨方向有F个精炼炉,由于炉子和钢包的位置预先已知,吊机在任意两点的距离和时间都是可以计算的.每个吊机每次只能吊起1个钢包,每个炉子1次只能加工1个钢包.由于所研究的问题是N P-难的,所以不可能在可以接受的时间内求得大规模问题的最优解.因此,提出求解问题的启发式算法,并对算法进行最坏性能分析.2启发式算法及最坏性能分析算法首先从左至右将L钢包平均分成F个子集.计算每台吊机当前位置空载移动到台车提起钢包㊁装载移动到精炼炉后再放下的时间.第1步从左至右将F个子集形成列表,将该列表按照每台吊机的总操作时间平均分成2部分.将具有相同钢包数的2部分共享处于列表中间位置的精炼炉,也就是一些共享精炼炉的钢包分配给1台吊机,剩下的钢包分配给另1台吊机.下文将这些共享的精炼炉称为交叉精炼炉.第2步对于可交叉部分的精炼炉,将钢包分配给最早可能空闲的吊机,一旦2台吊机可同时操作,则将精炼炉分配给另1台吊机.第3步分配每一个部分给对应的吊机.用a(或b)表示第1(或第2)部分钢包的总数.由于算法平均分成2部分,从左至右将L钢包平均分成F个子集,属于交叉精炼炉数目的就是L-FLF.也就是说,a+L-F L Fæèçöø÷+b=L.(1)结合交叉精炼炉的定义及启发式算法,如果交叉精炼炉存在或L-FLF>0,则有a<L2和b<L2.为了证明启发式算法的最坏性能,令C m a x (σA)为由算法A生成调度σA的最大完成时间.C m a x(σ*)为最优调度σ*的最大完成时间.当且仅当C m a x(σA)C m a x(σ*)ɤα时,称算法A给出了最坏性能保证α.性质1对于2台吊机的问题,启发式算法的最坏性能比为4/3.证明讨论以下2种情况.情况1交叉精炼炉属于第1部分.592第4期谢谢等:钢铁生产中具有不干涉约束的双吊机调度问题根据算法第2步,则有a +L -F L F æèçöø÷-L 2<L 2-a ,即2a +L -F L F æèçöø÷<L ;(2)C m a x (σA )=a +L -F L F æèçöø÷.(3)结合式(1)㊁式(2)得:a <b .(4)根据不交叉约束,当一台吊机操作L -F LF精炼炉时,另一吊机或者操作第1部分的m i nL -F L F æèçöø÷,{}a 炉子,或者操作第2部分的m i n L -F L F æèçöø÷,{}b 炉子.必须等待,直到L -F L F炉子加工完成,2台吊机同时操作另外一部分或者在L -F L F炉子之前或之后完成.因此,有C m a x (σ*)ȡL -F L F +a2.(5)情况1.1 当L -F L F ȡL 2,结合式(1),有a +b =L -L -F L F æèçöø÷ɤL 2;结合情况a <b ,有a <L 4和L -F LF a>2.结合式(3)和式(5),则有C m a x (σA)C m a x (σ*)ɤa +L -F L F æèçöø÷L -F L F +a 2<43.情况1.2 当L -F L F <L 2,如果b ȡL -FL F ,结合式(1)和式(4),则有b >L 3.结合C m a x(σ*)ȡH 2,则C m a x (σA)C m a x (σ*)ɤa +L -F L F æèçöø÷L 2=L -b L 2<43.否则如果b <L -F L F ,则a <L -F L F.由于式(4),则有C m a x (σA)C m a x (σ*)ɤa +L -F L F æèçöø÷a 2+L -FL F æèçöø÷<43.情况2 交叉精炼炉属于第2部分.根据算法第2步,有:a +L -F L F æèçöø÷-L 2ȡL 2-a ,因此有:2a +L -F L F æèçöø÷ȡL ;(6)C m a x (σA )=L -F L F æèçöø÷+b .(7)结合式(1)和式(6),得a ȡb .(8)在这种情况下,根据式(8)及不交叉约束,则有C m a x (σ*)ȡL -F L F +b 2.(9)情况2.1 当L -F L F ȡL 2.结合式(1)和式(8),有b <L 4及L -F LF ȡ2b .根据式(7)和式(9),C m a x(σA)C m a x (σ*)ɤb +L -F L F æèçöø÷L -F L F +b 2<43.情况2.2 当L -F L F <L 2.如果a ȡL -F L F,结合(1)和(8)则有a >L 3.结合C m a x (σ*)ȡH 2,C m a x (σA )C m a x (σ*)ɤb +L -FL F æèçöø÷L 2=L -a L 2<43.否则,如果a <L -FL F ,则b <L -F L F.由于式(8),因此,C m a x (σA)C m a x (σ*)ɤb +L -F L F æèçöø÷b 2+L -FL F æèçöø÷<43.3 计算结果利用数值计算实验验证算法的有效性,表1证明了对于小规模实例算法的最优间隙.算法采用C #5.0语言编程,并且根据钢铁企业生产实际的数据求解了一系列问题的实例.此算法在内存为8192M BR AM 和i 7-37703.4G H z 的x 64位计算机上用V i s u a lC++语言编码进行了测试.每个实例考虑的参数如下:(1)装载移动时间t 在[30,100]之间离散平692沈阳大学学报(自然科学版) 第30卷均分布随机生成;(2)空载移动时间e t在[10,50]之间离散平均分布随机生成;(3)钢包和精炼炉的数目分别在[6,30]和[5,10]之间离散平均分布随机生成.算法的质量由跟下界L B的相对偏差(C m a x (σA)-L B)/L B*100%来度量,算法的平均误差比(A v g.E R)㊁最大误差比(M a x.E R),以及算法的平均计算时间(A v g.C P U)用来度量测试实例的性能.由表1可以看出,随着问题规模㊁精炼炉㊁钢包数目的增加,所提出的启发式算法的质量平均偏差低于22%.对于一组最小规模的问题,相比加工时间,吊机的移动时间很短,可以忽略.因此,该算法可以产生最优解.当精炼炉的数目与钢包数目不接近时,解的质量保持稳定.对于小规模实例,算法可以迅速获得问题的解.对于较大规模问题,算法的计算时间也不超过1s.表1启发式算法与下界比的平均最优间隙T a b l e1A v e r a g eo p t i m a l i t yg a p s o f t h e l o w e r b o u n d sw i t h r e s p e c t t o t h eh e u r i s t i ca l g o r i t h mF Lt=50,e t=20M a x.E R A v g.E R A v g.C P U/st=80,e t=30M a x.E R A v g.E R A v g.C P U/s5618.20518.036019.50119.2280 1019.01218.925020.06619.8590 2019.33419.1020.00220.15220.0010.003 3019.39819.2200.12620.37520.2030.2108618.31218.009020.00419.6990 1019.22819.017020.50220.1160 2019.56119.2250.00521.03921.0030.008 3019.57319.3280.25821.38921.0150.30410619.21318.968020.39520.0090 1019.30619.0250.00121.40321.1050.001 2019.59219.2690.00921.55721.2690.011 3019.78419.5620.56121.63621.2780.7794结论本文研究钢铁企业精炼车间的双吊机调度问题,考虑吊机间的不交叉约束,目标函数为最小化给定钢包的最大完工时间.探究了问题的最优性质,并提出1个启发式算法,进一步证明了该算法的最坏性能比为4/3.数值计算结果表明所提出的算法可以产生问题的近优解,最大偏差不超过22%,求解的时间不超过1s.未来的研究考虑扩展到更多吊机同时移动的问题.参考文献:[1]T A N G L,L I U J,R O N G A,e ta l.Ar e v i e w o f p l a n n i n ga n ds c h e d u l i n g s y s t e m sa n d m e t h o d s f o r i n t e g r a t e ds t e e lp r o d u c t i o n[J].E u r o p e a n J o u r n a l o f O p e r a t i o n a lR e s e a r c h,2007,133(1):120.[2]D A G A N Z O C F.T h ec r a n es c h e d u l i n g p r o b l e m[J].T r a n s p o r t a t i o nR e s e a r c hP a r tB,1989,23(3):159175.[3]Z HU Y,L I M A.C r a n e s c h e d u l i n g w i t h n o n-c r o s s i n gc o n s t r a i n t[J].J o u r n a l o f t h e O p e r a t i o n a l R e s e a r c hS o c i e t y,2006,57(12):14641471.[4]L I M A,R O D R I G U E S B,X U Z.A m-p a r a l l e lc r a n es c h e d u l i n gp r o b l e m w i t han o n-c r o s s i n g c o n s t r a i n t[J].N a v a lR e s e a r c hL o g i s t i c s,2007,54(2):115127. [5]L E ED H,WA N G H Q,M I A OL.Q u a y c r a n e s c h e d u l i n gw i t h n o n-i n t e r f e r e n c e c o n s t r a i n t s i n p o r t c o n t a i n e rt e r m i n a l s[J].T r a n s p o r t a t i o nR e s e a r c hP a r t EL o g i s t i c s&T r a n s p o r t a t i o nR e v i e w,2008,44(1):124135. [6]K I M K H,P A R K Y M.Ac r a n es c h e d u l i n g m e t h o df o rp o r t c o n t a i n e r t e r m i n a l s[J].E u r o p e a n J o u r n a l o fO p e r a t i o n a lR e s e a r c h,2004,156(3):752768. [7]L E ED H,WA N G H Q.A na p p r o x i m a t i o na l g o r i t h mf o rq u a y c r a n e s c h e d u l i n g w i t h h a n d l i n g p r i o r i t y i n p o r tc o n t a i n e r t e r m i n a l s[J].E n g i n e e r i n g O p t i m i z a t i o n,2010,42(12):11511161.[8]L I M A,R O D R I G U E SB,X U Z.A p p r o x i m a t i o ns c h e m e sf o r t h e c r a n e s c h e d u l i n gp r o b l e m[J].B e r l i n,H e i d e l b e r g:S p r i n g e r,2004:323335.[9]Z HA N GA,Z HA N G W,C H E NY,e t a l.A p p r o x i m a t e t h es c h e d u l i n g o f q u a y c r a n e s w i t h n o n-c r o s s i n g c o n s t r a i n t s[J].E u r o p e a n J o u r n a l o fO p e r a t i o n a l R e s e a r c h,2017,258(3):820828.[10]谢谢,郑勇跃,李彦平.工件和工具混合搬运的多吊机调度问题[J].沈阳大学学报(自然科学版),2016,28(4): 291295.X I E X,Z H E N G Y Y,L I Y P.J o b a n d t o o l m i x e dt r a n s p o r t a t i o nb a s e d m u l t i-c r a n es c h e d u l i n gp r o b l e m[J].J o u r n a l o f S h e n y a n g U n i v e r s i t y(N a t u r a lS c i e n c e),2016, 28(4):291295.[11]谢谢,郑勇跃.带有机器卸载不延误约束的多吊机调度问题[J].沈阳大学学报(自然科学版),2017,29(2):118124.792第4期谢谢等:钢铁生产中具有不干涉约束的双吊机调度问题X I EX,Z H E N G Y Y.M u l t i p l e c r a n e s c h e d u l i n g w i t hn o-d e l a y c o n s t r a i n t sf o r m a c h i n eu n l o a d i n g[J].J o u r n a lo f S h e n y a n g U n i v e r s i t y(N a t u r a l S c i e n c e),2017,29(2):118 124.T w o-C r a n eS c h e d u l i n g P r o b l e m w i t h N o n-i n t e r f e r e n c eC o n s t r a i n t i n I r o na n dS t e e l P r o d u c t i o nX i eX i e1,Z h o uL i2,Z h e n g Y o n g y u e3(1.K e y L a b o r a t o r y o f M a n u f a c t u r i n g I n d u s t r i a l a n dI n t e g r a t e d A u t o m a t i o n,S h e n y a n g U n i v e r s i t y,S h e n y a n g110044,C h i n a;2.C h i n aN a t i o n a l I n s t i t u t eo fS t a n d a r d i z a t i o n,B e i j i n g100191,C h i n a;3.L i a o n i n g I n s t i t u t eo fS t a n d a r d i z a t i o n, S h e n y a n g110004,C h i n a)A b s t r a c t:B y i n v e s t i g a t i n g t h es t r u c t u r eo f t h et w o-c r a n es c h e d u l i n gp r o b l e m w i t hn o n-i n t e r f e r e n c e c o n s t r a i n t i n t h e r e f i n i n g w o r k s h o p o f t h e i r o na n d s t e e l c o m p a n y,a n e f f i c i e n t h e u r i s t i c a l g o r i t h mf o r s o l v i n gp r o b l e m s i sd e s i g n e d.I t i s p r o v e dt h a t t h ew o r s t p e r f o r m a n c e r a t i oo f t h i sa l g o r i t h mi nt h ec a s e o f t w o c r a n e s i s4/3.T h r o u g h f u r t h e r c a l c u l a t i o ne x p e r i m e n t s,a n du s i n g t h ea c t u a l p r od u c t i o nd a t a t o te s t t h e p r o p o s e da l g o r i t h m,t h er e s u l t s p r o v et h a t t h ea l g o r i t h m c a n p r o d u c en e a r-o p t i m a l s o l u t i o n sw i t h i na na c c e p t a b l e t i m e.K e y w o r d s:c r a n e s c h e d u l i n g;N P-h a r d;h e u r i s t i c a l g o r i t h mʌ责任编辑:赵炬,李艳ɔ892沈阳大学学报(自然科学版)第30卷。

考虑不确定靠港作业时间的船舶调度问题目录1. 内容概要 (2)1.1 问题的背景 (2)1.2 研究的意义和目标 (3)1.3 文献综述 (5)2. 相关理论基础 (6)3. 问题描述 (7)3.1 作业环境的分析 (8)3.2 不确定性因素的识别 (9)3.3 调度问题的数学建模 (10)4. 算法设计与分析 (12)4.1 确定性调度算法 (14)4.2 鲁棒调度算法的设计 (15)4.3 启发式算法的改进 (16)4.4 综合调度策略 (18)5. 实例与仿真 (19)5.1 实例数据的选择与准备 (20)5.2 算法的实现 (22)5.3 仿真结果的分析 (23)6. 性能评估与优化 (24)6.1 性能指标的确定 (25)6.2 算法性能的评估 (27)6.3 优化策略的探讨 (28)7. 讨论与展望 (29)7.1 研究成果的讨论 (30)7.2 实践应用的可能性和限制 (31)7.3 未来研究的方向 (33)1. 内容概要传统的船舶调度模型通常假设靠港作业时间是确定的，然而在实际运营中，受到天气、港口拥堵以及其他不可控因素的影响，靠港作业时间具有较高的不确定性。

这导致了调度方案的低效率和航线运营的不稳定性。

本文旨在通过构建考虑靠港作业时间不确定性的船舶调度模型，在提高航线运营效率、优化资源分配以及降低运营风险方面寻求解决方案。

将结合概率论、随机规划等数学模型方法，并探讨针对不同不确定性场景的调度策略，以提高系统的鲁棒性和适应性。

期望为实际企业提供有效的调度决策支持，促进船舶运营的可持续发展。

1.1 问题的背景在现代社会中，全球海上货物运输占据了重要的地位，而港口作为货物进出口的关键节点，扮演着不可或缺的角色。

船舶调度的效率直接影响到港口运营的效率，进而关系到整个物流链的安全与经济效益。

理想的船舶调度策略能够最大化货物进出港口的效率，减少等待时间，提高港口吞吐量以及客户满意度。

实际的船舶调度工作中面临诸多不可控因素，比如天气状况、机械设备故障、船舶右倾响应及修改厂计划等，这些都可能导致船舶实际靠港作业时间与计划时间不符，使得原本预设的港口作业安排变得不确定。

改进Memetic算法求解集装箱码头泊位岸桥调度问题杨春霞;王诺【期刊名称】《计算机工程与应用》【年(卷),期】2011(047)022【摘要】The berth and quay crane allocation problem in container terminal is a NP-hard problem.Thus, an improved Mc-metic algorithm is proposed in this paper.In the algorithm, feasible solutions are represented by chromosomes with three-layer structure, and the order crossover and a new mutation based on neighborhood search are employed.After each crossover and mutation operation, an improved simulated-annealing algorithm is utilized for local search.The experimental results show the effectiveness of the proposed algorithm.%针对集装箱码头泊位岸桥调度这一NP难题,提出了一种改进的Mcmctic算法.算法中采用三层染色体结构表示个体,通过改进顺序交叉算子和基于领域搜索的变异算子以避免个体超出可行域,在交叉和变异后采用改进的模拟退火策略进行局部搜索.试验算例表明该算法收敛速度较快,且能获得较好的满意解.【总页数】3页(P233-235)【作者】杨春霞;王诺【作者单位】大连海事大学交通与物流工程学院,辽宁大连116026;大连海事大学交通与物流工程学院,辽宁大连116026【正文语种】中文【中图分类】TP39【相关文献】1.集装箱码头泊位、岸桥和集卡协同调度优化 [J], 田星;孟庆柱2.具有预知信息的集装箱码头泊位与岸桥联合调度在线模型 [J], 李英;乔龙亮;郑斐峰3.考虑岸桥维护的集装箱码头泊位与岸桥集成调度 [J], 胡鸿韬;任淑珍;胡雄4.基于复合成本的集装箱码头泊位-岸桥联合调度优化方法 [J], 徐皖东; 刘桂云; 王慈云; 骆璐瑶5.有限预知信息下集装箱码头泊位与岸桥联合在线调度 [J], 郑斐峰;乔龙亮;黄基诞因版权原因，仅展示原文概要，查看原文内容请购买。