Heuristics for Distribution Network Design in Telecommunication

A distribution network problem arises in a lower level of an hierarchical modeling approach for telecommunication network planning. This paper describes a model and proposes a lagrangian heuristic for designing a distribution network. Our model is a complex extension of a capacitated single commodity network design problem. We are given a network containing a set of sources with maximum available supply, a set of sinks with required demands, and a set of transshipment points. We need to install adequate capacities on the arcs to route the required flow to each sink, that may be an intermediate or a terminal node of an arborescence. Capacity can only be installed in discrete levels, i.e., cables are available only in certain standard capacities. Economies of scale induce the use of a unique higher capacity cable instead of an equivalent set of lower capacity cables to cover the flow requirements of any link. A path from a source to a terminal node requires a lower flow in the measure that we are closer to the terminal node, since many nodes in the path may be intermediate sinks. On the other hand, the reduction of cable capacity levels across any path is inhibited by splicing costs. The objective is to minimize the total cost of the network, given by the sum of the arc capacity (cables) costs plus the splicing costs along the nodes. In addition to the limited supply and the node demand requirements, the model incorporates constraints on the number of cables installed on each edge and the maximum number of splices at each node. The model is a NP-hard combinatorial optimization problem because it is an extension of the Steiner problem in graphs. Moreover, the discrete levels of cable capacity and the need to consider splicing costs increase the complexity of the problem. We include some computational results of the lagrangian heuristics that works well in the practice of computer aided distribution network design.     

Dual mean field annealing scheme for binary optimization under linear constraints

It is shown that certain general classes of constrained binary optimization tasks can be solved with increasing accuracy by a first order mean field approximation of the Boltzmann distribution of the associated Lagrangian as the instance size grows. The formalism is thoroughly analyzed for the quadratic and multidimensional knapsack models. In these cases analytical expressions for the convergence of the optimality gaps are given, which are experimentally verified.     

Analysis of heuristics for finding a maximum weight planar subgraph

The problem of identifying a planar subgraph of maximum total weight in an edge-weighted graph has application to the layout of facilities in a production system and elsewhere in industrial engineering.This problem is NP-hard, and so we confine our attention to polynomial-time heuristics. In this paper we analyse the performance of some heuristics for this problem.     

A comparison of average and discounted cost models for the dynamic lot size inventory problem

It is a common practice in the inventory literature to use average cost models as approximations to the theoretically correct discounted cost models. An average cost model minimizes the average undiscounted cost per period, while a discounted cost model minimizes the total discounted cost over the problem horizon. This paper attempts to answer an important question: How good are the results (the total discounted costs) for the average cost models compared to those for the discounted cost models? This question has been conclusively answered for the simplest inventory model where the demand rate and other parameters are assumed to remain constant in time. This paper addresses this issue for the first time for the case where demand rates are allowed to be nonstationary in time.A discounted cost model has been developed in the paper to carry out this comparison. It is shown that a simple dynamic programming algorithm can be used to find optimal order policies for the discounted cost model.The effect of the varying interest rates and other parameters on the relative performance of the average cost model has been studied by developing an insightful analysis and also by doing a computational study. The results show that, while the average cost model can cost as much as about 26% more than the discounted cost model in extreme cases, this increase is not significant for the parameter values in the range of the common interest.     

A large scale machine loading problem in flexible assembly

Flexible manufacturing is characterized by versatile work stations with minimum change over times and a versatile material handling system. The loading problem in flexible manufacturing is to assign tools, material, operations and jobs to work stations in order to minimize the total number of job-to-work station assignments. In this paper, we describe a special case of the general loading problem applied to flexible assembly and develop a discrete optimization model. We then discuss approaches for obtaining good heuristic solutions and present results for a large scale study.     

A five facets frame for the design of heuristics

The author suggested to distinguish between the ‘engineering approach’ and the ‘mathematical approach’ in connection with the design of heuristics. Stainton and Papoulias extended the scope by suggesting the ‘relational approach’. Based upon this extension, a five facets frame is presented here which is suggested to precede and accompany the ‘technical’ design of the heuristic. The facets are: coverage by participation, experience by doing, abstraction by structuring, extension by comparison, exploration by creativity.     

Approximation schemes for the subset-sum problem: Survey and experimental analysis

Given a set of n positive integers w₁,…,w_n and a positive integer W, the Subset-Sum Problem is to find that subset whose sum is closest to, without exceeding, W. The most important heuristics for this problem are approximation schemes based on a worst-case analysis. We survey them and experimentally analyze their statistical behaviour on a large number of test problems.     

求解资源约束项目调度问题的启发式算法综述

本文综述了求解RCPSP的启发式算法.首先在对各种优先权规则进行归纳的基础上,概述基于优先权规则的RCPSP启发式算法研究现状;其次,综述项目进度的表述方式及常用超启发式策略,汇总求解RCPSP的超启发式算法的研究成果.此外,简要介绍除上述两大类启发式算法之外的其他几种启发式算法;最后,对全文进行总结,并指出该领域几个有希望的研究方向.     

A Computational Study of Shifting Bottleneck Procedures for Shop Scheduling Problems

We examine the performance of Shifting Bottleneck (SB) heuristics for shop scheduling problems where the performance measure to be minimized is makespan (C _max) or maximum lateness (L _max). Extensive computational experiments are conducted on benchmark problems from the literature as well as several thousand randomly generated test problems with three different routing structures and up to 1000 operations. Several different versions of SB are examined to determine the effect on solution quality and time of different subproblem solution procedures, reoptimization procedures and bottleneck selection criteria. Results show that the performance of SB is significantly affected by job routings, and that SB with optimal subproblem solutions and full reoptimization at each iteration consistently outperforms dispatching rules, but requires high computation times for large problems. High quality subproblem solutions and reoptimization procedures are essential to obtaining good solutions. We also show that schedules developed by SB to minimize L _max perform well with respect to several other performance measures, rendering them more attractive for practical use.     

Production scheduling with applications in the printing industry

This paper presents a technique for the solution of scheduling problems encountered in a printing company that can be applied to a range of practical industrial problems. The aim of the research was to develop a due date scheduling algorithm within the framework of the scheduling system already in use by the company. The objective was to enable jobs to be scheduled as close to their due dates as possible, while ensuring that the resultant schedule was feasible with respect to work centre capacities and earliest start date constraints.