An algorithm for algebraic assignment problems

An O(n³) algorithm is described for solving algebraic assigment problems.     

An integrated fuzzy simulation-fuzzy data envelopment analysis algorithm for job-shop layout optimization: The case of injection process with ambiguous data

This paper puts forward an integrated fuzzy simulation-fuzzy data envelopment analysis (FSFDEA) algorithm to cope with a special case of single-row facility layout problem (SRFLP). Discrete-event-simulation, a powerful tool for analyzing complex and stochastic systems, is employed for modeling different layout formations. Afterwards, a range-adjusted measure (RAM) is used as a data envelopment analysis (DEA) model for ranking the simulation results and finding the optimal layout design. Due to ambiguousness associated with the processing times, fuzzy sets theory is incorporated into the simulation model. Since the results of simulation are in the form of possibility distributions, the DEA model is treated on a fuzzy basis; therefore, a recent possibilistic programming approach is used to convert the fuzzy DEA model to an equivalent crisp one. The proposed FSFDEA algorithm is capable of modeling and optimizing small-sized SRFLP’s in stochastic, uncertain, and non-linear environments. The solution quality is inspected through a real case study in a refrigerator manufacturing company.     

An approximation algorithm for the generalized assignment problem

The generalized assignment problem can be viewed as the following problem of scheduling parallel machines with costs. Each job is to be processed by exactly one machine; processing jobj on machinei requires timep _ij and incurs a cost ofc _ij ; each machinei is available forT _i time units, and the objective is to minimize the total cost incurred. Our main result is as follows. There is a polynomial-time algorithm that, given a valueC, either proves that no feasible schedule of costC exists, or else finds a schedule of cost at mostC where each machinei is used for at most 2T _i time units.We also extend this result to a variant of the problem where, instead of a fixed processing timep _ij , there is a range of possible processing times for each machine—job pair, and the cost linearly increases as the processing time decreases. We show that these results imply a polynomial-time 2-approximation algorithm to minimize a weighted sum of the cost and the makespan, i.e., the maximum job completion time. We also consider the objective of minimizing the mean job completion time. We show that there is a polynomial-time algorithm that, given valuesM andT, either proves that no schedule of mean job completion timeM and makespanT exists, or else finds a schedule of mean job completion time at mostM and makespan at most 2T. Research partially supported by an NSF PYI award CCR-89-96272 with matching support from UPS, and Sun Microsystems, and by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550.Research supported in part by a Packard Fellowship, a Sloan Fellowship, an NSF PYI award, and by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550.     

An analysis of the stable marriage assignment algorithm

An algorithm for assigning the members of two disjoint equal sets to each other under the criterion of Stable Marriage is analysed and the results compared to the experimental results obtained on a computer. The number of comparisons is shown to be of ordern logn (wheren is the size of the sets) which is better than that achieved by algorithms for solving the Classical Assignment Problem.     

An algebraic multigrid-based algorithm for circuit clustering

Digital circuits have grown exponentially in their sizes over the past decades. To be able to automate the design of these circuits, efficient algorithms are needed. One of the challenging stages of circuit design is the physical design where the physical locations of the components of a circuit are determined. Coarsening or clustering algorithms have become popular with physical designers due to their ability to reduce circuit sizes in the intermediate design steps such that the design can be performed faster and with higher quality. In this paper, a new clustering algorithm based on the algebraic multigrid (AMG) technique is presented. In the proposed algorithm, AMG is used to assign weights to connections between cells of a circuit and find cells that are best suited to become the initial cells for clusters, seed cells. The seed cells and the weights between them and the other cells are then used to cluster the cells of a circuit. The analysis of the proposed algorithm proves linear-time complexity, O(N), where N is the number of pins in a circuit. The numerical experiments demonstrate that AMG-based clustering can achieve high quality clusters and improve circuit placement designs with low computational cost.     

An algorithm for the generalized quadratic assignment problem

This paper reports on a new algorithm for the Generalized Quadratic Assignment problem (GQAP). The GQAP describes a broad class of quadratic integer programming problems, wherein M pair-wise related entities are assigned to N destinations constrained by the destinations’ ability to accommodate them. This new algorithm is based on a Reformulation Linearization Technique (RLT) dual ascent procedure. Experimental results show that the runtime of this algorithm is as good or better than other known exact solution methods for problems as large as M=20 and N=15. Current address of P.M. Hahn: 2127 Tryon Street, Philadelphia, PA 19146-1228, USA.     

An efficient genetic algorithm for single row facility layout

The single row facility layout is the NP-Hard problem of arranging facilities with given lengths on a line, so as to minimize the weighted sum of the distances between all pairs of facilities. Owing to its computational complexity, researchers have developed several heuristics to obtain good quality solutions. In this paper, we present a genetic algorithm called GENALGO to solve large single row facility layout problem instances. Our algorithm uses standard genetic operators and periodically improves the fitness of all individuals. Our computational experiments show that our genetic algorithm yields high quality solutions in spite of starting with an initial population that is randomly generated. Our algorithm improves the previously best known solutions for the 19 instances of 58 benchmark instances and is competitive for most of the remaining ones.     

PORA: A Physarum-inspired obstacle-avoiding routing algorithm for integrated circuit design

The plasmodium of Physarum polycephalum, a large, amoeboid cell, has attracted much attention recently due to its intelligent behaviors in pathfinding, danger avoidance, and network construction. Inspired by the biological behaviors of this primitive organism, in this study, we explore the optimization capability of Physarum polycephalum systematically and present the first Physarum-inspired obstacle-avoiding routing algorithm for the physical design of integrated circuits. We simulate the foraging behaviors of Physarum polycephalum using a novel nutrition absorption/consumption mathematical model, thereby presenting an efficient routing tool called Physarum router. With the proposed routing approach, for a given set of pin vertices and a given set of on-chip functional modules, a rectilinear Steiner minimal tree connecting all the pin vertices while avoiding the blockage of functional modules can be constructed automatically. Furthermore, several heuristics including a divide-and-conquer strategy, a non-pin leaf node pruning strategy, a dynamic parameter strategy, etc., are integrated into the proposed algorithm to fundamentally improve the performance of the Physarum router. Simulation results on multiple benchmarks confirm that the proposed algorithm leads to shorter wirelength compared with several state-of-the-art methods.     

An algorithm of global optimization for solving layout problems

The two-dimensional layout problem is known to be NP-complete, and the current research work is basically in the heuristic way. In this paper, we mainly discuss the methods for solving layout problem about the artificial satellite module by virtue of graph theory and group theory. Also, an algorithm of global optimization is presented first time. The method given here can be extended to solve other type of layout problems.     

A branch-and-price algorithm to solve the integrated berth allocation and yard assignment problem in bulk ports

In this research, two crucial optimization problems of berth allocation and yard assignment in the context of bulk ports are studied. We discuss how these problems are interrelated and can be combined and solved as a single large scale optimization problem. More importantly we highlight the differences in operations between bulk ports and container terminals which highlights the need to devise specific solutions for bulk ports. The objective is to minimize the total service time of vessels berthing at the port. We propose an exact solution algorithm based on a branch and price framework to solve the integrated problem. In the proposed model, the master problem is formulated as a set-partitioning problem, and subproblems to identify columns with negative reduced costs are solved using mixed integer programming. To obtain sub-optimal solutions quickly, a metaheuristic approach based on critical-shaking neighborhood search is presented. The proposed algorithms are tested and validated through numerical experiments based on instances inspired from real bulk port data. The results indicate that the algorithms can be successfully used to solve instances containing up to 40 vessels within reasonable computational time.     

An integrated approach to worker assignment,workforce flexibility acquisition,and task rotation

In a manufacturing environment, workforce flexibility can be achieved by cross-training and improved via job rotation. In firms with a flexible workforce, employees perform different tasks and functions in response to fluctuations in both product demands and labour resources. This paper presents a mathematical programming model that assigns workers to tasks, rotates workers between the tasks, and determines the training schedule. The objective is to minimize the total costs including training cost, flexibility cost, and productivity loss cost. A constructive-search heuristic is also developed to solve the proposed model. The algorithm provides good solutions in two phases: construction and improvement. At the construction phase, a solution is built using some problem-specific information. The quality of the solution is then enhanced by changing worker assignments at a particular time point during a planning horizon. Our computational results for a number of randomly generated test problems confirms the efficiently of the proposed method.     

An algorithm for the single-input partial pole assignment problem

An algorithm for translating unstable eigenvalues of single-input partial pole assignment problems based on rank-one transformations is suggested. Special attention is paid to the practical case where translations are constructed using inexact spectral information provided by the Arnoldi procedure. Estimates of the resulting perturbations of stable and translated poles are derived. These estimates depend on the accuracy of spectral information about the unstable poles. The algorithm proposed is illustrated with numerical examples. Bibliography: 11 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 229, 1995, pp. 5–28. Translated by A. Yu. Yeremin.     

An exact algorithm for the general quadratic assignment problem

We develop an algorithm that is based on the linearization and decomposition of a general Quadratic Assignment Problem of size n into n² Linear Assignment Problems of size (n − 1). The solutions to these subproblems are used to calculate a lower bound for the original problem, and this bound is then used in an exact branch and bound procedure. These subproblems are similar to the ‘minors’ defined by Lawler [16], but permit us to calculate tighter bounds. Computational experience is given for solution to optimality of general quadratic assignment problems is sizes up to n = 10.     

An algorithm for then×n optimum assignment problem

In this paper we present an algorithm for finding an optimum assignment for ann×n matrixM inn iterations. The method uses systematic permutations on the rows ofM and is based on the properties of optimum assignments. The implementation presented in the paper requires at mostO(n ³) in time andn ²+6n memory locations for solving a densen×n problem.This work was supported by the National Science Foundation Grant NSF ENG 74-19788.     

An efficient cost scaling algorithm for the assignment problem

The cost scaling push-relabel method has been shown to be efficient for solving minimum-cost flow problems. In this paper we apply the method to the assignment problem and investigate implementations of the method that take advantage of assignment's special structure. The results show that the method is very promising for practical use.This author's research was supported in part by ONR Young Investigator Award N00014-91-J-1855, NSF Presidential Young Investigator Grant CCR-8858097 with matching funds from AT&T, DEC and 3M, and a grant from the Powell Foundation.This author's research was supported by the above-mentioned ONR and NSF grants.     

An algorithm for finding the nucleolus of assignment games

Assignment games with side payments are models of certain two-sided markets. It is known that prices which competitively balance supply and demand correspond to elements in the core. The nucleolus, lying in the lexicographic center of the nonempty core, has the additional property that it satisfies each coalition as much as possible. The corresponding prices favor neither the sellers nor the buyers, hence provide some stability for the market. An algorithm is presented that determines the nucleolus of an assignment game. It generates a finite number of payoff vectors, monotone increasing on one side, and decreasing on the other. The decomposition of the payoff space and the lattice-type structure of the feasible set are utilized in associating a directed graph. Finding the next payoff is translated into determining the lengths of longest paths to the nodes, if the graph is acyclic, or otherwise, detecting the cycle(s). In an (m,n)-person assignment game withm = min(m,n) the nucleolus is found in at most 1/2·m(m + 3) steps, each one requiring at mostO(m·n) elementary operations.     

An integrated pest management model with delayed responses to pesticide applications and its threshold dynamics

Pulse-like pest management actions such as spraying pesticides and killing a pest instantly and the release of natural enemies at critical times can be modelled with impulsive differential equations. In practice, many pesticides have long-term residual effects and, also, both pest and natural enemy populations may have delayed responses to pesticide applications. In order to evaluate the effects of the duration of the residual effectiveness of pesticides and of delayed responses to pesticides on a pest management strategy, we developed novel mathematical models. These combine piecewise-continuous periodic functions for chemical control with pulse actions for releasing natural enemies in terms of fixed pulse-type actions and unfixed pulse-type actions. For the fixed pulse-type model, the stability threshold conditions for the pest eradication periodic solution and permanence of the model are derived, and the effects of key parameters including killing efficiency rate, decay rate, delayed response rate, number of pesticide applications and number of natural enemy releases on the threshold values are discussed in detail. The results indicate that there exists an optimal releasing period or an optimal number of pesticide applications which maximizes the threshold value. For unfixed pulse-type models, the effects of the killing efficiency rate, decay rate and delayed response rate on the pest outbreak period, and the frequency of control actions are also investigated numerically.     

An infinite dimensional convolution theorem with applications to the efficient estimation of the integrated volatility

This paper proposes a general approach to obtain asymptotic lower bounds for the estimation of random functionals. The main result is an abstract convolution theorem in a non parametric setting, based on an associated LAMN property. This result is then applied to the estimation of the integrated volatility, or related quantities, of a diffusion process, when the diffusion coefficient depends on an independent Brownian motion.