Asymptotic Analysis of a Greedy Heuristic for the Multi-Period Single-Sourcing Problem: The Acyclic Case

The multi-period single-sourcing problem that we address in this paper can be used as a tactical tool for evaluating logistics network designs in a dynamic environment. In particular, our objective is to find an assignment of customers to facilities, as well as the location, timing and size of production and inventory levels, that minimizes total assignment, production, and inventory costs. We propose a greedy heuristic, and prove that this greedy heuristic is asymptotically optimal in a probabilistic sense for the subclass of problems where the assignment of customers to facilities is allowed to vary over time. In addition, we prove a similar result for the subclass of problems where each customer needs to be assigned to the same facility over the planning horizon, and where the demand for each customer exhibits the same seasonality pattern. We illustrate the behavior of the greedy heuristic, as well as some improvements where the greedy heuristic is used as the starting point of a local interchange procedure, on a set of randomly generated test problems. These results suggest that the greedy heuristic may be asymptotically optimal even for the cases that we were unable to analyze theoretically.     

A heuristic methodology for sizing a large-scale system of constrained, reusable resources

This paper proposes a methodology for sizing certain large-scale systems of reusable, capacity-constrained resources engaged in tasks of varying duration. A heuristic program schedules resources throughout a finite planning horizon using two decision variables: varying resource capacity for meeting demand and varying task duration. A model of the problem and heuristic scheduling program are presented. A sequential, iterative sizing procedure determines the number of system resources to meet demand at each stage of the problem. Results compare the methodology with heuristics used in practice to schedule resources and size a real-world, large-scale training system.     

Studies on optimal topology design of structures with discrete variables

Some problems in the optimal topology design of structures with discrete variables are studied in this paper. The problem of a model of discrete optimization is discussed and a neglected fact that discrete optimum design may be controlled by the discreteness of sizing variables and global constraints is pointed out. A heuristic algorithm for solving discrete topology optimization problems of trusses and frames is proposed.     

A Comparison of Heuristics for the Discrete Cost Multicommodity Network Optimization Problem

In this paper, approximate solutions algorithms for discrete cost multicommodity network optimization problems are presented and compared. Firstly, extensions of classical greedy heuristics, based on link-rerouting and flow-rerouting heuristics, are presented in details. Secondly, a new approximate solution algorithm, which basically consists of a heuristic implementation of the exact Benders-type cutting plane generation method, is proposed. All these algorithms are extensively compared on randomly generated graphs up to 50 nodes and 90 links. It clearly appears that this new Benders-type approach is very promising since it produces the best heuristic solutions.     

A Hybrid Heuristic for the p-Median Problem

Given n customers and a set F of m potential facilities, the p-median problem consists in finding a subset of F with p facilities such that the cost of serving all customers is minimized. This is a well-known NP-complete problem with important applications in location science and classification (clustering). We present a multistart hybrid heuristic that combines elements of several traditional metaheuristics to find near-optimal solutions to this problem. Empirical results on instances from the literature attest the robustness of the algorithm, which performs at least as well as other methods, and often better in terms of both running time and solution quality. In all cases the solutions obtained by our method were within 0.1% of the best known upper bounds.     

基于彩色离焦模糊图像清晰度评价的启发式调焦算法

运用启发式搜索策略提出了一种基于彩色离焦模糊图像清晰度评价的启发式调焦算法。算法采用了以2为模的Sobel算子梯度建立图像清晰度评价函数的数学模型。该评价函数具有无偏性好，单峰性强，灵敏度高，在焦平面变化趋势明显等特点。我们给出了结合启发式搜索策略的具体算法。实验结果证明，所提出的启发式调焦算法精度高，可重复性强，并对图像噪声具有良好的鲁棒性。     

流水车间作业排序问题蚁群算法研究

本文运用蚁群算法研究辨台处理机、目标函数为时间表长最小的同顺序排列流水车间作业排序问题，设计出解决该问题的算法步骤与流程。最后，通过仿真比较该算法与解决该问题的其它启发式算法性能，计算效果比较满意。     

Global Optimization Approach to Unequal Global Optimization Approach to Unequal Sphere Packing Problems in 3D

The problem of the unequal sphere packing in a 3-dimen-sional polytope is analyzed. Given a set of unequal spheres and a poly-tope, the double goal is to assemble the spheres in such a way that (i) they do not overlap with each other and (ii) the sum of the volumes of the spheres packed in the polytope is maximized. This optimization has an application in automated radiosurgical treatment planning and can be formulated as a nonconvex optimization problem with quadratic constraints and a linear objective function. On the basis of the special structures associated with this problem, we propose a variety of algorithms which improve markedly the existing simplicial branch-and-bound algorithm for the general nonconvex quadratic program. Further, heuristic algorithms are incorporated to strengthen the efficiency of the algorithm. The computational study demonstrates that the proposed algorithm can obtain successfully the optimization up to a limiting size.     

组合截面工程结构离散变量优化设计的通用模型及启发式算法

建立了组合截面离散变量优化设计的通用模型;提出了一种启发式求解算法。通过对截面设计变量的合并,把截面整体作为一个设计变量;将约束条件按其作用范围分为三类:局部约束、全局约束、中间约束,即介于局部和全局约束之间的约束;根据离散结构实体杆件在结构中受力和传力的特点,将杆件分为5类。针对三类约束的不同特点,分别给出了启发式求解算法。最后通过一个三维的空间结构实例给出验证,优化效率高,效果明显。六个工程实例的优化结果比经验设计可节省材料5.0～19.0%。实践表明本文提出的模型通用性强,启发式求解方法效率高且实用,适合大规模离散变量工程结构最轻设计问题。     

基于贪婪禁忌搜索算法的垂岸式堆场出口箱装船翻箱研究

基于垂岸式自动化集装箱码头不同装船周期出口集装箱堆场多贝位混合堆存、场桥大车在贝位间频繁移动取箱装船特点,考虑装船发箱时场桥移动等操作时间及翻箱取箱次数对出口箱装船效率和连续性影响,建立多贝位出口箱装船堆场翻箱模型,提出两阶段贪婪禁忌搜索算法,将翻箱规则嵌入算法中,有效限制算法时间和解空间增长速度。通过算例,将提出的翻箱规则与现有常见翻箱规则进行对比,验证模型及算法的有效性与实用性。结果表明,提出的模型和算法可以在合理的求解时间内输出较优的翻箱方案,减少装船时场桥发箱作业时间,提高装船作业效率。