Home About us Contact
|
Home About us Contact | ||
|
|
||
Assignment Problem (assignment + problem)
Kinds of Assignment Problem Selected AbstractsMeta-Optimization Using Cellular Automata with Application to the Combined Trip Distribution and Assignment System Optimal ProblemCOMPUTER-AIDED CIVIL AND INFRASTRUCTURE ENGINEERING, Issue 6 2001Wael M. ElDessouki In this paper, meta-optimization and cellular automata have been introduced as a modeling environment for solving large-scale and complex transportation problems. A constrained system optimum combined trip distribution and assignment problem was selected to demonstrate the applicability of the cellular automata approach over classical mixed integer formulation. A mathematical formulation for the selected problem has been developed and a methodology for applying cellular automata has been presented. A numerical example network was used to illustrate the potential for using cellular automata as a modeling environment for solving optimization problems. [source] Survivable wavelength-routed optical network design using genetic algorithmsEUROPEAN TRANSACTIONS ON TELECOMMUNICATIONS, Issue 3 2008Y. S. Kavian The provision of acceptable service in the presence of failures and attacks is a major issue in the design of next generation dense wavelength division multiplexing (DWDM) networks. Survivability is provided by the establishment of spare lightpaths for each connection request to protect the working lightpaths. This paper presents a genetic algorithm (GA) solver for the routing and wavelength assignment problem with working and spare lightpaths to design survivable optical networks in the presence of a single link failure. Lightpaths are encoded into chromosomes made up of a fixed number of genes equal to the number of entries in the traffic demand matrix. Each gene represents one valid path and is thus coded as a variable length binary string. After crossover and mutation, each member of the population represents a set of valid but possibly incompatible paths and those that do not satisfy the problem constraints are discarded. The best paths are then found by use of a fitness function and these are assigned the minimum number of wavelengths according to the problem constraints. The proposed approach has been evaluated on dedicated path protection and shared path protection. Simulation results show that the GA method is efficient and able to design DWDM survivable real-world optical mesh networks. Copyright © 2007 John Wiley & Sons, Ltd. [source] A Combined Cluster and Interaction Model: The Hierarchical Assignment ProblemGEOGRAPHICAL ANALYSIS, Issue 3 2005Mark W. Horner This article presents a new spatial modeling approach that deals with interactions between individual geographic entities. The developed model represents a generalization of the transportation problem and the classical assignment problem and is termed the hierarchical assignment problem (HAP). The HAP optimizes the spatial flow pattern between individual origin and destination locations, given that some grouping, or aggregation of individual origins and destinations is permitted to occur. The level of aggregation is user specified, and the aggregation step is endogenous to the model itself. This allows for the direct accounting of aggregation costs in pursuit of optimal problem solutions. The HAP is formulated and solved with several sample data sets using commercial optimization software. Trials illustrate how HAP solutions respond to changes in levels of aggregation, as well as reveal the diverse network designs and allocation schemes obtainable with the HAP. Connections between the HAP and the literature on the p-median problem, cluster analysis, and hub-and-spoke networks are discussed and suggestions for future research are made. [source] An efficient MAC protocol for multi-channel mobile ad hoc networks based on location informationINTERNATIONAL JOURNAL OF COMMUNICATION SYSTEMS, Issue 8 2006Yu-Chee Tseng Abstract This paper considers the channel assignment problem in a multi-channel MANET environment. We propose a scheme called GRID, by which a mobile host can easily determine which channel to use based on its current location. In fact, following the GSM style, our GRID spends no communication cost to allocate channels to mobile hosts since channel assignment is purely determined by hosts' physical locations. We show that this can improve the channel reuse ratio. We then propose a multi-channel MAC protocol, which integrates GRID. Our protocol is characterized by the following features: (i) it follows an ,on-demand' style to access the medium and thus a mobile host will occupy a channel only when necessary, (ii) the number of channels required is independent of the network topology, and (iii) no form of clock synchronization is required. On the other hand, most existing protocols assign channels to a host statically even if it has no intention to transmit [IEEE/ACM Trans. Networks 1995; 3(4):441,449; 1993; 1(6): 668,677; IEEE J. Selected Areas Commun. 1999; 17(8):1345,1352], require a number of channels which is a function of the maximum connectivity [IEEE/ACM Trans. Networks 1995; 3(4):441,449; 1993; 1(6): 668,677; Proceedings of IEEE MILCOM'97, November 1997; IEEE J. Selected Areas Commun. 1999; 17(8):1345,1352], or necessitate a clock synchronization among all hosts in the MANET [IEEE J. Selected Areas Commun. 1999; 17(8):1345,1352; Proceedings of IEEE INFOCOM'99, October 1999]. Through simulations, we demonstrate the advantages of our protocol. Copyright © 2005 John Wiley & Sons, Ltd. [source] Heuristic and simulated annealing algorithms for solving extended cell assignment problem in wireless ATM networksINTERNATIONAL JOURNAL OF COMMUNICATION SYSTEMS, Issue 1 2002Der-Rong Din Abstract In this paper, we investigate the extended cell assignment problem which optimally assigns new adding and splitting cells in Personal Communication Service (PCS) to switches in a wireless Asynchronous Transfer Mode (ATM) network. Given cells in a PCS network and switches on an ATM network (whose locations are fixed and known), we would like to do the assignment in an attempt to minimize a cost criterion. The cost has two components: one is the cost of handoffs that involve two switches, and the other is the cost of cabling. This problem is modeled as a complex integer programming problem, and finding an optimal solution to this problem is NP-hard. A heuristic algorithm and a simulated annealing algorithm are proposed to solve this problem. The heuristic algorithm, Extended Assignment Algorithm (EEA), consists of two phases, initial assigning phase and cell exchanging phase. First, in the initial assigning phase, the initial assignments of cells to switches are found. Then, these assignments are improved by performing cell exchanging phase in which two cells are repeatedly exchanged in different switches with great reduction of the total cost. The simulated annealing algorithm, ESA (enhanced simulated annealing), generates constraint-satisfied configurations, and uses three configuration perturbation schemes to change current configuration to a new one. Experimental results indicate that EAA and ESA algorithms have good performances. Copyright © 2002 John Wiley & Sons, Ltd. [source] A robust approach to the UAV task assignment problemINTERNATIONAL JOURNAL OF ROBUST AND NONLINEAR CONTROL, Issue 2 2008Mehdi Alighanbari Abstract This paper presents a new robust approach to the task assignment of unmanned aerial vehicles (UAVs) operating in uncertain dynamic environments for which the optimization data, such as target cost and target,UAV distances, are time varying and uncertain. The impact of this uncertainty in the data is mitigated by tightly integrating two approaches for improving the robustness of the assignment algorithm. One approach is to design task assignment plans that are robust to the uncertainty in the data, which reduces the sensitivity to errors in the situational awareness (SA), but can be overly conservative for long duration plans. A second approach is to replan as the SA is updated, which results in the best plan given the current information, but can lead to a churning type of instability if the updates are performed too rapidly. The strategy proposed in this paper combines robust planning with the techniques developed to eliminate churning. This combination results in the robust filter-embedded task assignment algorithm that uses both proactive techniques that hedge against the uncertainty, and reactive approaches that limit churning behavior by the vehicles. Numerous simulations are shown to demonstrate the performance benefits of this new algorithm. Copyright © 2007 John Wiley & Sons, Ltd. [source] A complete parameterization of clf-based input-to-state stabilizing control lawsINTERNATIONAL JOURNAL OF ROBUST AND NONLINEAR CONTROL, Issue 17 2004J. W. Curtis Abstract Sontag's formula proves constructively that the existence of a control Lyapunov function implies asymptotic stabilizability. A similar result can be obtained for systems subject to unknown disturbances via input-to-state stabilizing control Lyapunov functions (ISS-clfs) and the input-to-state analogue of Sontag's formula. The present paper provides a generalization of the ISS version of Sontag's formula by completely parameterizing all continuous ISS control laws that can be generated by a known ISS-clf. When a simple inner-product constraint is satisfied, this parameterization also conveniently describes a large family of ISS controls that solve the inverse-optimal gain assignment problem, and it is proved that these controls possess Kalman-type gain margins. Copyright © 2004 John Wiley & Sons, Ltd. [source] Annual planning of harvesting resources in the forest industryINTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, Issue 2 2010David Bredström Abstract A cost-efficient use of harvesting resources is important in the forest industry. The main planning is carried out in an annual resource plan that is continuously revised. The harvesting operations are divided into harvesting and forwarding. The harvesting operation fells trees and puts them in piles in the harvest areas. The forwarding operation collects piles and moves them to storage locations adjacent to forest roads. These operations are conducted by machines (harvesters, forwarders and harwarders), and these are operated by crews living in cities/villages that are within some maximum distance from the harvest areas. Machines, harvest teams and harvest areas have different characteristics and properties and it is difficult to find the best possible match throughout the year. The aim of the planning is to find an annual plan with the lowest possible cost. The total cost is based on three parts: production cost, traveling cost and moving cost. The production cost is the cost for the harvesting and forwarding. The traveling cost is the cost for driving back and forwards (daily) from the home base to the harvest area and the moving cost is associated with moving the machines and equipment between harvest areas. The Forest Research Institute of Sweden (Skogforsk), together with a number of Swedish forest companies, has developed a decision support platform for the planning. One important element of this platform is that it should find high-quality plans within short computational times. One central element is an optimization model that integrates the assignment of machines to harvest areas and schedules the harvest areas during the year for each machine. The problem is complex and we propose a two-phase solution method where, first, we solve the assignment problem and, second, the scheduling. In order to be able to control the scheduling in phase 1 as well, we have introduced an extra cost component that controls the geographical distribution of harvest areas for each machine in phase 1. We have tested the solution approach on a case study from one of the larger Swedish forest companies. This case study involves 46 machines and 968 harvest areas representing a log volume of 1.33 million cubic meters. We describe some numerical results and experience from the development and tests. [source] General stochastic user equilibrium traffic assignment problem with link capacity constraintsJOURNAL OF ADVANCED TRANSPORTATION, Issue 4 2008Qiang Meng Abstract This paper addresses a general stochastic user equilibrium (SUE) traffic assignment problem with link capacity constraints. It first proposes a novel linearly constrained minimization model in terms of path flows and then shows that any of its local minimums satisfies the generalized SUE conditions. As the objective function of the proposed model involves path-specific delay functions without explicit mathematical expressions, its Lagrangian dual formulation is analyzed. On the basis of the Lagrangian dual model, a convergent Lagrangian dual method with a predetermined step size sequence is developed. This solution method merely invokes a subroutine at each iteration to perform a conventional SUE traffic assignment excluding link capacity constraints. Finally, two numerical examples are used to illustrate the proposed model and solution method. [source] Architecting a System of Systems Responding to Maritime Domain Terrorism by Orthogonal Array ExperimentNAVAL ENGINEERS JOURNAL, Issue 1 2009THOMAS HUYNH In this work we solve the problem of architecting a conceptual, cost-effective, near-term system of systems (SoS) to respond to terrorist threats to the United States emanating from the maritime domain. The threats include a weapon of mass destruction smuggled on a container ship, a commandeered ship used as a weapon, and small boats used by terrorists to attack maritime commerce traffic and critical shore infrastructures. We formulate the problem as an assignment problem, which is then solved using the orthogonal array experiment. The optimality of the resulting SoS architecture is validated against a heuristically developed architecture and an optimal effective, but not necessarily cost-effective, architecture obtained also with the orthogonal array experiment approach. The principal results of the orthogonal array experiment method reported herein underline this successful exploratory work in architecting an SoS. This method can be extended to architecting of other systems of systems. [source] On labeling the vertices of products of complete graphs with distance constraintsNAVAL RESEARCH LOGISTICS: AN INTERNATIONAL JOURNAL, Issue 2 2005D.J. Erwin Variations of Hale's channel assignment problem, the L(j, k)-labeling problem and the radio labeling problem require the assignment of integers to the vertices of a graph G subject to various distance constraints. The ,j,k -number of G and the radio number of G are respectively the minimum span among all L(j, k)-labelings, and the minimum span plus 1 of all radio labelings of G (defined in the Introduction). In this paper, we establish the ,j,k -number of ,K for pairwise relatively prime integers t1 < t2 < , < tq, t1 , 2. We also show the existence of an infinite class of graphs G with radio number |V(G)| for any diameter d(G). © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2005 [source] The Hungarian method for the assignment problemNAVAL RESEARCH LOGISTICS: AN INTERNATIONAL JOURNAL, Issue 1 2005H. W. Kuhn This paper has been presented with the Best Paper Award. It will appear in print in Volume 52, No. 1, February 2005. [source] Analysis of a new vehicle scheduling and location problemNAVAL RESEARCH LOGISTICS: AN INTERNATIONAL JOURNAL, Issue 5 2001Ebru K. Bish We consider a container terminal discharging containers from a ship and locating them in the terminal yard. Each container has a number of potential locations in the yard where it can be stored. Containers are moved from the ship to the yard using a fleet of vehicles, each of which can carry one container at a time. The problem is to assign each container to a yard location and dispatch vehicles to the containers so as to minimize the time it takes to download all the containers from the ship. We show that the problem is NP-hard and develop a heuristic algorithm based on formulating the problem as an assignment problem. The effectiveness of the heuristic is analyzed from both worst-case and computational points of view. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 363,385, 2001 [source] An ejection chain algorithm for the quadratic assignment problemNETWORKS: AN INTERNATIONAL JOURNAL, Issue 3 2010Cesar Rego Abstract In this study, we present a new tabu search algorithm for the quadratic assignment problem (QAP) that utilizes an embedded neighborhood construction called an ejection chain. Our ejection chain approach provides a combinatorial leverage effect, where the size of the neighborhood grows multiplicatively while the effort of finding a best move in the neighborhood grows only additively. Our results illustrate that significant improvement in solution quality is obtained in comparison to the traditional swap neighborhood. We also develop two multistart tabu search algorithms utilizing the ejection chain approach in order to demonstrate the power of embedding this neighborhood construction within a more sophisticated heuristic framework. Comparisons to the best large neighborhood approaches from the literature are presented. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010 [source] New approaches for solving the block-to-train assignment problemNETWORKS: AN INTERNATIONAL JOURNAL, Issue 1 2008Krishna C. Jha Abstract Railroad planning involves solving two optimization problems: (i) the blocking problem, which determines what blocks to make and how to route traffic over these blocks; and (ii) the train schedule design problem, which determines train origins, destinations, and routes. Once the blocking plan and train schedule have been obtained, the next step is to determine which trains should carry which blocks. This problem, known as the block-to-train assignment problem, is considered in this paper. We provide two formulations for this problem: an arc-based formulation and a path-based formulation. The latter is generally smaller than the former, and it can better handle practical constraints. We also propose exact and heuristic algorithms based on the path-based formulation. Our exact algorithm solves an integer programming formulation with CPLEX using both a priori generation and dynamic generation of paths. Our heuristic algorithms include a Lagrangian relaxation-based method as well as a greedy construction method. We present computational results of our algorithms using the data provided by a major US railroad. We show that we can obtain an optimal solution of the block-to-train assignment problem within a few minutes of computational time, and can obtain heuristic solutions with 1,2% deviations from the optimal solutions within a few seconds. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008 [source] A column generation approach for SONET ring assignmentNETWORKS: AN INTERNATIONAL JOURNAL, Issue 3 2006Elder M. Macambira Abstract In this article we consider the SONET ring assignment problem (SRAP) presented in 7. The authors pointed out the inadequacy of solving SRAP instances using their integer programming formulation and commercial linear programming solvers. Similar experiences with IP models for SRAP are reported in 1. In this article we reformulate SRAP as a set partitioning model with an additional knapsack constraint. This new formulation has an exponential number of columns and, to solve it, we implemented a branch-and-price/column generation algorithm. Extensive computational experiments showed that the new algorithm is orders of magnitude faster than standard branch-and-bound codes running on compact IP models introduced earlier. Instances taken from 1, 7, which could not be solved there in hours of computation were solved here to optimality in just a few seconds. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 47(3), 157,171 2006 [source] Toward faster algorithms for dynamic traffic assignment.NETWORKS: AN INTERNATIONAL JOURNAL, Issue 1 2003Abstract Being first in a three-part series promising a practical solution to the user-equilibrium dynamic traffic assignment problem, this paper devises a parametric quickest-path tree algorithm, whose model makes three practical assumptions: (i) the traversal time of an arc i , j is a piecewise linear function of the arrival time at its i -node; (ii) the traversal time of a path is the sum of its arcs' traversal times; and (iii) the FIFO constraint holds, that is, later departure implies later arrival. The algorithm finds a quickest path, and its associated earliest arrival time, to every node for every desired departure time from the origin. Its parametric approach transforms a min-path tree for one departure-time interval into another for the next adjacent interval, whose shared boundary the algorithm determines on the fly. By building relatively few trees, it provides the topology explicitly and the arrival times implicitly of all min-path trees. Tests show the algorithm running upward of 10 times faster than the conventional brute-force approach, which explicitly builds a min-path tree for every departure time. Besides dynamic traffic assignment, other applications for which these findings have utility include traffic control planning, vehicle routing and scheduling, real-time highway route guidance, etc. © 2002 Wiley Periodicals, Inc. [source] Partial pole assignment for the quadratic pencil by output feedback control with feedback designsNUMERICAL LINEAR ALGEBRA WITH APPLICATIONS, Issue 10 2005Wen-Wei Lin Abstract In this paper we study the partial pole assignment problem for the quadratic pencil by output feedback control where the output matrix is also a designing parameter. In addition, the input matrix is set to be the transpose of the output matrix. Under certain assumption, we give a solution to this partial pole assignment problem in which the unwanted eigenvalues are moved to desired values and all other eigenpairs remain unchanged. Copyright © 2005 John Wiley & Sons, Ltd. [source] Weight of a link in a shortest path tree and the Dedekind Eta functionRANDOM STRUCTURES AND ALGORITHMS, Issue 3 2010Piet Van Mieghem Abstract The weight of a randomly chosen link in the shortest path tree on the complete graph with exponential i.i.d. link weights is studied. The corresponding exact probability generating function and the asymptotic law are derived. As a remarkable coincidence, this asymptotic law is precisely the same as the distribution of the cost of one "job" in the random assignment problem. We also show that the asymptotic (scaled) maximum interattachment time to that shortest path tree, which is a uniform recursive tree, equals the square of the Dedekind Eta function, a central function in modular forms, elliptic functions, and the theory of partitions. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010 [source] The ,(2) limit in the random assignment problemRANDOM STRUCTURES AND ALGORITHMS, Issue 4 2001David J. Aldous Abstract The random assignment (or bipartite matching) problem asks about An=min,,,c(i,,,(i)), where (c(i,,j)) is a n×n matrix with i.i.d. entries, say with exponential(1) distribution, and the minimum is over permutations ,. Mézard and Parisi (1987) used the replica method from statistical physics to argue nonrigorously that EAn,,(2)=,2/6. Aldous (1992) identified the limit in terms of a matching problem on a limit infinite tree. Here we construct the optimal matching on the infinite tree. This yields a rigorous proof of the ,(2) limit and of the conjectured limit distribution of edge-costs and their rank-orders in the optimal matching. It also yields the asymptotic essential uniqueness property: every almost-optimal matching coincides with the optimal matching except on a small proportion of edges. ©2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 381,418, 2001 [source] A Polymorphic Dynamic Network Loading ModelCOMPUTER-AIDED CIVIL AND INFRASTRUCTURE ENGINEERING, Issue 2 2008Nie Yu (Marco) The polymorphism, realized through a general node-link interface and proper discretization, offers several prominent advantages. First of all, PDNL allows road facilities in the same network to be represented by different traffic flow models based on the tradeoff of efficiency and realism and/or the characteristics of the targeted problem. Second, new macroscopic link/node models can be easily plugged into the framework and compared against existing ones. Third, PDNL decouples links and nodes in network loading, and thus opens the door to parallel computing. Finally, PDNL keeps track of individual vehicular quanta of arbitrary size, which makes it possible to replicate analytical loading results as closely as desired. PDNL, thus, offers an ideal platform for studying both analytical dynamic traffic assignment problems of different kinds and macroscopic traffic simulation. [source] Experimental studies of sequential selection and assignment with relative ranksJOURNAL OF BEHAVIORAL DECISION MAKING, Issue 3 2006J. Neil Bearden Abstract We study a class of sequential selection and assignment problems in which a decision maker (DM) must sequentially assign applicants to positions with the objective of minimizing expected cost. In modeling this class of problems, we assume that on each period the DM is only informed of the rank of the present applicant relative to the applicants that she previously observed and assigned. We first present the optimal decision policy that we subsequently use as a normative benchmark, and then report results from three experiments designed to study sequential assignment behavior. In comparing the aggregate results from all three experiments to the optimal decision policy, we identify a systematic bias, called the middleness bias, to over-assign applicants to intermediate positions. The results also reveal a strong bias for early applicants to be over-assigned to important positions. Copyright © 2006 John Wiley & Sons, Ltd. [source] On the hardness of range assignment problemsNETWORKS: AN INTERNATIONAL JOURNAL, Issue 4 2008Bernhard Fuchs Abstract We investigate the computational hardness of the connectivity, the strong connectivity, and the broadcast type of range assignment problems in ,2 and ,3. We present new reductions for the connectivity problem, which are easily adapted to suit the other two problems. All reductions are considerably simpler than the technically quite involved ones used in earlier works on these problems. Using our constructions, we can for the first time prove NP-hardness of these problems for all real distance-power gradients , > 0 (resp. , > 1 for broadcast) in 2D, and prove APX-hardness of all three problems in 3D for all , > 1. Our reductions yield improved lower bounds on the approximation ratios for all problems where APX-hardness was known before already. In particular, we derive the overall first APX-hardness proof for broadcast. This was an open problem posed in earlier work in this area, as was the question whether (strong) connectivity remains NP-hard for , = 1. In addition, we give the first hardness results for so-called well-spread instances. On the positive side, we prove that two natural greedy algorithms are 2-approximations for (strong) connectivity, and show that the factor 2 is tight in ,2 for , > 1. We also analyze the performance guarantee of the well-known MST-heuristic as a function of the input size. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008 [source] Solving partial constraint satisfaction problems with tree decompositionNETWORKS: AN INTERNATIONAL JOURNAL, Issue 3 2002Arie M. C. A. Koster Abstract In this paper, we describe a computational study to solve hard partial constraint satisfaction problems (PCSPs) to optimality. The PCSP is a general class of problems that contains a diversity of problems, such as generalized subgraph problems, MAX-SAT, Boolean quadratic programs, and assignment problems like coloring and frequency planning. We present a dynamic programming algorithm that solves PCSPs based on the structure (tree decomposition) of the underlying constraint graph. With the use of dominance and bounding techniques, we are able to solve small and medium-size instances of the problem to optimality and to obtain good lower bounds for large-size instances within reasonable time and memory limits. © 2002 Wiley Periodicals, Inc. [source] | ||||||||||||||||