A New Algorithm for Stochastic Discrete Resource Allocation Optimization

Stochastic discrete resource allocation problems are difficult to solve. In this paper, we propose a new algorithm designed specifically to tackle them. The algorithm combines with the Nested Partitions method, the Ordinal Optimization techniques, and an efficient simulation control technique. The resulting hybrid algorithm retains the global perspective of the Nested Partitions method and the fast convergence properties of the Ordinal Optimization. Numerical results demonstrate that the hybrid algorithm can be effectively used for many large-scale stochastic discrete optimization problems.     

双层束搜索算法优化机器人制造单元调度问题

针对混流生产阻塞机器人制造单元调度问题，给出了可行机器人运动插入法，构建可行解。依据可行机器人运动插入法，提出双层过滤变宽度束搜索算法进行求解。搜索过程利用局部评价函数和全局评价函数对节点进行两次择优选取。通过计算随机生成算例，仿真结果表明，相对于以分支定界算法产生的可行解进行变邻域搜索、分支定界算法、局部评价函数束搜索算法、全局评价函数束搜索算法和双层过滤定宽度束搜索算法，双层过滤变宽度束搜索算法不但能显著提高搜索效率，而且解的平均改进度分别为3.07%、6.07%、7.79%、12.62%、14.47%。     

嵌套分割算法：一种新的并行随机优化算法*

嵌套分割算法是一种新的系统优化计算方法,它可以应用于确定型和随机型、离散系统和连续系统的优化问题.综述了嵌套分割算法的概念原理、方法步骤,介绍了算法的应用情况,并探讨了算法未来的研究方向.     

Variable neighborhood search for the inventory routing and scheduling problem in a supply chain

The inventory, routing and scheduling decisions are three major driving factors for supply chain performance. Since they are related to one another in a supply chain, they should be determined simultaneously to improve the decision quality. In the past, the inventory policy, vehicle routing and vehicle scheduling are determined sequentially and separately. Hence, the total cost (inventory, routing and vehicle costs) would increase. In this paper, an integrated model for the inventory routing and scheduling problem (IRSP) is proposed. Since searching for the optimal solution for this model is a non-polynomial (NP) problem, a metaheuristic, variable neighborhood search (VNS), is proposed. The proposed method was compared with other existing methods. The experimental results indicate that the proposed method is better than other methods in terms of average cost per day.     

一种模糊项目调度问题的变宽Beam Search 算法

具有弹性约束和模糊工期的项目调度问题是一类具有实际应用意义但难于解决的问题.传统BS(Beam Search)方法存在常数线宽大小影响求解效果的问题.本文建立了此类项目调度问题的模型,并将序优化理论思想与BS方法结合,提出一种通过计算和改变线宽,兼顾解的质量和求解速度的变宽BS调度算法.仿真计算结果表明,该算法能够在较短时间内得到满意的调度结果,适用于实际模糊项目调度决策.     

蚁群优化算法在物流车辆调度系统中的应用

根据对蚁群算法进行的深入研究,指出了蚁群算法在解决大型非线性系统优化问题时的优越性。通过仔细分析遗传算法和粒子群算法在解决物流车辆调度系统问题的不足之处,基于蚁群算法的优点,并根据物流车辆调度系统自身的特点,对基本蚁群算法进行适当的改进,给出算法框架。并且以线性规划理论为基础,建立物流车辆系统的数学模型,给出调度目标与约束条件,用改进后的蚁群算法求解物流车辆调度系统的问题,求得最优解,根据最优解和调度准则进行实时调度。使用Java语言编写模拟程序对比基于改进粒子群算法和改进蚁群算法的调度程序。通过对比证明了所提出的改进蚁群算法解决物流车辆调度优化问题的正确性和有效性     

基于Min—Min和蚁群算法的网格任务调度方法

网格任务调度是网格计算的研究热点,也是一个NP难问题。文章结合Min-Min算法和蚁群算法的优点,提出了一种基于Min—Min群算法（MMACO）的任务调度方法。仿真实验表明：在网格环境下,该算法具有较好的全局最优求解能力和较快的收敛速度。     

面向哈佛体系结构的集装箱码头场桥作业调度

集装箱码头堆场作业调度问题一直是国内外相关研究的热点和难点,但由于码头作业的动态性、开放性、强耦合性和复杂性,堆场主要装卸设备场桥的调度配置问题一直未能有较好的解决方案。故提出面向哈佛体系结构的基于Agent建模和仿真模式,并将计算机操作系统中的磁盘臂调度算法和基于仿真的优化思想引入到上述模型中。通过构建相应的多Agent系统仿真得出敏捷高效鲁棒的场桥调度和配置解决方案,从而帮助集装箱码头提高服务水平和竞争力。     

基于TS的动态车辆调度问题的混合算法研究

对带时间窗的动态车辆调度问题进行分析,采用实时再优化方法进行研究,引入时间轴概念,建立动态车辆调度模型,并给出求解的混合禁忌搜索算法。该算法先用C-K节约算法求得初始解,然后用禁忌搜索进行优化,得到全局最优解。禁忌搜索算法中采用动态邻域移动方法构造候选解和动态禁忌长度选取策略设置紧急长度,提高算法的收敛速度。最后用实例证明该混合算法的可行性和有效性。     

Integrating simulation and optimization to schedule loading operations in container terminals

In this paper, a simulation optimization method for scheduling loading operations in container terminals is developed. The method integrates the intelligent decision mechanism of optimization algorithm and evaluation function of simulation model, its procedures are: initializing container sequence according to certain dispatching rule, then improving the sequence through genetic algorithm, using simulation model to evaluate objective function of a given scheduling scheme. Meanwhile, a surrogate model based on neural network is designed to predict objective function and filter out potentially bad solutions, thus to decrease the times of running simulation model. Numerical tests show that simulation optimization method can solve the scheduling problem of container terminals efficiently. And the surrogate model can improve the computation efficiency of simulation optimization.     

低空复杂环境下基于采样空间约减的无人机在线航迹规划算法

针对低空复杂环境下障碍物密集且类型多样、带有多通道并存在不确定信息的无人机在线航迹规划问题,为了减少碰撞检测次数,提高航迹搜索速度,降低航迹代价,提出一种基于采样空间约减的无人机在线航迹规划算法. 算法通过引入代价模型,提出约减域逐步构造方法,引导规划树快速有效扩展,改善了基于动态域的快速拓展随机树（Dynamic domain rapidly-exploring random tree,DDRRT） 算法中存在的采样空间过度约减问题. 算法通过密度划分索引的方法逐步构建多棵Kd 树（K-dimensional tree）并采用多近邻节点搜索方法,加快了近邻树节点搜索速度. 仿真实验结果表明,与DDRRT方法相比,该方法在保证对采样空间约减合理性的同时,提高了航迹规划效率和通道内的寻路能力.     

Minimizing total earliness and tardiness on a single machine using a hybrid heuristic

This paper focuses on scheduling jobs with different processing times and distinct due dates on a single machine with no inserted idle time as to minimize the sum of total earliness and tardiness. This scheduling problem is a very important and frequent industrial problem that is common to most just-in-time production environments. This NP hard scheduling problem is herein solved using a hybrid heuristic which combines local search heuristics (dispatching rules, hill climbing and simulated annealing) and an evolutionary algorithm based on genetic algorithms. The heuristic involves low and high, relay and teamwork hybridization. Computational results reflect the sizeable solution quality improvement induced by hybridization, and assess the impact of each type of hybridization on the efficiency of the hybrid heuristic.     

基于改进粒子群算法的物流配送车辆调度

物流配送车辆调度问题是指安排有限的车辆有效地完成配送任务。优化目标是在满足客户需求和车辆能力约束的条件下,找出配送成本较低的配送车辆调度方案。由于配送过程受客户位置、配送车辆限制等多种因素影响,导致车辆的调度问题十分复杂。参照经典车辆路径问题模型,考虑了车辆配送里程和用户数等限制,建立了双向车辆调度问题的数学模型。在标准粒子群算法的基础上,引入爬山操作,增加了粒子群的多样性,提高了算法的局部搜索能力,并设计了基于改进粒子群算法的物流配送车辆调度算法,有效地解决了物流配送车辆的优化调度问题。     

Scheduling activities at oil wells with resource displacement

Before promising locations at petroliferous basins become productive oil wells, it is necessary to complete development activities at these locations. The scheduling of such activities must satisfy several conflicting constraints and attain a number of goals. Moreover, resource displacements between wells are important and must also be taken into account. The problem is NP‐hard, as can be seen by a simple poly‐time reduction from the Job Shop problem. This paper describes Greedy Randomized Adaptive Search Procedures (GRASPs) for the scheduling of oil well development activities with resource displacement. The heuristics were tested on real instances from a major oil company, recognized for its expertise in offshore oil exploration. Computational experiments over real instances revealed that the GRASP implementations are competitive, outperforming the software currently being used by the company.     

集装箱码头装卸桥调度优化模型与算法

研究装卸桥调度优化问题,以提高集装箱码头装卸效率。首先,建立了混合整数规划模型,模型充分考虑了集装箱装卸桥调度优化中的各种约束条件及特点。为了求解设计了基于遗传算法的求解方法,并且采用随机贪婪适应性搜索方法对算法进行改进。最后,通过实际算例对模型与算法的有效性进行了验证。     

Coupling Genetic Local Search and Recovering Beam Search algorithms for minimizing the total completion time in the single machine scheduling problem subject to release dates

In this paper we consider the well-known single machine scheduling problem with release dates and minimization of the total job completion time. For solving this problem, denoted by 1|r_j|∑C_j, we provide a new metaheuristic which is an extension of the so-called filtered beam search proposed by Ow and Morton [30]. This metaheuristic, referred to as a Genetic Recovering Beam Search (GRBS), takes advantages of a Genetic Local Search (GLS) algorithm and a Recovering Beam Search (RBS) in order to efficiently explore the solution space. In this paper we present the GRBS framework and its application to the 1|r_j|∑C_j problem. Computational results show that it consistently yields optimal or near-optimal solutions and that it provides interesting results by comparison to GLS and RBS algorithms. Moreover, these results highlight that the proposed algorithm outperforms the state-of-the-art heuristics.     

集装箱码头装卸作业的调度控制模型及算法设计

对集装箱码头上装卸作业的调度控制直接影响码头的整体运营效率．本文研究了集装箱码头装卸作业的调度控制问题,提出了一个基于柔性化flow shop的集成化控制模型．该问题具有非线性规划(NP：non- polynomial)难度,因此本文开发设计了两类基于优先级规则的启发式调度算法．利用该模型来对码头中多种装卸设备进行总体调度可以提高设备之间的协调性,提高码头效率,降低成本．实验研究证明算法能有效地解决该问题．     

Queue-based local scheduling and global coordination for real-time operation control in a container terminal

To maximize the productivity of a container terminal, the operations of various types of equipments should be optimized and synchronized in real time. However, use of optimization techniques such as mathematical programming or search-based meta-heuristics becomes difficult when given a large-scaled problem due to their high computational cost. Addressing this problem, the queue-based local scheduling and global coordination method proposed in this paper stands as a viable alternative. The method consists of the following steps. First, separate schedules are locally generated for each equipment type using a queue-based dispatching heuristic which pays attention to the queue lengths of the quay cranes (QCs) under service. Next, the schedules are executed via a simulation and a notable QC delay is identified. Based on the analysis on the causes of this delay, some compromising adjustments are made to the priorities of relevant jobs. Then, the localized scheduling followed by the adjustment is repeated until the termination condition is met. Adopting simple heuristics in the local scheduling phase, the overall process easily meets the real-time constraint, yet producing an integrated schedule with a better global perspective than the myopic heuristic-only approach.     

Quay crane and yard truck dual-cycle scheduling with mixed storage strategy

In order to enhance the efficiency of port operations, the scheduling problem of the quay cranes and yard trucks is crucial. Conventional port operation mode lacks optimization research on efficiency of port handling operation, yard truck scheduling, and container storage location. To make quay crane operations and horizontal transportation more efficient, this study uses a dual-cycle strategy to focus on a quay crane and yard truck scheduling problem in conjunction with a mixed storage strategy. A dispatching plan for yard trucks is considered, as well as the storage location of inbound containers. Based on the above factors, a mixed-integer programming model is formulated to minimize vessels’ berth time for completing all tasks. The proposed model is solved using a particle swarm optimization-based algorithm. Validation of the proposed model and algorithm is conducted through numerical experiments. Additionally, some managerial implications which may be potentially useful for port operators are obtained.     

面向多星观测调度的启发式算法研究

以实际应用任务为背景进行动态仿真分析,是科学评价卫星系统能力进而支持卫星系统发展建设规划的重要手段。探讨了一类涉及多星、多地面站、多任务的航天观测系统联合调度问题。考虑到仿真环境对调度算法的高时效性要求,提出了一种快速高效的基于规则的启发式构造算法。与禁忌搜索算法的比较结果表明,该文算法在求解速度上具有明显的优越性,并且能够获得相对满意的求解质量。