Search

In this paper, a novel bi-level grouping optimization (BIGO) model is proposed for solving the storage location assignment problem with grouping constraint (SLAP-GC). A major challenge in this problem is the grouping constraint which restricts the number of groups each product can have and the locations of items in the same group. In SLAP-GC, the problem consists of two subproblems, one is how to group the items, and the other one is how to assign the groups to locations. It is an arduous task to solve the two subproblems simultaneously. To overcome this difficulty, we propose a BIGO. BIGO optimizes item grouping in the upper level, and uses the lower-level optimization to evaluate each item grouping. Sophisticated fitness evaluation and search operators are designed for both upper and lower level optimization so that the feasibility of solutions can be guaranteed, and the search can focus on promising areas in the search space. Based on the BIGO model, a multistart random search method and a tabu search algorithm are proposed. The experimental results on the real-world dataset validate the efficacy of the BIGO model and the advantage of the tabu search method over the random search method. © 2018 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

The quadratic assignment problem (QAP) is a combinatorial optimization problem that arises in many real-world applications, such as equipment allocation in industry. The QAP is NP-hard and, in practice, one of the hardest combinatorial optimization problems to solve to optimality. Exact solutions of QAP are typically obtained by the branch-and-bound method. This method, however, potentially requires a high computational effort, and the use of good lower bounds is essential to prune the search tree. Branch-and-bound algorithms that use the dual-ascent procedure based on the level-2 reformulation linearization technique (RLT2) belong to the state of the art on exactly solving QAP. In this work, we propose a parallel implementation of that branch-and-bound algorithm. Our approach uses the Auction Algorithm of Bertsekas and Castañon to solve the linear assignment problems of RLT2, which allows us to take advantage of the massive parallel environment of graphics processing units to speed up the lower bound computation and implement some memory optimization techniques to address large-size problems. We report experimental results that show significant execution time reductions compared to previous works and allow us to provide, for the first time, exact solutions for two instances of QAP: tai35b and tai40b.

We study the q -adic assignment problem. We first give an O ( n (q−1)/2) )-approximation algorithm for the Koopmans--Beckman version of the problem, improving upon the result of Barvinok. Then, we introduce a new family of instances satisfying “tensor triangle inequalities” and give a constant factor approximation algorithm for them. We show that many classical optimization problems can be modeled by q -adic assignment problems from this family. Finally, we give several integrality gap examples for the natural LP relaxations of the problem.

A new repeated iterated tabu search for the quadratic assignment problem is developed. A comparative study of this algorithm and the best existing algorithms for solving this problem has shown its competitiveness with respect to both its performance and quality of solutions.

The generalized quadratic assignment problem (GQAP) is the task of assigning a set of facilities to a set of locations such that the sum of the assignment and transportation costs is minimized. The facilities may have different space requirements, and the locations may have varying space capacities. Also, multiple facilities may be assigned to each location such that space capacity is not exceeded. In this paper, an application of the GQAP is presented for assigning a set of machines to a set of locations on the plant floor. Construction algorithms and a simple tabu search heuristic are developed for the GQAP. A set of test problems available in the literature was used to evaluate the performances of the TS heuristic using different construction algorithms. The results show that the simple TS heuristic is effective for solving the GQAP.

In this paper we propose a new lower bounding procedure for the Quadratic Assignment Problem based on a generalization of the well-known Gilomore-Lawler procedure for a higher order reformulation. Computational results on some benchmark instances show the strength of the new approach compared with other lower bounds.

We consider a relaxation of the quadratic assignment problem without the constraint on the number of objects assigned to a specific position. This problem is NP-hard in the general case. To solve the problem, we propose a polynomial algorithm with guaranteed posterior accuracy estimate; we distinguish a class of problems with special assignment cost functions where the algorithm is 2-approximate. We show that if the graph in question contains one simple loop, and the set of assignment positions is a metric space, the proposed algorithm is 2-approximate and guaranteed to be asymptotically exact. We conduct a computational experiment in order to analyze the algorithm's errors and evaluate its accuracy.

In this paper we introduce a new approach to solve fuzzy assignment problem namely, ones assignment method. Considering each fuzzy cost as a triangular fuzzy numbers the fuzzy assignment problem has been transformed into crisp values by using linguistic variables and ranking techniques and then it is solved by ones assignment method. The proposed method is a systematic procedure, easy to apply and can be utilized for all types of assignment problem with maximize or minimize objective functions. At the end, this method is illustrated with some numerical example

The doubly constrained entropy distribution/assignment (DEDA) problem that combines a gravity-based trip distribution (TD) problem and a traffic assignment (TA) problem has long been formulated as an optimization model and solved by two solution algorithms, i.e., partial- and full-linearization solution algorithms. As an alternative, this research first treats the DEDA problem by the augmented Lagrangian dual (ALD) method as the singly constrained entropy distribution/assignment (SEDA) problem, which in turn is addressed, via a tactical supernetwork representation, as an “extended” 1-origin-to-1-destination TA problem. A quick-precision TA solution algorithm, − called TAPAS (Traffic Assignment by Paired Alternative Segments), − is then adopted for solutions. The proposed approach is demonstrated with a numerical example for the correctness of the result, using Lingo 11 solver and the partial linearization solution (PLS) algorithm. Moreover, through the use of TAPAS in the innermost loop, the proposed approach also has the merit of generating unique path flow solution, which is very useful in route guidance under the intelligent transportation systems environment, among other academic applications. In addition, the proposed approach can be easily applied, or with minor modification at most, to various combined models in travel demand forecasting.

In this paper Branch and bound technique is applied to assignment problem with fuzzy cost with objective to minimise cost, fuzzy cost is assumed as triangular fuzzy number, Yager’s ranking method has been used for ranking the fuzzy numbers, after transforming assignment problem into a crisp one using linguistic variables, assignment problem is solved by branch and bound technique. To deal with fuzzy assignment problem with qualitative data, linguistic variable helps to convert qualitative data into quantitative data.

Generally, the optimal solution of assignment problem can be obtained by Hungarian algorithm of two-sided optimization with time complexity . This paper suggests one-sided optimal assignment and swap optimization algorithm with time complexity can be achieve the goal of two-sided optimization. This algorithm selects the minimum cost for each row, and reassigns over-assigned to under-assigned cell. Next, that verifies the existence of swap optimization candidates, and swap optimizes with . For 27 experimental data, the swap-optimization performs only 22% of data, and 78% of data can be get the two-sided optimal result through one-sided optimal result. Also, that can be improves on the solution of best known solution for partial problems.

We consider the bilevel assignment problem in which each decision maker (i.e., the leader and the follower) has its own objective function and controls a distinct set of edges in a given bipartite graph. The leader acts first by choosing some of its edges. Subsequently, the follower completes the assignment process. The edges selected by the leader and the follower are required to constitute a perfect matching. In this paper we propose an exact solution approach, which is based on a branch-and-bound framework and exploits structural properties of the assignment problem. Extensive computational experiments with linear sum and linear bottleneck objective functions are conducted to demonstrate the performance of the developed methods. While the considered problem is known to be NP-hard in general, we also describe some restricted cases that can be solved in polynomial time.

The paper proposes a new method to solve the assignment problem based on recursive derivation of the optimal solution. The assignment problem is formulated in the rearrangement matrix form that allows the use of the matrix approach to optimal solution. The algorithm is to find the minimum total weight matching in the bipartite graph with 2n vertices. The computational scheme of the recurrence method for solving the assignment problem is presented in the form adapted for implementation on a computer.

Teaching–Learning-Based Optimization (TLBO) is a novel swarm intelligence metaheuristic that is reported as an efficient solution method for many optimization problems. It consists of two phases where all individuals are trained by a teacher in the first phase and interact with classmates to improve their knowledge level in the second phase. In this study, we propose a set of TLBO-based hybrid algorithms to solve the challenging combinatorial optimization problem, Quadratic Assignment. Individuals are trained with recombination operators and later a Robust Tabu Search engine processes them. The performances of sequential and parallel TLBO-based hybrid algorithms are compared with those of state-of-the-art metaheuristics in terms of the best solution and computational effort. It is shown experimentally that the performance of the proposed algorithms are competitive with the best reported algorithms for the solution of the Quadratic Assignment Problem with which many real life problems can be modeled.

We propose an exact algorithm to find the optimal solution to the grey pattern problem which is a special instance of the quadratic assignment problem. A very effective branch and bound algorithm is constructed. The special structure of the problem is exploited and optimal solutions for many problem instances established. One instance based on 64 facilities, organized in an 8 by 8 pattern, that was extensively researched in the literature was optimally solved in 15 s of computer time while existing papers report solution times of hours.

Display Omitted A major optimization problem in synthesis of sequential circuits is State Assignment (SA).Cuckoo search optimization (CSO) algorithm is employed for solving the SA problem.CSO targets area minimization of synthesized sequential circuits.CSO results outperform deterministic and non-deterministic heuristic optimization methods. A major optimization problem in the synthesis of sequential circuits is State Assignment or State Encoding in Finite State Machines (FSMs). The state assignment of an FSM determines the complexity of its combinational circuit and thus area, delay, testability and power dissipation. Since optimal state assignment is an NP-hard problem and existing deterministic algorithms produce solutions far from best known solutions, we resort to the use of non-deterministic iterative optimization heuristics. This paper proposes the use of cuckoo search optimization (CSO) algorithm for solving the state assignment problem (SAP) of FSMs with the aim of minimizing area of the resulting sequential circuit. Results obtained from the CSO algorithm are compared with those obtained from binary particle swarm optimization (BPSO) algorithm, genetic algorithm (GA), and the well-known deterministic methods of NOVA and JEDI. The results indicate that CSO outperforms deterministic methods as well as other non-deterministic heuristic optimization methods.

The cooperative multi-targets assignment for multiple unmanned aerial vehicles (UAV) is a complex combinatorial optimization problem. Multi-UAVs cooperation increases the scale of problems which cause a noticeable increase in task planning time. Moreover, it is difficult to build a unified assignment model because different tasks often require different numbers of UAVs and targets. Besides, the cooperative constraints of multi-UAVs in a three-dimensional environments are more complex than that in a two-dimensional environments, which makes it difficult to obtain an optimal solution. To solve these problems, we present a unified gene coding strategy to handle various models in a consistent framework. Then, a cooperative target assignment algorithm in a three-dimensional environments based on discrete mapping differential evolution is given. First, we use flight path cost to indicate the assignment relationship between the UAV and the target, which turns the optimization problem from discrete space to continuous space, and so the solving process can be simplified. Secondly, in order to obtain reasonable offspring for differential evolution, we map the solution back to the assignment relationship space according to inverse mapping rules. Finally, to avoid falling into a local optimal, a balance between exploration and exploitation is achieved by combining the dynamic crossover rate with the hybrid evolution strategy. The simulation results show that the proposed discrete mapping differential evolution algorithm with the unified gene coding strategy not only effectively solves the cooperative multi-targets assignment problem, but also improves the accuracy of the multi-targets assignment. It is also suitable for solving the large scale problem of assignment.

Analysing the characters of the elements of the efficiency matrix of the assignment problem, we find some properties of the optimal solution. Different from the traditional algorithm, Hungarian method, we give several principles to recognize some optimal points rapidly, thus we can reduce the dimension of the assignment problem.

We address the solution of a very challenging (and previously unsolved) instance of the quadratic 3-dimensional assignment problem, arising in digital wireless communications. The paper describes the techniques developed to solve this instance to optimality, from the choice of an appropriate mixed-integer programming formulation, to cutting planes and symmetry handling. Using these techniques we were able to solve the target instance with moderate computational effort (2.5 million nodes and 1 week of computations on a standard PC).

In this study, we consider a bicriteria multiresource generalized assignment problem. Our criteria are the total assignment load and maximum assignment load over all agents. We aim to generate all nondominated objective vectors and the corresponding efficient solutions. We propose several lower and upper bounds and use them in our optimization and heuristic algorithms. The computational results have shown the satisfactory behaviors of our approaches. © 2014 Wiley Periodicals, Inc. Naval Research Logistics, 61: 621–636, 2014

The assignment problem (AP) is to optimally solve the task of assigning n jobs to n individuals, such that minimum cost or maximum profit can be obtained. It is a vitally important NP-complete problem in operation management and applied mathematics, having a wide range of applications. In this paper, we present a new parallel DNA algorithm to solve the assignment problem using DNA molecular operations. Meanwhile, we design flexible length DNA strands to represent different jobs and individuals, take appropriate steps and get the solutions of the AP in proper length range and with O ( n 2 ) time complexity. We extend the application of DNA molecular operations and simultaneity reduce the complexity of the computation.

The weapon target assignment (WTA) problem is a fundamental problem arising in defense-related applications of operations research. The multi-stage weapon target assignment (MWTA) problem is the basis of the dynamic weapon target assignment (DWTA) problem which commonly exists in practice. The MWTA problem considered in this paper is formulated as a multi-objective constrained combinatorial optimization problem with two competing objectives. Apart from maximizing the damage to hostile targets, this paper follows the principle of minimizing the ammunition consumption. Decomposition and Pareto dominance both are efficient and prevailing strategies for solving multi-objective optimization problems. Three competitive multi-objective optimizers: DMOEA-eC, NSGA-II, and MOEA/D-AWA are adopted to solve multi-objective MWTA problems efficiently. Then comparison studies among DMOEA-eC, NSGA-II, and MOEA/D-AWA on solving three different-scale MWTA instances are done. Three common used performance metrics are used to evaluate the performance of each algorithm. Numerical results demonstrate that NSGA-II performs best on small-scale and medium-scale instances compared with DMOEA-eC and MOEA/D-AWA, while DMOEA-eC shows advantages over the other two algorithms on solving the large-scale instance.

The traditional assignment problem assumes that the number of persons is equal to that of the tasks, beyond that, one person is allowed to undertake only one task and one task must be accomplished by one person. However, in practical situation, a real task usually calls for more than one person, in some cases, those persons are required to work at the same time. If so, the classical assignment model will not be able to describe the problem accurately. In view of this situation, a new generalized assignment model based on nonlinear integer programming is presented in this paper. The new model gives a unified description of the generalized assignment problems in which one or more persons are required to work at the same time to complete a single task. As a result, it makes up for the deficiency of the existing generalized assignment model. Moreover, for the case of binary quadratic programming, a new branch and bound method is also proposed. The numerical results indicate that the generalized assignment model and method proposed are valid.

Article history: Received March 2 2014 Accepted 29 July 2014 Available online July 31 2014 This paper presents a multi-objective assignment problem (MAP) with interval parameters. Here, the model concentrates on three criteria: total cost, total profit and total operation time of assignment. The proposed model is classified as a nonlinear programming, in which it is difficult to solve. Hence, the model is converted into crisp linear programming problem by applying a substitution variables approach. In addition, a weighted min-max method is applied to transform the multi-objective problem into a single objective optimization problem. Finally, several numerical examples are provided to illustrate the implementation of the proposed approach. The results clearly provide some evidences that the proposed approach was easier to contrast compared with other approaches. The results also indicate that decision makers’ preferences over various objectives could influence on solutions. © 2014 Growing Science Ltd. All rights reserved.

We consider a variant of the multidimensional assignment problem (MAP) with decomposable costs in which the resulting optimal assignment is described as a set of disjoint stars. This problem arises in the context of multi-sensor multi-target tracking problems, where a set of measurements, obtained from a collection of sensors, must be associated to a set of different targets. To solve this problem we study two different formulations. First, we introduce a continuous nonlinear program and its linearization, along with additional valid inequalities that improve the lower bounds. Second, we state the standard MAP formulation as a set partitioning problem, and solve it via branch and price. These approaches were put to test by solving instances ranging from tripartite to 20-partite graphs of 4 to 30 nodes per partition. Computational results show that our approaches are a viable option to solve this problem. A comparative study is presented.

A class of polynomially solvable problems of combinatorial optimization is illustrated by the example of the traveling salesman problem. It is proved that this class includes problems for which the structure of initial data is specially modeled.

In this paper, a novel discrete differential evolution (DDE) algorithm is proposed to solve the multiobjective generalized assignment problem (mGAP), which is basically concerned with finding the optimal assignment of jobs to agents such that each job is assigned to exactly one agent, subject to capacity constraint of agents, and aims to optimize multiple objective functions simultaneously, such as minimizing cost, minimizing time, and maximizing profit. First, the mGAP is described and a standard multi-objective mathematical programming model for mGAP is given. Second, the DDE is presented, in which individuals are represented as the integer encoding scheme, and a novel integer-encoding-based dynamic mutation operator is employed to generate new candidate solutions. Furthermore, a sequential selection operator for dealing with multiple objectives is embedded in the proposed DDE. Finally, an extensive computational study is carried out by comparison with the enumeration algorithm and genetic algorithm, the results show that the proposed DDE is an effective algorithm for mGAP.

In this paper, we study a multi-objective multi-choice assignment problem considering cost and time objectives subject to some realistic constraints including multi-job assignment. We assume that the decision-maker provides multiple aspiration levels regarding both cost and time objectives using discrete choices as well as interval values. To obtain efficient allocation plans, we use multi-choice goal programming methodology to solve the assignment problem. The proposed methodology is illustrated through numerical examples.

In this paper, we consider sensor-mission assignment in wireless sensor networks. We consider some approaches to solve the problem of sensor-mission assignment. In particular, we consider integer programs and logical models for the problem.

In this paper, we consider the quadratic assignment problem (QAP), one of the hardest NP-hard combinatorial optimization problems. We first present a new reformulation of the problem. Then a Lexisearch Algorithm (LSA) is developed for obtaining exact optimal solution to the problem. Finally, a comparative study has been carried out to show the efficiency of the algorithm against an existing algorithm for some medium sized instances from the quadratic assignment problem library, QAPLIB. The comparative study shows the efficiency of the proposed LSA based on the reformulation.

We prove that, for two simple functions d r l t , solving the online assignment problem with c r l − d r l t as the contribution for assigning resource r to task l at time t gives the optimal solution to the corresponding offline assignment problem (provided the optimal offline solution is unique). We call such functions d r l t optimal discount functions.

The bottleneck assignment (BA) and the generalized assignment (GA) problems and their exact solutions are explored in this paper. Firstly, a determinant elimination (DE) method is proposed based on the discussion of the time and space complexity of the enumeration method for both BA and GA problems. The optimization algorithm to the pre-assignment problem is then discussed and the adjusting and transformation to the cost matrix is adopted to reduce the computational complexity of the DE method. Finally, a synthesis method for both BA and GA problems is presented. The numerical experiments are carried out and the results indicate that the proposed method is feasible and of high efficiency.

In daily life, it often comes to such a problem that a department need to complete assignments , and there are people who are committed to achieving the tasks. In view of each person has different abilities and tasks, so the efficiency is different either .In order to gain the maximum efficiency or the minimum tine-consuming of accomplishing tasks ,there arise a question that is how to effectively assign these resources. The paper uses the Vogel method of transportation problem to solve the non-standard assignment problem. In practice, it’s more convenient and effectively to solve the assignment problem with the Vogel method than the Hungarian method.

International audience; Several real-life applications can be stated in terms of the Quadratic Assignment Problem. Finding an optimal assignment is com-putationally very difficult, for many useful instances. We address this problem using a local search technique, based on Extremal Optimization and present experimental evidence that this approach is competitive. Moreover, cooperative parallel versions of our solver improve performance so much that large and hard instances can be solved quickly.

In this paper, we extend the classical assignment problem to the multicriteria assignment problem by considering three criteria: cost, time and quality subject to many realistic constraints including multi-job assignment and a knapsack-type resource constraint. The paper addresses the uncertainty of the real-life assignment problem by formulating a fuzzy cost–time–quality assignment problem using exponential membership functions. We define fuzzy goal for each criterion as per the preferences of the decision-maker and aggregate the fuzzy goals using product operator. In order to obtain optimal assignment plans, the resultant nonlinear 0-1 optimization problem is solved using genetic algorithm for different choices of the shape parameters in the exponential membership functions. As an illustrative example, we consider a fuzzy manpower planning problem.

The vector assignment p-median problem (VAPMP) and the ordered p-median problem (OMP) are important extensions of the classic p-median problem. The VAPMP extends the p-median problem by allowing assignment of a demand to multiple facilities, and a wide variety of multi-assignment and backup location problems are special cases of this problem. The OMP optimizes a weighted sum of service distances according to their relative ranks among all demands. The OMP is well known as it represents a generalization of both the p-median and the p-center problems. In this article, a new model is developed which extends both the VAPMP and OMP problems. In addition, beyond median, center, and vector assignment, this new model can resolve problems where the system objective involves maximizing distance. The new model also gives rise to meaningful special-case problems, such as a “reliable p-center” problem. Different integer linear programming (ILP) formulations of the new problem are presented and tested. It is demonstrated that an efficient formulation for a special case of the VAOMP problem can solve medium sized problems optimally in a reasonable amount of time.

The quadratic assignment problem (QAP) is a challenging combinatorial problem. The problem is NP-hard and in addition, it is considered practically intractable to solve large QAP instances, to proven optimality, within reasonable time limits. In this paper we present an attractive mixed integer linear programming (MILP) formulation of the QAP. We first introduce a useful non-linear formulation of the problem and then a method of how to reformulate it to a new exact, compact discrete linear model. This reformulation is efficient for QAP instances with few unique elements in the flow or distance matrices. Finally, we present optimal results, obtained with the discrete linear reformulation, for some previously unsolved instances (with the size n = 32 and 64), from the quadratic assignment problem library, QAPLIB.

Discovering the conditions under which an optimization algorithm or search heuristic will succeed or fail is critical for understanding the strengths and weaknesses of different algorithms, and for automated algorithm selection. Large scale experimental studies - studying the performance of a variety of optimization algorithms across a large collection of diverse problem instances - provide the resources to derive these conditions. Data mining techniques can be used to learn the relationships between the critical features of the instances and the performance of algorithms. This paper discusses how we can adequately characterize the features of a problem instance that have impact on difficulty in terms of algorithmic performance, and how such features can be defined and measured for various optimization problems. We provide a comprehensive survey of the research field with a focus on six combinatorial optimization problems: assignment, traveling salesman, and knapsack problems, bin-packing, graph coloring, and timetabling. For these problems - which are important abstractions of many real-world problems - we review hardness-revealing features as developed over decades of research, and we discuss the suitability of more problem-independent landscape metrics. We discuss how the features developed for one problem may be transferred to study related problems exhibiting similar structures.

This paper introduces a new variable depth search method for the Quadratic Assignment Problem. The new method considers the cost of edges assignment as the criterion to decide which vertices to exchange during local search moves. It also presents the results of an extensive experimental study that compares the performance of local search and variable depth search algorithms for the Quadratic Assignment Problem. The investigation presented here contributes to a better understanding of the potential of these techniques, which are widely used as intensification tools in more sophisticated heuristic methods, such as evolutionary algorithms. Different algorithms presented in the literature were implemented and compared to the proposed methods. The results of a computational experiment with 161 benchmark instances are reported. Different statistical tests are applied in order to analyze the results provided by the experiments.

This research deals with the path-based system optimal dynamic traffic assignment (SODTA) problem with uncertain demands that are assumed to be bounded by a prescribed uncertainty set. A robust optimization approach is adopted to address this problem. The objective is to minimize the total network travel time under the worst-case scenario defined by a pre-determined demand uncertainty set. We formulate the robust counterpart optimization problem of SODTA for a general uncertainty set and show that solving the robust SODTA problem is not more difficult than solving the deterministic SODTA problem for some specific types of uncertainty set. Moreover, a column generation-based algorithmic framework that embeds a scaled gradient projection algorithm is proposed to solve the SODTA problem. Numerical experiments were conducted to demonstrate the effectiveness of the algorithm and to examine the impact of different types of demand uncertainty set on solution quality.

The well-known generalized assignment problem (GAP) is to minimize the costs of assigning n jobs to m capacity constrained agents (or machines) such that each job is assigned to exactly one agent. This problem is known to be NP-hard and it is hard from a computational point of view as well. In this paper, follows from practical point of view in real systems, the GAP is extended to the equilibrium generalized assignment problem (EGAP) and the equilibrium constrained generalized assignment problem (ECGAP). A heuristic equilibrium strategy based genetic algorithm (GA) is designed for solving the proposed EGAP. Finally, to verify the computational efficiency of the designed GA, some numerical experiments are performed on some known benchmarks. The test results show that the designed GA is very valid for solving EGAP.

Evaluation of system reliability in stochastic flow networks under time constraints depends on the transmission time of minimal paths. The lead-time of a minimal path plays an important role in calculating the transmission time. Component assignments not only affect on the lead-time of a path but also the reliability value. Components assignment problem subject to total lead-time is never discussed. Thus, this paper focuses on solving this problem under total-lead time constraint, in which each component has an assignment lead-time. Subsequently an optimization method based on genetic algorithm is proposed to search the optimal components for a minimum total lead-time that maximizes the system reliability. The mathematical programming formulation for the assignment problem with optimal network reliability subject to total lead-time is formulated and solved by the presented genetic algorithm. The presented algorithm is applied on two given examples with different number of available components to assert its efficiency in solving the given assignment problem.

The generalized quadratic assignment problem (GQAP) concerns with assigning m facilities to n locations. Multiple facilities can be assigned to a single location as long as the space allows. The aim is to find a way of assignment such that the total cost involved is minimized while respecting the space constraints. The total cost composes of installation and transportation costs, which is obtained by multiplying the facility flows and distances. GQAP is the generalization of the well-known quadratic assignment problem, which requires the number of facilities and locations to be the same and exactly one facility is assigned to one location. This paper presents a hybrid metaheuristic for solving the GQAP. The proposed algorithm hybridizes biogeography-based optimization with tabu search. Experimental results show that the hybrid metaheuristic is able to solve problem instances obtained from a manufacturing company, within reasonable computational times.

A new method for solving the assignment problem based on the decomposition of the original problem into a number of two-dimensional optimization problems is proposed. The integer-valuedness and monotonicity of the iterative procedure with respect to the objective function ensures that the algorithm is finite. As a result, either a unique optimal solution of the original assignment problem or a system of constraints is obtained. In the latter case, the system of constraints can be used to obtain all optimal solutions. Examples illustrating the algorithm are discussed.

The classical greedy algorithm for discrete optimization problems where the optimal solution is a maximal independent subset of a finite ground set of weighted elements, can be defined in two ways which are dual to each other. The Greedy-In where a solution is constructed from the empty set by adding the next best element, one at a time, until we reach infeasibility, and the Greedy-Out where starting from the ground set we delete the next worst element, one at a time, until feasibility is reached. It is known that while the former provides an approximation ratio for maximization problems, its worst case performance is not bounded for minimization problems, and vice-versa for the later. However the Greedy-Out algorithm requires an oracle for checking the existence of a maximal independent subset which for most discrete optimization problems is a difficult task. In this work we present a Greedy-Out algorithm for the quadratic assignment problem by providing a combinatorial characterization of its solutions.

We investigate a special case of the maximum quadratic assignment problem where one matrix is a product matrix and the other matrix is the distance matrix of a one-dimensional point set. We show that this special case, which we call the Wiener maximum quadratic assignment problem, is NP-hard in the ordinary sense and solvable in pseudo-polynomial time. Our approach also yields a polynomial time solution for the following problem from chemical graph theory: Find a tree that maximizes the Wiener index among all trees with a prescribed degree sequence. This settles an open problem from the literature., 11 pages, no figures

The typical assignment problem for finding the optimal assignment of a set of components to a set of locations in a system has been widely studied in practical applications. However, this problem mainly focuses on maximizing the total profit or minimizing the total cost without considering component’s failure. In practice, each component should be multistate due to failure, partially failure, or maintenance. That is, each component has several capacities with a probability distribution and may fail. When a set of multistate components is assigned to a system, the system can be treated as a stochastic-flow network. The network reliability is the probability that d units of homogenous commodity can be transmitted through the network successfully. The multistate components assignment problem to maximize the network reliability is never discussed. Therefore, this paper focuses on solving this problem under an assignment budget constraint, in which each component has an assignment cost. The network reliability under a components assignment can be evaluated in terms of minimal paths and state-space decomposition. Subsequently an optimization method based on genetic algorithm is proposed. The experimental results show that the proposed algorithm can be executed in a reasonable time.

This paper proposes an enhanced Multi-objective Go with the Winners (MOGWW) algorithm to solve multi-objective combinatorial optimization problems. The original MOGWW algorithm is equipped with the well known Pareto Local Search (PLS) procedure. In order to assess the performance of the hybridization, the non-dominated solutions it generates are compared with the ones generated by each of its components. The algorithms are applied to benchmark instances of the bi-objective Quadratic Assignment Problem. Experimental results show that the hybridized version outperforms both its components, i.e. the original MOGWW algorithm and a PLS variant.

Terminal assignment problem (TEAP) is to determine minimum cost links to form a network by connecting a given set of terminals to a given collection of concentrators. This paper presents a novel discrete particle swarm optimization (PSO) based on estimation of distribution (EDA), named DPSO-EDA, for TEAP. EDAs sample new solutions from a probability model which characterizes the distribution of promising solutions in the search space at each generation. The DPSO-EDA incorporates the global statistical information collected from personal best solutions of all particles into the PSO, and therefore each particle has comprehensive learning and search ability. In the DPSO-EDA, a modified constraint handling method based on Hopfield neural network (HNN) is also introduced to fit nicely into the framework of the PSO and thus utilize the merit of the PSO. The DPSO-EDA adopts the asynchronous updating scheme. Further, the DPSO-EDA is applied to a problem directly related to TEAP, the task assignment problem (TAAP), in order to show that the DPSO-EDA can be generalized to other related combinatorial optimization problems. Simulation results on several problem instances show that the DPSO-EDA is better than previous methods.

One of the most important variants of the standard linear assignment problem is the bottleneck assignment problem. In this paper we give a method by which one can find all of the asymptotic moments of a random bottleneck assignment problem in which costs (independent and identically distributed) are chosen from a wide variety of continuous distributions. Our method is obtained by determining the asymptotic moments of the time to first complete matching in a random bipartite graph process and then transforming those, via a Maclaurin series expansion for the inverse cumulative distribution function, into the desired moments for the bottleneck assignment problem. Our results improve on the previous best-known expression for the expected value of a random bottleneck assignment problem, yield the first results on moments other than the expected value, and produce the first results on the moments for the time to first complete matching in a random bipartite graph process.