The dynamic frequency assignment problem

In this paper, we consider a frequency assignment problem occurring in a military context. The main originality of the problem pertains to its dynamic dimension: new communications requiring frequency assignments need to be established throughout a battlefield deployment. The problem resolution framework decomposes into three phases: assignment of an initial kernel of communications, dynamic assignment of new communication links and a repair process when no assignment is possible. Different solution methods are proposed and extensive computational experiments are carried out on realistic instances.     

Fixed interval scheduling: Models,applications, computational complexity and algorithms

The defining characteristic of fixed interval scheduling problems is that each job has a finite number of fixed processing intervals. A job can be processed only in one of its intervals on one of the available machines, or is not processed at all. A decision has to be made about a subset of the jobs to be processed and their assignment to the processing intervals such that the intervals on the same machine do not intersect. These problems arise naturally in different real-life operations planning situations, including the assignment of transports to loading/unloading terminals, work planning for personnel, computer wiring, bandwidth allocation of communication channels, printed circuit board manufacturing, gene identification and examining computer memory structures. We present a general formulation of the interval scheduling problem, show its relations to cognate problems in graph theory, and survey existing models, results on computational complexity and solution algorithms.     

Frequency assignment in a SDMA satellite communication system with beam decentring feature

In satellite communication, Spatial Division Multiple Access (SDMA) has become one of the most promising techniques that can accommodate continuing increase in the number of users and traffic demands. The technology is based on radio resource sharing that separates communication channels in space. It relies on adaptive and dynamic beam-forming technology and well-designed algorithms for resource allocation among which frequency assignment is considered. This paper studies static Frequency Assignment Problem (FAP) in a satellite communication system involving a satellite and a number of users located in a service area. The objective is to maximize the number of users that the system can serve while maintaining the signal to interference plus noise ratio of each user under a predefined threshold. Traditionally, interference is treated as fixed (binary interferences or fixed minimal required separation between frequencies) . In this paper, the interference is cumulative and variable. To solve the problem, we work on both discrete and continuous optimizations. Integer linear programming formulations and greedy algorithms are proposed for solving the discrete frequency assignment problem. The solution is further improved by beam decentring algorithm which involves continuous adjustment of satellite beams and deals with non-linear change of interference.     

多无线WMN中干扰最小化信道分配算法研究

为了提高无线迈适网的通信容量,网络中的每个路由节点均配备有多个无线网卡,并提供多个可用的无线信道.如何将这些信道合理地分配到网络的各个通信链路上,使得整个网络的干扰最小是一个至关重要问题.分析了基于禁忌搜索的信道分配算法,并针对该算法存在的问题,提出了初步的改进算法.     

Heuristic Solution Methods for the Multilevel Generalized Assignment Problem

The multilevel generalized assignment problem is a problem of assigning agents to tasks where the agents can perform tasks at more than one efficiency level. A profit is associated with each assignment and the objective of the problem is profit maximization. Two heuristic solution methods are presented for the problem. The heuristics are developed from solution methods for the generalized assignment problem. One method uses a regret minimization approach whilst the other method uses a repair approach on a relaxation of the problem. The heuristics are able to solve moderately large instances of the problem rapidly and effectively. Procedures for deriving an upper bound on the solution of the problem are also described. On larger and harder instances of the problem one heuristic is particularly effective.     

Random assignment problems

Analysis of random instances of optimization problems provides valuable insights into the behavior and properties of problem’s solutions, feasible region, and optimal values, especially in large-scale cases. A class of problems that have been studied extensively in the literature using the methods of probabilistic analysis is represented by the assignment problems, and many important problems in operations research and computer science can be formulated as assignment problems. This paper presents an overview of the recent results and developments in the area of probabilistic assignment problems, including the linear and multidimensional assignment problems, quadratic assignment problem, etc.     

A facet generation and relaxation technique applied to an assignment problem with side constraints

We consider a solution method for combinatorial optimization problems based on a combination of Lagrangean relaxation and constraint generation techniques. The procedure is applied to a constrained assignment problem, where subsets of variables are specified, and variables belonging to the same subset must have the same value. The model can be applied to solve constrained job assignment or classroom assignment problems. The procedure we suggest requires only the solution of classical assignment subproblems. An illustrative numerical example is given.     

Test Problem Generator for the Multidimensional Assignment Problem

The multidimensional assignment problem (MAPs) is a higher dimensional version of the standard linear assignment problem. Test problems of known solution are useful in exercising solution methods. A method of generating an axial MAP of controllable size with a known unique solution is presented. Certain characteristics of the generated MAPs that determine realism and difficulty are investigated.     

On A Special Case of the Quadratic Assignment Problem with an Application to Storage-and-Retrieval Devices

In a storage-and-retrieval device, items are retrieved on demand from a storage bank by a picking mechanism. Many varieties of these robotic devices are in use in manufacturing, logistics and computer peripherals. In printed circuit board manufacturing, storage-and-retrieval is intertwined with component placement and product clustering. Under certain circumstances, the problem of assigning items by type to storage slots to minimize the expected retrieval time is a quadratic assignment problem. Although such models are very difficult to solve to optimality, an important special case considered here admits an easy solution, namely, the well known “organ pipe” arrangement of items.     

Traffic assignment in communication satellites

A high capacity communication satellite interconnects scores of ground stations simultaneously. Under the Satellite-Switched/Time Division Multiple Access (SS/TDMA) system, each channel of the satellite is allocated to a pair of ground stations for a certain time period, after which the whole set of allocations (called a switch) is changed simultaneously. The problem we address is to minimize the time length of the entire sequence of switches, subject to a limit on the number of switches. We formulate this as a 3-index bottleneck-sum assignment problem, and solve it by a heuristic that obtains consistently better results than earlier methods based on different formulations.     

Models and algorithms for the optimization of signal settings on urban networks with stochastic assignment models

In this paper models and algorithms for the optimization of signal settings on urban networks are proposed. Two different approaches to the solution of the problem may be identified: a global approach (optimization of intersection signal settings on the whole network) and a local approach (optimization of signal settings intersection by intersection). For each approach a different optimization model and some solution algorithms are proposed; both models and algorithms are based on the assumptions of within-day static system and stochastic user equilibrium assignment models. The paper includes numerical results on test networks and a comparison between the two approaches.     

On iterative optimization ol structured Markov decision processes with discounted rewards

The paper gives a survey on solution techniques for Markov decision processes with respect to the total reward criterion. We will discuss briefly a number of problem structures which guarantee that the optimal policy possesses a specific structure which can be exploited in numerical solution procedures. However, the main emphasis is on iterative methods. It is shown by examples that the effect of a number of modifications of the standard iterative method, which are advocated in the literature, is limited in some realistic situations. Numerical evidence is provided to show that exploiting the structure of a problem under consideration of ten yields a more substantial reduction of the required computational effort than some of the existing acceleration procedures.

We advocate that this structure should be analyzed and used in choosing the appropriate solution procedure. The appropriate procedure might be composed on one hand by blending several of the acceleration concepts that are described in literature. On the other hand it should exploit the structure of optimal policies. This latter can often be done by using monotonicity properties of the computed value vector or policy. To illustrate the influence of the structure of a problem and if available, the structure of optimal policies, we sketch and solve four test problems with several successive approximation methods. In the final part of the paper, the required computational efforts are compared.     

人力资源多维分配问题的混合算法

针对已有多维分配问题求解算法复杂、耗时长及精度低等问题,本文将二部图中寻求最优匹配的方法进行推广,运用试分配、饱和路调整和增广路调整对多维分配问题的最优解进行搜索,提出了求解人力资源多维分配问题的最小零面优先分配混合算法和随机试分配混合算法,对算法的有效性进行了理论证明,并分析了算法的时间和空间复杂度;同时通过这两种混合算法对初始零元素数不同的代价矩阵求解时间的计算,以及与Lagrangian松弛算法和剪枝法的耗时、精度的对比,分别得到了两种混合算法的适用性和高效性,最后通过算例验证了算法的有效性。     

Assignment problems: A golden anniversary survey

Having reached the 50th (golden) anniversary of the publication of Kuhn’s seminal article on the solution of the classic assignment problem, it seems useful to take a look at the variety of models to which it has given birth. This paper is a limited survey of what appear to be the most useful of the variations of the assignment problem that have appeared in the literature over the past 50 years. The intention here is not to identify every such paper (of which there have been hundreds) nor to identify the best solution procedure for each variation. Rather, the intention is to identify what these variations are and what they are called so as to make it easier for a researcher trying to develop some variation of the assignment problem for a particular application to find the relevant literature.     

Robust Capacity Assignment in Telecommunications

In telecommunications, the demand is a key data that drives network planning. The demand exhibits considerable variability, due to customers movement and introduction of new services and products in the present competitive markets. To deal with this uncertainty, we consider capacity assignment problem in telecommunications in the framework of robust optimization proposed in Ben-Tal and Nemcrovski (Math Oper Res 23(4):769–805, 1998, MPS-SIAM series on optimization, 2001) and Kouvelis and Yu. We propose a decomposition scheme based on cutting plane methods. Some preliminary computational experiments indicate that the Elzinga–Moore cutting plane method (Elzinga and Moore in Math Program 8:134–145, 1975) can be a valuable choice. Since in some situations different possible uncertainty sets may exist, we propose a generalization of these models to cope at a time with a finite number of plausible uncertainty sets. A weight is associated with each uncertainty set to determine its relative importance or worth against another.     

A simple dual algorithm for the generalised assignment problem

A new algorithm for the generalised assignment problem is described in this paper. The dual-type algorithm uses a simple heuristic derived from a relaxation of the problem. The algorithm has been tested on generalised assignment problems of substantial size and compared to an exact integer programming approach and a well-established heuristic approach. Computational results look promising in terms of speed and solution quality.     

Asymptotic Results for Random Multidimensional Assignment Problems

The multidimensional assignment problem (MAP) is an NP-hard combinatorial optimization problem occurring in applications such as data association and target tracking. In this paper, we investigate characteristics of the mean optimal solution values for random MAPs with axial constraints. Throughout the study, we consider cost coefficients taken from three different random distributions: uniform, exponential and standard normal. In the cases of uniform and exponential costs, experimental data indicates that the mean optimal value converges to zero when the problem size increases. We give a short proof of this result for the case of exponentially distributed costs when the number of elements in each dimension is restricted to two. In the case of standard normal costs, experimental data indicates the mean optimal value goes to negative infinity with increasing problem size. Using curve fitting techniques, we develop numerical estimates of the mean optimal value for various sized problems. The experiments indicate that numerical estimates are quite accurate in predicting the optimal solution value of a random instance of the MAP.