Optimizing yard assignment in an automotive transshipment terminal

This paper studies a yard management problem in an automotive transshipment terminal. Groups of cars arrive to and depart from the terminal in a given planning period. These groups must be assigned to parking rows under some constraints resulting from managerial rules. The main objective is the minimization of the total handling time. Model extensions to handle application specific issues such as a rolling horizon and a manpower leveling objective are also discussed. The main features of the problem are modeled as an integer linear program. However, solving this formulation by a state-of-the-art solver is impractical. In view of this, we develop a metaheuristic algorithm based on the adaptive large neighborhood search framework. Computational results on real-life data show the efficacy of the proposed metaheuristic algorithm.     

Crane scheduling in container yards with inter-crane interference

This paper examines the problem of scheduling multiple yard cranes to perform a given set of jobs with different ready times in a yard zone with only one bi-directional travelling lane. Due to sharing of the travelling lane among two or more yard cranes, inter-crane interference, a planned move of a yard crane blocked by the other yard cranes, may happen. The scheduling problem is formulated as an integer program. It is noted that the scheduling problem is NP-complete. This research develops a dynamic programming-based heuristic to solve the scheduling problem and an algorithm to find lower bounds for benchmarking the schedules found by the heuristic. Computational experiments are carried out to evaluate the performance of the heuristic and the results show that the heuristic can indeed find effective solutions for the scheduling problem, with the heuristic solutions on average 7.3% above their lower bounds.     

基于仿真优化的炼钢生产批调度求解方法

论文针对钢铁企业炼钢工序具有高温、高能耗、复杂工况的实际特征,从中提炼出生产批调度问题,其工件根据其实际工艺属性可分为多个簇,基于给定的工件簇,决策工件的分批和调度情况,综合考虑工件之间的切换费用,以及工件提前、拖期所导致的惩罚,使得总的生产成本期望最小化,从而降低生产成本;针对该问题,考虑工件的处理时间、工件的加工属性具有不确定性,基于仿真优化思想,建立数学模型,并基于大数定理,对模型目标函数进行近似;提出基于样本近似方法的求解框架,通过随机抽样的方法获得不同规模的样本,针对不同规模的样本,提出Filter & Fan算法对问题进行求解;最后,通过基于实际数据的计算实验验证所提算法的有效性。     

Two-stage search algorithm for the inbound container unloading and stacking problem

This study focuses on the inbound container unloading and stacking problem at container terminals and achieves both a reasonable unloading sequence and the optimal yard stacking distribution. A formulation is proposed as the relational expression between the expected number of rehandles and the stacking height. Based on the formulation, an integer programming model is established to both find the optimal stacking distribution and unloading sequence and attempt to minimize the expected number of rehandles. The model can be solved by the commercial solver for small-scale instances. To solve for large-scale instances in the real world, a two-stage search algorithm is designed, therein incorporating an initial stage for generating the feasible solution and a neighborhood search stage for finding the optimal solution. The algorithm can find an optimal solution in polynomial time, which is proved by theoretical methods and evidenced by numerical experiments.     

An Eulerian‐Lagrangian Concept for the Numerical Simulation of Flat Steady‐State Hot Rolling Processes

For the finite element analysis of stationary flat hot rolling processes, a new and efficient mathematical model was developed. The method is based on an intermediary Eulerian‐Lagrangian concept, where an Eulerian coordinate is employed in the rolling direction, while Lagrangian coordinates are used in the direction of the thickness and width of the strip. This approach yields an efficient algorithm, where the time is eliminated as an independent variable in the steady‐state case. Further, the vector of independent field variables consists of a velocity component in Eulerian and of displacement components in Lagrangian directions. Due to this concept, the free surface deformations can be accounted for directly and the problems encountered with pure Eulerian or Lagrangian models now appear with reduced complexity and can thus be tackled more easily. The general formalism was applied to different practical hot rolling situations, ranging from thick slabs to ultra‐thin hot strips. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

基于两阶段混合动态规划算法的龙门吊路径优化

产业界已出现利用多台轨道式龙门吊同时作业以提升集装箱码头装船效率的情况,由于需要确定每台龙门吊的取箱作业集合以及增加了“避免碰撞”、“顺次移动”等现实约束,故其移动路径规划问题在模型建立与求解上比单台轨道式龙门吊更为复杂。本文针对两台轨道式龙门吊同时作业的情形,建立了龙门吊移动路径网络模型,并开发了基于贪婪算法与动态规划的两阶段混合算法,并通过仿真算例,借助与基于实际调度规则所得到的调度方案的对比,验证了模型及优化算法的有效性与实用性。     

Models for scheduling charges in continuous casting: application to a Brazilian steel plant

In this paper we propose models for the scheduling of charges considering the alternatives of intermix slabs or setups between consecutive jobs. The study is motivated by the practical need of a steel plant in Brazil to reduce costs in a low volumes/wide range of products environment. An intermix slab is formed when two jobs with different grades and/or widths are processed without stopping the machine. This may generate a poor material, which has low commercial value or is used as scrap. The machine may also be stopped between two consecutive jobs to allow a setup. The setup operation has an associated cost, but no intermix slab is created. Thus, the scheduling problem consists of defining the sequence of charges and whether an intermix slab or a setup operation must take place to minimize the total cost. We report computational experiments on real data. This study, by comparing results with actual schedules planned, shows that significant cost savings upon practice can be achieved by running the proposed models on standard optimization packages.     

Yard crane scheduling in port container terminals

Yard cranes are the most popular container handling equipment for loading containers onto or unloading containers from trucks in container yards of land scarce port container terminals. However, such equipment is bulky, and very often generates bottlenecks in the container flow in a terminal because of their slow operations. Hence, it is essential to develop good yard crane work schedules to ensure a high terminal throughput. This paper studies the problem of scheduling a yard crane to perform a given set of loading/unloading jobs with different ready times. The objective is to minimize the sum of job waiting times. A branch and bound algorithm is proposed to solve the scheduling problem optimally. Efficient and effective algorithms are proposed to find lower bounds and upper bounds. The performance of the proposed branch and bound algorithm is evaluated by a set of test problems generated based on real life data. The results show that the algorithm can find the optimal sequence for most problems of realistic sizes.     

The service allocation problem at the Gioia Tauro Maritime Terminal

The Service Allocation Problem (SAP) is a tactical problem arising in the yard management of a container transshipment terminal. The objective is the minimization of the container rehandling operations inside the yard. This study of the SAP was undertaken for the Gioia Tauro port which is located in Italy and is the main hub terminal for container traffic in the Mediterranean Sea. The SAP can be formulated as a Generalized Quadratic Assignment Problem (GQAP) with side constraints. Two mixed integer linear programming formulations are presented. The first one exploits characteristics of the yard layout at Gioia Tauro where the berth and the corresponding yard positions extend along a line. The second formulation is an adaptation of a linearization for the GQAP. In both cases only small instances can be solved optimally. An evolutionary heuristic was therefore developed. For small size instances the heuristic always yields optimal solutions. For larger sizes it is always better than a truncated branch-and-bound algorithm applied to the exact formulations.     

考虑翻箱的场桥调度和提箱集卡数量的集成优化

在集装箱码头的进口箱堆场中,码头预约机制、待提箱的实时位置和场桥作业调度方案是制约堆场作业效率和堵塞情况的关键。为缓解进口箱堆场的拥塞情况并提高作业效率,在固定的预约时段内,考虑实时压箱量最少的翻箱规则,兼顾场桥间不可跨越和保持安全间距等现实约束,以场桥最长完工时间最小为目标,构建数学优化模型,设计了嵌入修复算子的改进遗传算法用于求解;通过算例实验验证了算法的有效性和方案的优越性,可为堆场实际作业提供决策参考。     

A mathematical model and two-stage heuristic for hot rolling scheduling in compact strip production

This paper addresses a new hot rolling scheduling problem from the compact strip production process, which is the mainstream production technology that is used worldwide for sheet strips. The problem is modeled as a combination of two coupled sub-problems. One sub-problem is a sheet strip assignment problem that assigns sheet strips to rolling turns with the constraints of safe values of different gauge levels, and the other is a sheet strip sequencing problem that decides the rolling sequence for all of the sheet strips in a rolling turn to form a particular parabolic shape in thickness. To solve this hot rolling scheduling problem, we present a novel approach that consists of a sheet strip assignment heuristic and a sheet strip sequencing heuristic. The sheet strip assignment heuristic minimizes the number of virtual sheet strips by generating rolling turns according to the ordered sheet strips with maximum gauge level and their safe values. The sheet strip sequencing heuristic minimizes the average change of the thickness of adjacent sheet strips by arranging a certain number of duplicate sheet strips to the increasing stage of a rolling turn. Extensive experiments based on both synthetic and real-world instances from a compact strip production process show the effectiveness of the proposed two-stage heuristic in solving the hot rolling scheduling problem.     

Yard template planning in transshipment hubs under uncertain berthing time and position

This paper is concerned with yard management in transshipment hubs, where a consignment strategy is often used to reduce reshuffling and vessel turnaround time. This strategy groups unloaded containers according to their destination vessels. In this strategy, yard template determines the assignment of the spaces (sub-blocks) in the yard to the vessels. This paper studies how to make a good yard template under uncertain environment, for example, uncertain berthing time and berthing positions of the arriving vessels. To reduce the potential traffic congestion of prime movers, the workload distribution of sub-blocks within the yard is considered. A mixed integer programming model is formulated to minimize the expected value of the route length of container transshipping flows in the yard. Moreover, a heuristic algorithm is developed for solving the problem in large-scale realistic environments. Numerical experiments are conducted to validate the efficiency of the proposed algorithm.     

A novel dynamics model for railway ballastless track with medium-thick slabs

Motivated by the requirements for elaborated slab ballastless track dynamics analysis in practical engineering application, a novel dynamic model for the railway ballastless tracks with medium-thick slabs is proposed in this work based on the Reissner–Mindlin plate theory, and it is implemented into the coupled dynamics analysis of a vehicle and the ballastless track. First, an efficient and easily programmable computational algorithm is adopted to solve the transverse deflection of the Reissner–Mindlin plate, in which the displacements and shear strains are chosen as the independent variables and subsequently constructed by spline functions, resulting in no shear-locking effect. The involved partial differential equations are transformed into ordinary ones by using the energy variation principle. Further, a mathematical model for the ballastless track dynamics analysis is established, which can consider the effects of the shear deformation and moment of inertia involved in the medium-thick track slab. Experimental verification and comparative analysis with other models demonstrate the accuracy and efficiency of the proposed model. Finally, a spatially coupled dynamics model of a vehicle and the ballastless track is developed, and it is efficiently solved by using the hybrid explicit-implicit time integration method. Compared with the widely used modelling the track slab by elastic thin plate, the reliability and advantages of the proposed vehicle-slab track coupled dynamics model are demonstrated.     

A finite algorithm to fit geometrically all midrange lines, circles, planes, spheres, hyperplanes, and hyperspheres

Summary. The algorithm proved here solves the problem of orthogonal distance regression for the maximum norm with hyperplanes and hyperspheres. For each finite set of points in a Euclidean space of any dimension, the algorithm determines – through finitely many arithmetic operations – all the hyperplanes and hyperspheres that minimize the maximum Euclidean distance measured perpendicularly from the data. The algorithm finds all the slabs (bounded by parallel hyperplanes) and all the spherical shells (bounded by concentric hyperspheres) that contain all the data and are “rigidly supported” by the data (for which there does not exist any other pair of parallel hypersurfaces of the same type that intersect the data at the same points.) The computational complexity of the algorithm increases as the number of data points raised to the dimension of the ambient space. The solutions are then the midrange hyperplanes in the thinnest slabs, and the midrange hyperspheres in the thinnest shells. Their sensitivity to perturbations of the data is of the order of a power of the reciprocal of the smallest angle between two median hyperplanes separating two pairs of data points. The methods of proof consist in showing that if a pair of parallel hyperplanes or hyperspheres is not rigidly supported but encompasses all the data, then there exists a projective shift of their common projective center producing a thinner slab or shell that still contains all the data. Received December 14, 1999 / Revised version received August 30, 2000 / Published online September 19, 2001     

A rolling horizon approach for disruption management of railway rolling stock

This paper deals with real-time disruption management of rolling stock in passenger railway transportation. We describe a generic framework for dealing with disruptions of railway rolling stock schedules. The framework is presented as an online combinatorial decision problem, where the uncertainty of a disruption is modeled by a sequence of information updates. To decompose the problem and to reduce the computation time, we propose a rolling horizon approach: rolling stock decisions are only considered if they are within a certain time horizon from the time of rescheduling. The schedules are then revised as time progresses and new information becomes available. We extend an existing model for rolling stock scheduling to the specific requirements of the real-time situation, and we apply it in the rolling horizon framework. We perform computational tests on instances constructed from real-life cases of Netherlands Railways (NS), the main operator of passenger trains in the Netherlands. We explore the consequences of different settings of the approach for the trade-off between solution quality and computation time.     

Parareal in time approximation of the Korteveg-deVries-Burgers' equations

The parareal in time algorithm is a predictor corrector method that allows to get parallelisation through the time. It consists in segmenting the interval of time integration into slabs, then propose iteratively seed values at the left hand side of each of the slabs. The derivation of the seed values is done sequentially and involves propagator that should mimic the equation to be solved but should be very cheap and parallel accurate propagations of each seed value over each slab. Various approaches have been proposed to get the coarse propagator, in this paper, we use the averaging approach developed by Barenblatt and Chorin for the Korteveg-deVries-Burgers' equations. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Secondary log breakdown optimization with dynamic programming

Log breakdown can be viewed as a two-stage process with logs sawn into slabs of wood known as flitches during the primary stage and flitches further processed during the secondary stage to produce edged (cut lengthwise) and trimmed (cut widthwise) pieces. This paper addresses the secondary problem and describes some procedures for determining the optimal cutting of flitches into graded dimensional boards. The problem is formulated as a set packing problem with the objective being to maximise total value. Extensions to the basic formulation include constraints which restrict the number of saws and which disallow waste between adjacent edged pieces. The problem is solved using dynamic programming techniques and the algorithms incorporated into a sawing simulation system. Comparisons with existing edging and trimming procedures show that substantial reductions in solution time (to as little as 1/25th of the time required for an enumerative search) can be achieved.     

Steady-state oscillations of composite isotropic plates

The problem of the steady-state transverse oscillations of composite isotropic slabs is solved by the small-parameter method. A two-layer slab with a fixed and free contour is examined numerically. Curves of specific energy along the radius of the slab versus vibration frequency are given.Donetsk. Mariupol'. Translated from Teoreticheskaya i Prikladnaya Mekhanika, No. 21, pp. 51–55, 1990.     

Combined primary and secondary log breakdown optimisation

At sawmills logs are converted into boards by a series of cutting operations. Primary cuts reduce logs into slabs of wood, secondary cuts produce boards. Boards incorporating natural defects such as knots (branch sections) are inferior to clear boards. The aim of the sawmill is to cut logs to produce boards of greatest value. However, when logs are pruned, knots are only exposed after primary cutting. This complicates the conversion problem.To effectively convert logs into boards the interrelated effects of the cutting phases must be recognized. In this paper linked dynamic programming formulations are developed. The inner (secondary) formulation determines the optimal sequence for cutting a slab into boards. The result is passed to the master (primary) formulation that determines the optimal sequence for cutting the log into slabs. The objective functions can be modified to maximise either total value of boards (incorporating quality) or total volume. Results from simulations indicate that significant increases in value are possible when quality is considered.     

A critical-shaking neighborhood search for the yard allocation problem

The yard allocation problem (YAP) is a real-life resource allocation problem faced by the Port of Singapore Authority (PSA). As the problem is NP-hard, we propose an effective meta-heuristic procedure, named critical-shaking neighborhood search. Extensive experiments have shown that the new method can produce higher quality solutions in a much shorter time, as compared with other meta-heuristics in the literature. Further to this, it has also improved or at least achieved the current best solutions to all the benchmark instances of the problem.