Search

The Hungarian algorithm is one of the most well-known methods in computer science literature. By this method, in each step the cost matrix is systematically reduced to a new matrix in order to obtain an optimal solution for the assignment problem. The subroutine of the algorithm includes determining the minimum number of lines needed to cover all zeros in the reduced cost matrix and modifying the matrix according to the number of lines. In this paper, firstly the methods in literature including the covering all zeros with a minimum number of lines are examined, then a new method is proposed and computational experiments are discussed. [ABSTRACT FROM AUTHOR]

The Assignment Problem is a classical problem in the field of combinatorial optimization, having a wide range of applications in a variety of contexts. In general terms, the Assignment Problem consists of determining the best assignment of tasks to agents according to a predefined objective function. Different variants of the Assignment Problem have been extensively investigated in the literature in the last 50 years. In this work, we introduce and analyze the problem of optimizing a business process model with the objective of finding the most beneficial assignment of tasks to agents. Despite similarities, this problem is distinguished from the traditional Assignment Problem in that we consider tasks to be part of a business process model, being interconnected according to defined rules and constraints. In other words, assigning a business process to agents is a more complex form of the Assignment Problem. Two main categories of business processes, assignment-independent and assignment-dependent, are distinguished. In the first category, different assignments of tasks to agents do not affect the flow of the business process, while processes in the second category contain critical tasks that may change the workflow, depending on who performs them. In each category several types of processes are studied. Algorithms for finding optimal and near-optimal solutions to these categories are presented. For the first category, depending on the type of process, the Hungarian algorithm is combined with either the analytical method or simulation to provide an optimal solution. For the second category, we introduce two algorithms. The first one finds an optimal solution, but is feasible only when the number of critical tasks is small. The second algorithm is applicable to large number of critical tasks, but provides a near-optimal solution. In the second algorithm a hill-climbing heuristic method is combined with the Hungarian algorithm and simulation to find an overall near-optimal solution. A series of tests is conducted which demonstrates that the proposed algorithms efficiently find optimal solutions for assignment-independent and near-optimal solutions for assignment-dependent processes. [ABSTRACT FROM AUTHOR]

The Hungarian algorithm is one of the most well-known methods in computer science literature. By this method, in each step the cost matrix is systematically reduced to a new matrix in order to obtain an optimal solution for the assignment problem. The subroutine of the algorithm includes determining the minimum number of lines needed to cover all zeros in the reduced cost matrix and modifying the matrix according to the number of lines. In this paper, firstly the methods in literature including the covering all zeros with a minimum number of lines are examined, then a new method is proposed and computational experiments are discussed. [ABSTRACT FROM AUTHOR]

Role assignment is a critical task in role-based collaboration. It has three steps, i.e., agent evaluation, group role assignment, and role transfer, where group role assignment is a time-consuming process. This paper clarifies the group role assignment problem (GRAP), describes a general assignment problem (GAP), converts a GRAP to a GAP, proposes an efficient algorithm based on the Kuhn–Munkres (K-M) algorithm, conducts numerical experiments, and analyzes the solutions' performances. The results show that the proposed algorithm significantly improves the algorithm based on exhaustive search. The major contributions of this paper include formally defining the GRAPs, giving a general efficient solution for them, and expanding the application scope of the K-M algorithm. This paper offers an efficient enough solution based on the K-M algorithm that outperforms significantly the exhaustive search approach. [ABSTRACT FROM PUBLISHER]

This paper addresses the organization structure design problem in a make-to-order (MTO) operation environment. A mathematical model is presented to aid an operations manager in an MTO environment to select a set of potential managerial layers to minimize the operation and supervision cost. With a given Work Breakdown Structure (WBS) for any specific project, solving this model leads an optimal organization structure design. The proposed model considers allocation tasks to workers, considering complexity and compatibility of each task with respect to workers, and the requirement of management for planning, execution, training and control in a hierarchical organization. This model addresses the span of control problem and provides a quantitative approach to the organization design problem and is intended for applications as a design tool in the make-to-order industries. [ABSTRACT FROM AUTHOR]

Abstract: We consider the following model of cellular networks. Each base station has a given finite capacity, and each client has some demand and profit. A client can be covered by a specific subset of the base stations, and its profit is obtained only if its demand is provided in full. The goal is to assign clients to base stations, so that the overall profit is maximized subject to base station capacity constraints. In this work, we present a distributed algorithm for the problem, that runs in polylogarithmic time, and guarantees an approximation ratio close to the best known ratio achievable by a centralized algorithm. [Copyright &y& Elsevier]

Abstract: Random third party quality audits are mandatory by the regulations for public construction projects in Taiwan. This project and auditor selection process is normally carried out based on personal experience and the quality of the selection outcome is hard to predict and control. This is a difficult work assignment problem because there are normally hundreds of projects and dozens of auditors to choose from. The purpose of this research is to establish a genetic algorithm-based model to assist with the project selection and auditor assignment process. The model is set up to find the optimal match between the project characteristics and auditor expertise from approximately 5.09E+29 possible combinations. Information provided by the Kaohsiung County Government is used to validate the model. The results show that the model is not only valid but also able to produce a “much better match” between projects and auditors when comparing to manual assignment. [Copyright &y& Elsevier]

Abstract: 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. [Copyright &y& Elsevier]

We show that several decision problems originating from max-plus or tropical convexity are equivalent to zero-sum two player game problems. In particular, we set up an equivalence between the external representation of tropical convex sets and zero-sum stochastic games, in which tropical polyhedra correspond to deterministic games with finite action spaces. Then, we show that the winning initial positions can be determined from the associated tropical polyhedron. We obtain as a corollary a game theoretical proof of the fact that the tropical rank of a matrix, defined as the maximal size of a submatrix for which the optimal assignment problem has a unique solution, coincides with the maximal number of rows (or columns) of the matrix which are linearly independent in the tropical sense. Our proofs rely on techniques from non-linear Perron-Frobenius theory. [ABSTRACT FROM AUTHOR]

Abstract: In view of the simplex-type algorithm, the assignment problem is inherently highly degenerate. It may be the optimal basis has changed, but the optimal assignment is unchanged when parameter variation occurs. Degeneracy then makes sensitivity analysis difficult, as well as makes the classical Type I range, which identifies the range the optimal basis unchanged, impractical. In this paper, a labeling algorithm is proposed to identify two other sensitivity ranges – Type II range and Type III range. The algorithm uses the reduced cost matrix, provided in the final results of most solution algorithms for AP, to determine the Type II range which reflects the stability of the current optimal assignment. Thus, the algorithm generates a streamlined situation from searching the optimal solution until performing the sensitivity analysis of the assignment problem. The Type III range, reflecting the flexibility of optimal decision making, can be obtained immediately after the Type II range is determined. Numerical examples are presented to demonstrate the algorithm. [Copyright &y& Elsevier]

Abstract: We extend the classical linear assignment problem to the case where the cost of assigning agent to task is a multiplication of task ’s cost parameter by a cost function of agent . The cost function of agent is a linear function of the amount of resource allocated to the agent. A solution for our assignment problem is defined by the assignment of agents to tasks and by a resource allocation to each agent. The quality of a solution is measured by two criteria. The first criterion is the total assignment cost and the second is the total weighted resource consumption. We address these criteria via four different problem variations. We prove that our assignment problem is -hard for three of the four variations, even if all the resource consumption weights are equal. However, and somewhat surprisingly, we find that the fourth variation is solvable in polynomial time. In addition, we find that our assignment problem is equivalent to a large set of important scheduling problems whose complexity has been an open question until now, for three of the four variations. [Copyright &y& Elsevier]

Abstract: In an effort to hold back the domestic effects caused by the global economic downturn, many countries present a variety of economic stimulus programs to create and save employment opportunities. Among them, offering short-term jobs to unemployed citizens is one of the most popular plans. Allocation of short-term jobs to jobless citizens has become an important issue since an improper allocation could bring about the dissatisfaction and complaints from citizens. In this paper, we propose a novel mechanism which is based on genetic algorithm (GA) to allocate the short-term jobs. The allocation is decided by a system which considers the unemployed citizens’ preferences. Employing GA to solve the allocation problem shows that the complicated problem can be well solved and the job allocation can be properly made. Moreover, this easy-to-use system can facilitate the allocation in different scenarios. [Copyright &y& Elsevier]

We consider the problem of multi-robot task-allocation when robots have to deal with uncertain utility estimates. Typically an allocation is performed to maximize expected utility; we consider a means for measuring the robustness of a given optimal allocation when robots have some measure of the uncertainty (e.g. a probability distribution, or moments of such distributions). We introduce the interval Hungarian algorithm, a new algorithm that extends the classic Kuhn—Munkres Hungarian algorithm to compute the maximum interval of deviation, for each entry in the assignment matrix, which will retain the same optimal assignment. The algorithm has a worst-case time complexity of O(n4); we also introduce a parallel variant with O(n3) running time, which is able to exploit the concurrent computing capabilities of distributed multi-robot systems. This provides an efficient measurement of the tolerance of the allocation to the uncertainties and dynamics, for both a specific interval and a set of interrelated intervals. We conduct experiments both in simulation and with physical robots to validate the approach and to gain insight into the effect of location uncertainty on allocations for multi-robot multi-target navigation tasks. [ABSTRACT FROM AUTHOR]

The pilot mission assignment problem is addressed to improve mission efficiency, with low level of accident risk. In this paper, an integrated framework for the risk management of pilot mission assignment is presented, which can be applied in Korean army helicopter units, using the IDEA (Imprecise Data Envelopment Analysis) method. The risks due to pilots, missions and helicopters are evaluated based on imprecise data, and the assignment of pilots to missions and helicopters is performed using goal programming with risk scores. The process is designed to obtain smaller variances in the risk evaluation based on the interval bounded data so that it can be combined with the AHP (Analytic Hierarchy Process). These numerical experiments provide reasonable solutions to the problem of risk management of pilot mission assignment. Significance: The suggested framework provides an efficient risk management as applied in the resource allocation in consideration of the risk expectation and variance as well. It is expected that this robust procedure for the resource allocation using the mathematical optimization may provide more confident to the customer during its application in the area of risk management. The approach addressed in the paper is new and sophisticated in the sense that the risk evaluation and risk based allocation adopted the IDEA method and mathematical programming using history data. [ABSTRACT FROM AUTHOR]

Abstract: We study an aggregation problem in which a society has to determine its position on each of several issues, based on the positions of the members of the society on those issues. There is a prescribed set of feasible evaluations, i.e., permissible combinations of positions on the issues. The binary case of this problem, where only two positions are allowed on each issue, is by now quite well understood. We consider arbitrary sets of conceivable positions on each issue. This general framework admits the modeling of aggregation of various types of evaluations, including: assignments of candidates to jobs, choice functions from sets of alternatives, judgments in many-valued logic, probability estimates for events, etc. We require that the aggregation be performed issue-by-issue, and that the social position on each issue be supported by at least one member of the society. The set of feasible evaluations is called an impossibility domain if these requirements are satisfied for it only by dictatorial aggregation; that is to say, if it gives rise to an analogue of Arrow''s impossibility theorem for preference aggregation. We obtain a two-part sufficient condition for an impossibility domain, and show that the major part is a necessary condition. For the ternary case, where three positions are allowed on each issue, we get a full characterization of impossibility domains. [Copyright &y& Elsevier]

Abstract: In this brief note we consider rank aggregation, a popular method in voting theory, social choice, business decisions, etc. Mathematically the problem is to find a permutation—viewed as a vector—that minimizes the sum of the -distances to a given family of permutations. The problem may be solved as an assignment problem and we establish several properties of optimal solutions in this problem. [Copyright &y& Elsevier]

In this paper, we present a theoretical investigation and an extensive computational study of exterior point simplex algorithm (EPSA) initialization methods for the assignment problem (AP). We describe the exterior point algorithm using three different initialization methods. Effective implementations are explored for each initialization method. Then we perform an experimental evaluation on a large set of benchmark problems from the TSPLib 95 and OR Library collections. The results obtained demonstrate the advantages of the three initialization methods. Finally, we give a theoretical justification of the initialization methods efficiency. We explain theoretically the computational ranking for these methods. [ABSTRACT FROM AUTHOR]

Abstract: This paper proposes modified particle swarm optimization to solve the problem of activity assignment of fourth party logistics (4PL) with preemptive structure. In practice, decision makers must consider goals of different importance when they encounter 4PL decision problems. Previous studies have adopted weighted fuzzy goal programming to design optimization problems. However, it is difficult for decision makers to determine proper weights. This paper proposes a decision making method based on preemptive fuzzy goal programming and a modified PSO. The proposed method does not require weights, and prevents results without feasible solutions caused by improper resource setting. Furthermore, this paper proposes a modified PSO with mutation operator extension. Numerical analysis shows that proposed modified PSOs prevent algorithms from caving prematurely into local optimums. [Copyright &y& Elsevier]

An interesting variant of the assignment problem is the case where each partial assignment of an individual to a job involves multiple inputs and outputs. In this paper, three issues about this problem are discussed: finding an efficient assignment, verifying the efficiency of a solution and restoring the efficiency of an inefficient assignment. For the first issue, a current method, proposed by Chen and Lu, is compared with a proposed multiobjective formulation and for the second and third ones, a two-phase method is developed, which is based on the simplex method and the Dantzig-Wolfe decomposition algorithm. [ABSTRACT FROM AUTHOR]

We consider some variant models, having changeover cost, of the assignment problem. In these models, multiple assignments to an operator are allowed. In addition to assignment costs, a changeover cost is incurred if an operator does one job after another is completed. Two different types of changeover costs and related two models are considered. Mathematical programming formulations are given for the models. When changeover costs are dependent on the operator but independent of the jobs and are non-negative, a linear programming model is obtained. For the case when changeover costs are dependent on the jobs, a linear integer programming formulation is obtained. We also show that, this problem is strongly NP-hard. A heuristic solution method is suggested for it. Numerical findings on the performance of the method are given. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, the equilibrium optimization problem is proposed and the assignment problem is extended to the equilibrium multi-job assignment problem, equilibrium multi-job quadratic assignment problem and the minimum cost and equilibrium multi-job assignment problem. Furthermore, the mathematical models of the equilibrium multi-job assignment problem and the equilibrium multi-job quadratic assignment problem with fuzzy parameters are formulated. Finally, a genetic algorithm is designed for solving the proposed programming models and some numerical examples are given to verify the efficiency of the designed algorithm. [Copyright &y& Elsevier]

Abstract: This note shows that the data envelopment analysis (DEA) models formulated by Chen and Lu [L.H. Chen, H.W. Lu, An extended assignment problem considering multiple inputs and outputs, Appl. Math. Modell. 31 (2007) 2239–2248] are not correct. The enveloping form of the Chen and Lu formulation is studied and a simple example is presented to demonstrate the differences between the efficiency scores resulted of the Chen and Lu formulation, and the true ones. [Copyright &y& Elsevier]

Abstract: This paper develops the goal programming technique to solve the multiple objective assignment problem. The required model is formulated and an appropriate solution method is presented. The proposed method, which is a decomposition method, exploits the total unimodularity feature of the assignment problem and effectively reduces the computational efforts. Some issues related to the efficiency of a GP solution are stated and some specialized techniques for detecting and restoring efficiency are proposed. [Copyright &y& Elsevier]

Abstract: In R&D project selection, experts (or external reviewers) always play a very important role because their opinions will have great influence on the outcome of the project selection. It is also undoubted that experts with high expertise level will make useful and professional judgments on the projects to be selected. So, how to assign the most appropriate experts to the relevant proposals is a very significant issue. This paper presents a hybrid knowledge and model approach which integrates mathematical decision models with knowledge rules, for the assignment of external reviewers to R&D project proposals. The approach can be applied to government funding agencies in China and other countries. [Copyright &y& Elsevier]

Abstract: Brualdi brought to Geršgorin Theory the concept that the digraph G(A) of a matrix A is important in studying whether A is singular. He proved, for example, that if, for every directed cycle of G(A), the product of the diagonal entries exceeds the product of the row sums of the moduli of the off-diagonal entries, then the matrix is nonsingular. We will show how, in polynomial time, that condition can be tested and (if satisfied) produce a diagonal matrix D, with positive diagonal entries, such that AD (where A is any nonnnegative matrix satisfying the conditions) is strictly diagonally dominant (and so, A is nonsingular). The same D works for all matrices satisfying the conditions. Varga raised the question of whether Brualdi’s conditions are sharp. Improving Varga’s results, we show, if G is scwaltcy (strongly connected with at least two cycles), and if the Brualdi conditions do not hold, how to construct (again in polynomial time) a complex matrix whose moduli satisfy the given specifications, but is singular. [Copyright &y& Elsevier]

In this paper we propose a generalization of the Assignment Problem. First, we describe an algorithm, based on network flow techniques, that obtains just one solution of the approached problem; further, we develop an algorithm that is able to find all the solutions. Finally, we discuss how this general form of the Assignment Problem can be applied in solving the Rank Aggregation Problem, in the case of rankings with ties. [ABSTRACT FROM AUTHOR]

Abstract: The existing assignment problems for assigning n jobs to n individuals are limited to the considerations of cost or profit incurred by each possible assignment. However, in real applications, various inputs and outputs are usually concerned in an assignment problem, such as a general decision-making problem. This paper develops a procedure for resolving assignment problems with multiple incommensurate inputs and outputs for each possible assignment. The concept of the relative efficiency in using various resources, instead of cost or profit, is adopted for each possible assignment of the problem. Data envelopment analysis (DEA) is employed in this paper to measure the efficiency of one assignment relative to that of the others according to a set of decision-making units. A composite efficiency index, consisting of two kinds of relative efficiencies under different comparison bases, is defined to serve as the performance measurement of each possible assignment in the problem formulation. A mathematical programming model for the extended assignment problem is proposed, which is then expressed as a classical integer linear programming model to determine the assignments with the maximum efficiency. A numerical example is used to demonstrate the approach. [Copyright &y& Elsevier]

Although the basic version of the linear assignment problem (AP) can be solved very efficiently, there are variants of this problem which are much harder, some being NP-complete or with undecided computational complexity. One of them is the parity AP, in which an optimal permutation of a prescribed parity is sought. A related variant is the weak parity AP, in which we only need to know whether the set of optimal permutations to the AP contains permutations of both parities. In this short note, we prove that both these problems are efficiently solvable for Monge matrices, as well as for diagonally dominant symmetric matrices. We also note that the parity bottleneck AP is polynomially solvable for any matrix. [ABSTRACT FROM AUTHOR]

The article presents a study which proposes a new hierarchical method for the flexible job-shop scheduling problem (FJSP). The FJSP is a nondeterministic polynomial-time hard since it is an extension of the job-shop scheduling problem. The first method proposed is based successively on a heuristic approach and a local search. The second one is based on a branch-and-bound algorithm.

The assignation of new students to schools could be considered a problem into the process that manages the student places at the Bogotá educational system. It is possible to model that problem like an assignation with similar objects, the solutions of this problem increase in complexity when consider the large number of students and other additional restrictions. This Document explores two strategies to approach the student assignation problem, which differ from the current "greedy" algorithm that is used into the assignation process. Initially a Branch and Price algorithm is discussed which presents convergence problems, and then the Auction Algorithm is studied. [ABSTRACT FROM AUTHOR]

• Measures of diversity within populations, and distance between populations, are compared for organisms with an asexual or mixed mode of reproduction. Examples are drawn from studies of plant pathogenic fungi based on binary traits including presence/absence of DNA bands or virulence/avirulence to differential hosts. • Commonly used measures of population diversity or genetic distance consider either genotype frequencies or allele frequencies. Kosman's diversity and distance measures are the most suitable for populations with an asexual or mixed mode of reproduction, because by considering genetic patterns of all individuals they take into account not just the genotype frequencies but also the genetic similarities between genotypes in the populations. • The Kosman distance and diversity measures for populations can be calculated using different measures of dissimilarity between individuals (the simple mismatch, Jaccard and Dice coefficients of dissimilarity). Kosman's distances based on the simple mismatch and Jaccard dissimilarities are metrics. • Comparisons of diversity indices for hypothetical examples as well as for actual data sets are presented to demonstrate that inferences from diversity analysis of populations can be driven by techniques of diversity and distance assessments and not only data driven. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we study the relationship between the Asymmetric Traveling Salesman Problem (ATSP) and the Cycle Cover Problem in terms of the strength of the triangle inequality on the edge costs in the given complete directed graph instance, . The strength of the triangle inequality is captured by parametrizing the triangle inequality as follows. A complete directed graph with a cost function is said to satisfy the -parametrized triangle inequality if for all distinct . Then the graph is called a -triangular graph. For any -triangular graph , for , we show that , where and are the costs of an optimum Hamiltonian cycle and an optimum cycle cover respectively. In addition, we observe that there exists an infinite family of -triangular graphs for each valid which demonstrates the near-tightness (up to a factor of ) of the above bound. For , the ratio can become unbounded. The upper bound is shown constructively and can also be viewed as an approximation algorithm for ATSP with parametrized triangle inequality. We also consider the following problem: in a -triangular graph, does there exist a function such that is bounded above by ? (Here and are the costs of the maximum cost and minimum cost edges respectively.) We show that when , . This upper bound is sharp in the sense that there exist -triangular graphs with . Moreover, for , no such function exists. [Copyright &y& Elsevier]

Abstarct: This paper presents a technique that uses the Wang recurrent neural network with the “Winner Takes All” principle to solve the traveling salesman problem (TSP). When the Wang neural network presents solutions for the assignment problem with all constraints satisfied, the “Winner Takes All” principle is applied to the values in the neural network''s decision variables, with the additional constraint that the new solution must form a feasible route for the TSP. The results from this new technique are compared to other heuristics (SOM, SA and heuristics of remotion and insertion of arcs), with data from the traveling salesman problem library (TSPLIB). The 2-opt local search technique is applied to the final solutions of the proposed technique and shows a considerable improvement of the results. The advantages of this new technique are the easy computational implementation, the low computational complexity, the good results obtained and the possibility of solving symmetrical and asymmetrical problems with the same technique. [Copyright &y& Elsevier]

We consider the gap between the cost of an optimal assignment in a complete bipartite graph with random edge weights, and the cost of an optimal traveling salesman tour in a complete directed graph with the same edge weights. Using an improved ‘patching’ heuristic, we show that with high probability the gap is O((ln n)²/n), and that its expectation is Ω(1/n). One of the underpinnings of this result is that the largest edge weight in an optimal assignment has expectation Θ(ln n/n). A consequence of the small assignment-TSP gap is an eÕ(√n)-time algorithm which, with high probability, exactly solves a random asymmetric traveling salesman instance. In addition to the assignment-TSP gap, we also consider the expected gap between the optimal and second-best assignments; it is at least Ω(1/n²) and at most O(ln n/n²). [ABSTRACT FROM AUTHOR]

Abstract: This paper investigates a two-objective -cardinality assignment problem. As a result, a chance-constrained goal programming model is constructed for the problem. Also, tabu search algorithm based on fuzzy simulation is designed to solve the problem. Finally, a numerical example is presented to show the application of the algorithm. [Copyright &y& Elsevier]

The considered assignment problem generalizes its classical counterpart by the existence of some incompatibility constraints limiting the assignment of tasks to processing units within groups of mutually exclusive tasks. The groups are defined for each processing unit and the constraints allow at most one task from each group to be assigned to the corresponding processing unit. The processing units can normally process a certain number of tasks without any cost; this capacity can be extended, however, at some extra marginal cost that is non-decreasing with the number of additional tasks. Each task has to be assigned to exactly one processing unit and has some preference for the assignment; it is expressed for each pair ‘task-processing unit’ by a dissatisfaction degree. The quality of feasible assignments is evaluated by three criteria: g 1-the maximum dissatisfaction of tasks, g 2-the total dissatisfaction of tasks, g 3-the total cost of processing units. If there is no feasible assignment, tasks and processing units creating a blocking configuration are identified and all actions of unblocking are proposed. Formal properties of blocking configurations and unblocking actions are proven, and an interactive procedure for exploring the set of non-dominated assignments is described together with illustrative examples processed by special software. [ABSTRACT FROM AUTHOR]

This paper deals with automated guided vehicles (AGVs) which transport containers between the quay and the stack on automated container terminals. The focus is on the assignment of transportation jobs to AGVs within a terminal control system operating in real time. First, we describe a rather common problem formulation based on due times for the jobs and solve this problem both with a greedy priority rule based heuristic and with an exact algorithm. Subsequently, we present an alternative formulation of the assignment problem, which does not include due times. This formulation is based on a rough analogy to inventory management and is solved using an exact algorithm. The idea behind this alternative formulation is to avoid estimates of driving times, completion times, due times, and tardiness because such estimates are often highly unreliable in practice and do not allow for accurate planning. By means of simulation, we then analyze the different approaches. We show that the inventory-based model leads to better productivity on the terminal than the due-time-based formulation. [ABSTRACT FROM AUTHOR]

Similarity of edge labeled graphs is considered in the sense of minimum squared distance between corresponding values. Vertex correspondences are established by isomorphisms if both graphs are of equal size and by subisomorphisms if one graph has fewer vertices than the other. Best fit isomorphisms and subisomorphisms amount to solutions of quadratic assignment problems and are computed exactly as well as approximately by minimum cost flow, linear assignment relaxations and related graph algorithms. [ABSTRACT FROM AUTHOR]

Abstract: This paper presents some computational properties of the rank-distance, a measure of similarity between partial rankings. We show how this distance generalizes the Spearman footrule distance, preserving its good computational complexity: the rank-distance between two partial rankings can be computed in linear time, and the rank aggregation problem can be solved in polynomial time. Further, we present a generalization of the rank-distance to strings, which permits to solve the median string problem in polynomial time. This appears rather surprising to us given the fact that for other non-trivial string distances, such as edit-distance, this problem is NP-hard. [Copyright &y& Elsevier]

Abstract: According to Kauffman’s theory [S. Kauffman, The Origins of Order, Self-Organization and Selection in Evolution, Oxford University Press, New York, 1993], enzymes in living organisms form a dynamic network, which governs their activity. For each enzyme the network contains: [•] a collection of enzymes affecting the enzyme and [•] a Boolean function prescribing next activity of the enzyme as a function of the present activity of the affecting enzymes. Kauffman’s original pure random structure of the connections was criticized by Barabasi and Albert [A.-L. Barabasi, R. Albert, Emergence of scaling in random networks, Science 286 (1999) 509–512]. Their model was unified with Kauffman’s network by Aldana and Cluzel [M. Aldana, P. Cluzel, A natural class of robust networks, Proc. Natl. Acad. Sci. USA 100 (2003) 8710–8714]. Kauffman postulated that the dynamic character of the network determines the fitness of the organism. If the network is either convergent or chaotic, the chance of survival is lessened. If, however, the network is stable and critical, the organism will proliferate. Kauffman originally proposed a special type of Boolean functions to promote stability, which he called the property canalyzing. This property was extended by Shmulevich et al. [I. Shmulevich, H. Lähdesmäki, E.R. Dougherty, J. Astola, W. Zhang, The role of certain Post classes in Boolean network models of genetic networks, Proc. Natl. Acad. Sci. USA 100 (2003) 10734–10739] using Post classes. Following their ideas, we propose decision tree functions for enzymatic interactions. The model is fitted to microarray data of Cogburn et al. [L.A. Cogburn, W. Wang, W. Carre, L. Rejtő, T.E. Porter, S.E. Aggrey, J. Simon, System-wide chicken DNA microarrays, gene expression profiling, and discovery of functional genes, Poult. Sci. Assoc. 82 (2003) 939–951; L.A. Cogburn, X. Wang, W. Carre, L. Rejtő, S.E. Aggrey, M.J. Duclos, J. Simon, T.E. Porter, Functional genomics in chickens: development of integrated-systems microarrays for transcriptional profiling and discovery of regulatory pathways, Comp. Funct. Genom. 5 (2004) 253–261]. In microarray measurements the activity of clones is measured. The problem here is the reconstruction of the structure of enzymatic interactions of the living organism using microarray data. The task resembles summing up the whole story of a film from unordered and perhaps incomplete collections of its pieces. Two basic ingredients will be used in tackling the problem. In our earlier works [L. Rejtő, G. Tusnády, Evolution of random Boolean NK-models in Tierra environment, in: I. Berkes, E. Csaki, M. Csörgő (Eds.), Limit Theorems in Probability an Statistics, Budapest, vol. II, 2002, pp. 499–526] we used an evolutionary strategy called Tierra, which was proposed by Ray [T.S. Ray, Evolution, complexity, entropy and artificial reality, Physica D 75 (1994) 239–263] for investigating complex systems. Here we apply this method together with the tree–structure of clones found in our earlier statistical analysis of microarray measurements [L. Rejtő, G. Tusnády, Clustering methods in microarrays, Period. Math. Hungar. 50 (2005) 199–221]. [Copyright &y& Elsevier]

A common approach to determining corresponding points on two shapes is to compute the cost of each possible pairing of points and solve the assignment problem (weighted bipartite matching) for the resulting cost matrix. We consider the problem of solving for point correspondences when the shapes of interest are each defined by a single, closed contour. A modification of the standard assignment problem is proposed whereby the correspondences are required to preserve the ordering of the points induced from the shapes' contours. Enforcement of this constraint leads to significantly improved correspondences. Robustness with respect to outliers and shape irregularity is obtained by required only a fraction of feature points to be matched. Furthermore, the minimum matching size may be specified in advance. We present efficient dynamic programming algorithms to solve the proposed optimization problem. Experiments on the Brown and MPEG-7 shape databases demonstrate the effectiveness of the proposed method relative to the standard assignment problem. [ABSTRACT FROM AUTHOR]

Abstract: The assignment problem is to find the total costs optimal jobs assignment schedule where n jobs are allocated to n workers, and each worker receives exactly just one job, such that the total cost is optimal. The quadratic assignment problem with penalty takes three types of costs into consideration: direct cost, interactive cost an penalty. In this paper, the fuzzy quadratic assignment problem with penalty is formulated as expected value model, chance-constrained programming and dependent-chance programming according to various decision criteria, and the crisp equivalents are given. Furthermore, hybrid genetic algorithm is designed for solving the proposed fuzzy programming models. [Copyright &y& Elsevier]

Determining true genetic dissimilarity between individuals is an important and decisive point for clustering and analysing diversity within and among populations, because different dissimilarity indices may yield conflicting outcomes. We show that there are no acceptable universal approaches to assessing the dissimilarity between individuals with molecular markers. Different measures are relevant to dominant and codominant DNA markers depending on the ploidy of organisms. The Dice coefficient is the suitable measure for haploids with codominant markers and it can be applied directly to (0,1)-vectors representing banding profiles of individuals. None of the common measures, Dice, Jaccard, simple mismatch coefficient (or the squared Euclidean distance), is appropriate for diploids with codominant markers. By transforming multiallelic banding patterns at each locus into the corresponding homozygous or heterozygous states, a new measure of dissimilarity within locus was developed and expanded to assess dissimilarity between multilocus states of two individuals by averaging across all codominant loci tested. There is no rigorous well-founded solution in the case of dominant markers. The simple mismatch coefficient is the most suitable measure of dissimilarity between banding patterns of closely related haploid forms. For distantly related haploid individuals, the Jaccard dissimilarity is recommended. In general, no suitable method for measuring genetic dissimilarity between diploids with dominant markers can be proposed. Banding patterns of diploids with dominant markers and polyploids with codominant markers represent individuals’ phenotypes rather than genotypes. All dissimilarity measures proposed and developed herein are metrics. [ABSTRACT FROM AUTHOR]

In the assignment problem units of supply are assigned on a one-to-one basis to units of demand so as to minimize the sum of the cost associated with each supply-to-demand matched pair. Defined on a network, the supplies and demands are located at vertices and the cost of a supply-to-demand matched pair is the distance between them. This paper considers a two-stage stochastic program for locating the units of supply based upon only a probabilistic characterization of demand. The objective of the first-stage location problem is to minimize the expected cost of the second-stage assignment problem. Principal results include showing that the problem is NP-hard on a general network, has a simple solution procedure on a line network, and is solvable by a low order polynomial greedy procedure on a tree network. Potential applications are discussed. [ABSTRACT FROM AUTHOR]

In this work, we consider a combinatorial "dominating subset with minimal weight" problem, which is an associative problem for solving global optimization problem. This problem can be expressed as a kind of assignment problem. The mathematical model and the economical interpretations of the problem are given and its properties are described. Then, we propose a new algorithm which has a ratio bound in polynomial time, by using above properties for solving the problem and present the results of numerical experiments. † E-mail: bordin@sci.ege.edu.tr [ABSTRACT FROM AUTHOR]

With the increasing availability of real-time information and communication systems in logistics, the need for appropriate planning algorithms, which make use of this technology, arises. Customers in transport markets increasingly expect quicker and more flexible fulfillment of their orders, especially in the electronic marketplace. This paper considers a dynamic routing system that dispatches a fleet of vehicles according to customer orders arriving at random during the planning period. Each customer order requires a transport from a pickup location to a delivery location in a given time window. The system disposes of online communication with all drivers and customers and, in addition, disposes of online information on travel times from a traffic management center. This paper presents a planning framework for this situation which, to our knowledge, has not yet been addressed in the literature. It then describes three routing procedures for event-based dispatching, which differ in the length of the planning horizon per event. We focus on the use of dynamic travel time information, which requires dynamic shortest path calculations. The procedures are tested and compared using real-life data of an urban traffic management center and a logistics service provider. [ABSTRACT FROM AUTHOR]

The problem of assigning identical servers to different customer classes with the objectives of optimizing customer service and resource utilization is analysed. The problem that motivated this research is the assignment of batch jobs in a computer centre running the operating system MYS (Multiple Virtual Storage). A mathematical formulation of the problem is presented and its computational complexity discussed. A new schema for the definition of customer classes and a heuristic for the assignment of servers to classes are developed and applied to the problem. Numerical results show the efficiency of the procedure as compared with other previously utilized methods. The final part of the paper presents the conclusions and recommendations for further research. [ABSTRACT FROM AUTHOR]

Analyzes the max algebra and the linear assignment problem. Basic notions of max-algebra; Linear equation system in max-algebra; Information on the minimal-dimensional realization of discrete event dynamical systems.

Let us denote a⊕b=max(a,b) and a⊗b=a+b for a,b∈R=R∪{−∞} and extend this pair of operations to matrices and vectors in the same way as in linear algebra. We present an O(n2(m+n log n)) algorithm for finding all essential terms of the max-algebraic characteristic polynomial of an n×n matrix over R with m finite elements. In the cases when all terms are essential, this algorithm also solves the following problem: Given an n×n matrix A and k∈{1,…,n}, find a k×k principal submatrix of A whose assignment problem value is maximum. [Copyright &y& Elsevier]

We survey recent developments in the fields of bipartite matchings, linear sum assignment and bottleneck assignment problems and applications, multidimensional assignment problems, quadratic assignment problems, in particular lower bounds, special cases and asymptotic results, biquadratic and communication assignment problems. [Copyright &y& Elsevier]