堆场龙门吊调度问题研究

在集装箱码头作业中,龙门吊是非常重要的码头资源,如何更合理地调度龙门吊对减少船舶在港时间,提高码头效率有重要意义。在综合考虑龙门吊在时间和空间上的不可跨越性以及其他约束条件的基础上,建立了龙门吊调度问题的混合整数规划模型,目标是使得集卡的等待时间最短。由于问题计算的复杂性,引进遗传算法来求解模型;算例验证了算法的有效性,与已有的模型进行比较,证明了该模型的优越性。     

海铁联运港口混合作业模式下轨道吊与集卡协同调度

在集装箱海铁联运港口中,铁路作业区作为连接铁路运输和水路运输的重要节点,其装卸效率将影响集装箱海铁联运的整体效率。首先,对比分析了“船舶-列车”作业模式和“船舶-堆场-列车”作业模式的特点,并结合海铁联运港口实际作业情况提出了混合作业模式。然后,以轨道吊完工时间最短为目标构建混合整数规划模型,既考虑了班列和船舶的作业时间窗约束,又考虑了轨道吊间干扰和安全距离、轨道吊和集卡接续作业和等待时间等现实约束。针对遗传算法在局部搜索能力方面的不足,将启发式规则与遗传算法相结合设计了求解轨道吊与集卡协同调度问题的混合遗传算法（HGA）,并进行了数值实验。实验结果验证了所提模型和混合算法的有效性。最后通过设计实验分析集装箱数量、岸边箱占比、轨道吊数量和集卡数量对轨道吊完工时间和集卡完工时间的影响,发现同等集装箱数量下岸边箱占比提高时,应通过增加轨道吊数量来有效缩短完工时间。     

不确定环境下码头堆场设备集成调度优化

集装箱码头堆场设备调度优化中,对确定条件下的内集卡和场桥的联合调度研究较多,且没有考虑外集卡的随机到达情况。考虑内集卡和场桥作业过程中的不确定性因素,包括：内集卡行驶速度,场桥行走速度和作业时间,并考虑外集卡随机到达堆场对于内集卡调度作业的影响,构建了不确定因素条件下的堆场设备集成调度优化模型,其优化目标是在考虑外集卡随机到达的情况下,最优化堆场设备的作业时间。设计了求解模型的粒子群算法,并比较了一般确定性模型和考虑不确定因素优化模型的结果。算例结果表明,所建立的模型和算法能有效真实地反映不确定因素对集装箱码头堆场设备作业的影响。     

考虑作业状态能耗的集装箱码头设备协调调度

绿色港口日渐成为港口发展的必然趋势,为了提高集装箱码头的服务水平及降低其能耗,综合分析了集装箱码头的装卸作业流程,考虑岸桥、场桥、集卡在不同作业状态下的能耗,且以总完工时间和总作业能耗最小为目标建立了多目标混合整数规划模型。使用MATLAB编码改进自适应遗传算法求解所建模型,并分别与CPLEX和原始遗传算法的求解结果作对比,证明了该算法的优秀性。更改能耗目标和作业时间目标所占权重进行求解,发现考虑各设备在不同作业状态下的能耗会影响总完工时间,且能耗与作业时间是相互冲突的目标,追求低能耗会造成作业效率的牺牲。分析结果表明,所建模型和算法在岸桥、场桥和集卡的协调调度问题中可以帮助决策者更好地权衡作业时间和能耗目标。     

不确定环境下的岸桥集卡协调调度耦合模型建立与求解

集装箱码头系统是一个由多个子系统组成的复杂的生产系统,系统内资源的调度也是非线性的复杂问题,同时涉及多种多样的不确定性因素。从不确定性的角度出发,主要考虑码头装卸设备运行参数的概率分布,研究岸桥和集卡之间的协调调度问题。采用多学科变量耦合优化设计的方法,同时考虑了集装箱任务的时间窗约束,分别建立集卡分派子模型和集卡配置子模型。并将完工时刻和集卡数量作为公用设计变量连接两个子模型,建立了协调调度耦合模型。选取上海港某码头的数据编写算例,在Visual Studio 2012环境下调用Gurobi4.0求解该耦合模型,反复迭代计算后得出最优的集卡分派方案相对于最初的调度方案,总延误时间成本下降了90.69%,集卡数量下降了30.76%,验证了本模型的有效性和实用性。     

集装箱码头送箱外集卡预约优化研究

通过预约缓解集装箱码头拥堵是提高港口运作效率的有效途径。考虑集卡公司和码头运营商双方的利益以及码头内部作业系统的复杂性,以减小外集卡在预约时间窗内的平均排队长度和集卡公司期望到达的预约时间窗与被调配到的预约时间窗间的差异为目标,运用排队论相关知识和逐点固定流体近似方法（PSFFA）,建立了多目标规划模型,以确定一个使集卡公司和码头运营商双赢的集卡调度计划。引入实例数据,利用CPLEX求解模型,并将结果与蒙特卡罗仿真结果作比较,以验证模型的有效性,并在此基础上调节参数优化预约模式。算例结果表明,集卡预约多目标规划模型能有效描述集卡在闸口和堆场的排队情况,最小化外集卡在码头排队长度和集卡公司期望到达的预约时间窗与被调配到的预约时间窗之间的差异。     

集卡分批到达模式下的进口箱场桥作业调度优化

在进口箱疏港过程中, 服务于相同客户的若干集卡组成集卡组, 具有相同的抵港时间, 因此, 外部集卡抵港提箱呈现分批到达的特点. 集卡组内作业指派的优劣直接影响场桥的作业效率, 存在较大的优化空间. 对此, 基于翻箱作业不能跨贝进行的现实约束, 将场桥作业调度解构为场桥作业路径优化问题和贝内翻箱作业优化问题两部分并分别建立动态优化模型. 针对场桥作业路径优化问题, 提出一种多项式时间的精确算法并给以证明; 针对贝内翻箱作业优化问题, 设计一种基于MSA的双层启发式算法进行求解. 一系列数值实验的结果显示了所提出优化模型及算法的有效性和鲁棒性.

     

FF现场总线系统中实时任务的建模与调度

本文研究了单网段 FF现场总线系统中具有时间约束和次序约束的实时任务，即 功能块任务和通信任务的建模与调度．首先，将功能块任务和通信任务等视为相同的任务， 在只考虑任务间次序约束的情况下，提出了基于紧凑模式的任务模型，以保证每个作业被尽 可能早地完成．其次，考虑单网段通信任务共享一个传输介质而引起的通信超时，提出了基 于作业速率单调优先级算法的扩展紧凑模式的任务调度算法，以满足实时任务的时间约束 和次序约束．最后，通过一个应用实例来描述实时任务的调度过程．     

速度不确定下作业时间最短的集卡调度优化

在集装箱码头装卸作业中,提高集卡调度对作业效率有非常大的影响。而集装箱卡车重车和空车行驶速度的不确定性,增加了集卡调度的难度。为此提出建立不确定环境下作业时间最短的集卡调度优化模型。在完成固定装卸任务的前提下,通过对集卡的合理调度,达到不确定情况下集卡总作业时间最短。针对不确定模型的特点,采用粒子群算法快速求解,同时保证了解的有效性。算例表明上述模型和算法合理解决了不确定环境下集卡调度优化问题,得到较好的计算结果,并且降低了运算复杂度,提高了调度效率。     

具有树和路约束的平行机排序问题

考虑具有树和路约束的平行机排序问题,其工件集对应于无向图(有向图)的边(弧)集。目标是选取工件集的一个子集使其满足树或路的约束,将其放在平行机上处理,使得机器的最大完工时间(makespan)尽可能地小。通过分析此类问题的组合性质,得到如下结论：在K-树约束下,利用最小支撑K-树的性质可得一个有效多项式时间近似方案;在两固定点间路的约束下,通过构造辅助实例以控制边的权重,分析辅助实例的输出值与目标实例最优值之间的关系,利用最短路的性质可以得到一个2-近似算法;在单源点最短路径树的约束下,根据最短路径树的性质可以得到一个有效多项式时间近似方案;在两固定点间最短路的约束下,在所有的两点间最短路构成的子图基础上,通过构造新的辅助图以控制弧的权重,再利用最短路的性质可以得到一个1.618-近似算法。     

混堆集装箱箱区内场桥调度模型与算法

在混堆模式下的集装箱港口中,场桥（YC）调度是否合理直接影响着堆场的作业效率。考虑到混堆箱区内各任务对应的内集卡或外集卡到达时刻的不同,以及内外集卡优先级别的差异,构建了一个以所有集卡的等待成本和场桥的总移动成本最小为目标的场桥调度（YCS）模型,并设计了对应的遗传算法,给出了相应遗传算子的操作规则,通过算例的求解验证了模型与算法的有效性。     

A decision method on yard cranes transformation and deployment in green ports

This study proposes a strategic level decision method for yard cranes (YCs) transformation and deployment for the purpose of building efficient and energy-saving green ports with low carbon emission. An integer programming model is embedded in the method for the above decision considering some green technology for YC transformation. The aim of the model is to minimize the investment cost for purchasing and transforming YCs as well as the operation costs during the planning horizon. A neighborhood descent particle swarm optimization algorithm is developed for solving the proposed model. Real data based on numerical experiments are conducted to verify the effectiveness of the proposed decision method. Take the case of Shanghai Yangshan Deep Water Port, the carbon emission is reduced by 415,756.8 kg and the energy consumption costs are saved 1,226,016 RMB. The above method may be potentially useful for the practitioners on the strategic level decisions of YCs transformation and deployment.     

Yard crane scheduling in a container terminal for the trade-off between efficiency and energy consumption

Green transportation has recently been the focus of the transportation industry to sustain the development of global economy. Container terminals are key nodes in the global transportation network and energy-saving is a main goal for them. Yard crane (YC), as one type of handling equipment, plays an important role in the service efficiency and energy-saving of container terminals. However, traditional methods of YC scheduling solely aim to improve the efficiency of container terminals and do not refer to energy-saving. Therefore, it is imperative to seek an appropriate approach for YC scheduling that considers the trade-off between efficiency and energy consumption. In this paper, the YC scheduling problem is firstly converted into a vehicle routing problem with soft time windows (VRPSTW). This problem is formulated as a mixed integer programming (MIP) model, whose two objectives minimize the total completion delay of all task groups and the total energy consumption of all YCs. Subsequently, an integrated simulation optimization method is developed for solving the problem, where the simulation is designed for evaluating solutions and the optimization algorithm is designed for exploring the solution space. The optimization algorithm integrates the genetic algorithm (GA) and the particle swarm optimization (PSO) algorithm, where the GA is used for global search and the PSO is used for local search. Finally, computational experiments are conducted to validate the performance of the proposed method.     

Yard crane scheduling problem in a container terminal considering risk caused by uncertainty

In a container terminal, the arriving times and handling volumes of the vessels are uncertain. The arriving times of the external trucks and the number of containers which are needed to be brought into or retrieved from a container terminal by external trucks within a period are also uncertain. Yard crane (YC) scheduling is under uncertainty. This paper addresses a YC scheduling problem with uncertainty of the task groups' arriving times and handling volumes. We do not only optimize the efficiency of YC operations, but also optimize the extra loss caused by uncertainty for reducing risk of adjusting schedule as the result of the task groups' arriving times and handling volumes deviating from their plan. A mathematical model is proposed for optimizing the total delay to the estimated ending time of all task groups without uncertainty and the extra loss under all uncertain scenarios. Furthermore, a GA-based framework combined with three-stage algorithm is proposed to solve the problem. Finally, the proposed mathematical model and approach are validated by numerical experiments.     

Scheduling of collaborative operations of yard cranes and yard trucks for export containers using hybrid approaches

Optimizing collaborative operations for yard cranes (YCs) and yard trucks (YTs) is vital to the overall performance of a container terminal. This research investigates four different hybrid approaches developed for dealing with yard crane scheduling problem (YCSP) and yard truck scheduling problem (YTSP) simultaneously for export containers in the yard side area of a container terminal. First, these approaches use a load-balancing heuristic to assign containers to YCs evenly. Following this, each of them employs a specific heuristic/metaheuristic, such as genetic algorithm (GA), particle swarm optimization (PSO) or subgroups PSO (SGPSO), to generate alternative container loading sequences for each YC. Finally, a simulation model is used to simulate loading and transporting of these export containers, evaluate alternative planning results, and finally output the best planning result. Experiments have been conducted to compare these hybrid approaches. The results show Hybrid4 (SGPSO) outperforms Hybrid1 (Sort-by-bay), Hybrid2 (GA), and Hybrid3 (PSO) in terms of makespan.     

Genetic mechanism-based coupling algorithm for solving coordinated scheduling problems of yard systems in container terminals

This study develops models and methods utilized for solving the coordination scheduling problem in the yard of a container terminal. Based on the information shared by the yard storage subsystem and the YC scheduling subsystem, and the interaction between these subsystems, a coordination scheduling model, which is composed of a storage subsystem model, a YC scheduling subsystem and a coordinate controller model, is developed. A coupling algorithm, which is based on a genetic mechanism, is developed to solve the coordination scheduling problem. The algorithm adopts the genetic selection, crossover and mutation operations to adjust the yard storage plan and the YC scheduling plan. The performance of the coordination scheduling model and that of the proposed coupling algorithm are confirmed with reference to a numerical example.     

Dynamic yard crane dispatching in container terminals with predicted vehicle arrival information

The performance of a container terminal depends on many aspects of operations. This paper focuses on the optimal sequencing of a yard crane (or YC for short) for serving a fleet of vehicles for delivery and pickup jobs. The objective is to minimize the average vehicle waiting time. While heuristic algorithms could not guarantee an optimal solution, a conventional mathematical formulation such as mixed integer program would require too much computing time. We present two new algorithms to efficiently compute YC dispatching sequences that are provably optimal within the planning window. The first algorithm is based on the well-known A^∗ search along with an admissible heuristics. We also incorporate this heuristics into a second backtracking algorithm which uses a prioritized search order to accelerate the computation. Experimental results show that both new algorithms perform very well for realistic YC jobs. Specifically, both are able to find within seconds optimal solutions for heavy workload scenarios with over 2.4 × 10¹⁸ possible dispatching sequences. Moreover, even when the vehicle arrival times are not accurately forecasted, the new algorithms are still robust enough to produce optimal or near-optimal sequences, and they consistently outperform all the other algorithms evaluated.     

集装箱码头微观分析仿真模型的构建方法研究

集装箱码头日常的生产组织具有微观、细致的典犁特点,但在以往的仿真研究中,对集装箱码头的细节描述比较粗糙,实体的行为进行了简化.为此,提出了集装箱码头微观分析仿真模型(Container Yard Microanalysis Simulation Model,CYMSM)的概念,分析了集装箱码头微观分析仿真模型的特点,研究了一个一般意义上的集装箱码头微观分析仿真模型的构建方法,对该模型的实体、事件、活动、进程(Entity,Event,Activity & Process,EEAP)四要素进行了描述.分析了影响集装箱码头生产作业微观系统真实性的作业规则,在此基础上确定了相应的仿真模拟机制.提出了基于微观分析的集装箱码头仿真模型的评价指标及调整机制.研究结果可为集装箱码头生产作业仿真系统的构建提供依据.     

Steelmaking and refining coordinated scheduling problem with waiting time and transportation consideration

This article explores the coordinated scheduling problem between production and transportation in a steelmaking shop. Two models arising from steelmaking and refining operations are considered. The first model assumes that there is a converter at the steelmaking operation and a refining furnace at the refining operation. A transporter with capacity one is available to carry out jobs from converter to a refining furnace. The objective is to minimize the maximum completion time. For this model, we provide an algorithm with worst case ratio of two and show the computational results. The second model considers more practical situation in which jobs are processed in identical parallel converters first, and then the jobs coming from same converter are transported by a dedicated trolley with capacity one to the next operations. Two objectives are considered in the second model. One is to minimize the sum of maximum completion time, idle time penalties and waiting time penalties satisfying waiting time constraints. The other is to minimize the sum of maximum completion time, idle times penalties and hot consumption penalties related to waiting times while satisfying waiting time constraints. For the model, we develop a tabu search algorithm, provide the computational results and then give the worst case analysis.