An addendum on the incremental assignment problem

In Toroslu and Üçoluk [I.H. Toroslu, G. Üçoluk, Incremental assignment problem, Information Sciences 177 (2007) 1523-1529] the incremental assignment problem is defined as follows. A new pair of vertices and their incident edges are added to a weighted bipartite graph whose maximum-weighted matching is already known, and the maximum-weighted matching of the extended graph is sought. An O(n²) algorithm for the problem has been derived, with n the size of a partition in the bipartite graph. We point out that such a result can be found in literature.     

A negative dual rectangle cancellation algorithm for the linear assignment problem

In this paper, we consider three alternative primal models and their corresponding alternative dual models for the linear assignment problem. We then define the concept of Negative Dual Rectangle (NDR) and suggest an algorithm that solves two of these dual problems by repeatedly finding and cancelling NDRs until it yields an optimal solution to the assignment problem. The algorithm is simple, flexible, efficient, and unified. We also introduce the notion of partial zero cover as an interpretation of an NDR. We then introduce some heuristic methods for finding NDRs. We also state and prove a lemma to establish the optimal use of an NDR. Furthermore, we show that on a new class of benchmark instances that is introduced in this paper the running time of our algorithm is highly superior to a well-known pure shortest path algorithm.     

Genetic algorithm for the personnel assignment problem with multiple objectives

The assignment problem is a well-known graph optimization problem defined on weighted-bipartite graphs. The objective of the standard assignment problem is to maximize the summation of the weights of the matched edges of the bipartite graph. In the standard assignment problem, any node in one partition can be matched with any node in the other partition without any restriction. In this paper, variations of the standard assignment problem are defined with matching constraints by introducing structures in the partitions of the bipartite graph, and by defining constraints on these structures. According to the first constraint, the matching between the two partitions should respect the hierarchical-ordering constraints defined by forest and level graph structures produced by using the nodes of the two partitions respectively. In order to define the second constraint, the nodes of the partitions of the bipartite graph are distributed into mutually exclusive sets. The set-restriction constraint enforces the rule that in one of the partitions all the elements of each set should be matched with the elements of a set in the other partition. Even with one of these constraints the assignment problem becomes an NP-hard problem. Therefore, the extended assignment problem with both the hierarchical-ordering and set-restriction constraints becomes an NP-hard multi-objective optimization problem with three conflicting objectives; namely, minimizing the numbers of hierarchical-ordering and set-restriction violations, and maximizing the summation of the weights of the edges of the matching. Genetic algorithms are proven to be very successful for NP-hard multi-objective optimization problems. In this paper, we also propose genetic algorithm solutions for different versions of the assignment problem with multiple objectives based on hierarchical and set constraints, and we empirically show the performance of these solutions.     

A Heuristic for Dijkstra's Algorithm with Many Targets and Its Use in Weighted Matching Algorithms

Abstract. We consider the single-source many-targets shortest-path (SSMTSP) problem in directed graphs with non-negative edge weights. A source node s and a target set T is specified and the goal is to compute a shortest path from s to a node in T . Our interest in the shortest path problem with many targets stems from its use in weighted bipartite matching algorithms. A weighted bipartite matching in a graph with n nodes on each side reduces to n SSMTSP problems, where the number of targets varies between n and 1 . The SSMTSP problem can be solved by Dijkstra's algorithm. We describe a heuristic that leads to a significant improvement in running time for the weighted matching problem; in our experiments a speed-up by up to a factor of 12 was achieved. We also present a partial analysis that gives some theoretical support for our experimental findings.     

On the variable-depth-search heuristic for the linear-cost generalized assignment problem

The classical assignment problem seeks to determine a mapping between a set of assignees and a set of assignments. The linear cost assignment problem (LCGAP), as a generalized model, incorporates the relative workloads between assignees and assignments. Although LCGAP is computationally intractable, it has been extensively studied because of its practical implications in many real world situations. Variable-depth-search heuristic (VDSH) method is one of the solution methods that have been developed to produce quality near-optimal solutions to LCGAP. The main structure of VDSH consists of two basic operations: reassign and swap. In this paper, we make further observations on this effective heuristic method through a series of computational experiments. The numerical results statistically evince that different combina-tions of these two operations will result in solutions of different quality levels. These findings are expected to have similar implications to search heuristics for other optimization problems.     

An orthogonal systolic design for the assignment problem

A systolic array for the solution of the assignment problem is presented. The algorithm requires O(n²) time on an orthogonally connected array of (n + 2) * (n + 2) cells consisting of simple adders and control logic. The design is area efficient and incorporates the new concept of a Systolic Control Ring (SCR) to generate the necessary systolic wavefronts in any orientation within the design, while special cells are positioned only on the periphery of the design. The design was simulated and tested by an OCCAM program.     

基于本体和二部图的网格服务发现算法研究

为了提高网格服务发现的查全率、查准率和效率,论文设计了一个基于本体和二部图的网格服务发现算法OGSDA-BG。该算法把请求服务和发布服务的属性集分别作为二部图顶点集,所有匹配属性之间的连线为边,边权是属性匹配度,把问题转换为二部图的最优完全匹配。实验结果表明该算法的查全率和查准率较以前的算法提高了10%~50%,尽管服务发现的效率降低10%左右,但是在可接受范围之内。     

Exact and heuristic algorithms for the interval data robust assignment problem

We consider the Assignment Problem with interval data, where it is assumed that only upper and lower bounds are known for each cost coefficient. It is required to find a minmax regret assignment. The problem is known to be strongly NP-hard. We present and compare computationally several exact and heuristic methods, including Benders decomposition, using CPLEX, a variable depth neighborhood local search, and two hybrid population-based heuristics. We report results of extensive computational experiments.     

改进人工蜂群算法求解信道分配问题

为求解频率分配问题提出一种改进人工蜂群算法。该算法保持人工蜂群算法原有搜索流程,引入蝙蝠算法回声定位的机制,令蜜蜂拥有蝙蝠的能力,在搜索过程中调节响度和频率逐渐接近目标,以提高频率分配过程中的局部搜索精度和效率。算法利用自然选择阈值来降低搜索过程中对当前全局最优解的依赖,以提高种群多样性,降低陷入局部最优解的可能性。经固定频率分配问题的仿真实验和与其他算法对比结果表明,本文算法不仅具有较快的全局收敛速度,而且有高质量的解和高的效率。     

文本相似度计算在主观题评分中的应用

针对传统主观题自动评分准确度低的问题,提出一种基于文本相似度计算的主观题评分方法。利用扩展的《同义词词林》计算词语之间的相似度,根据标准答案中的词语和学生答卷中的词语以及词语之间的相似度构造二部图,通过二部图的最大匹配算法获得标准答案和学生答案的相似度。实验结果表明,该方法可以给主观题评分提供一个较好的参考。     

Optimal matching problem in detection and recognition performance evaluation

This paper proposes a principle of one-to-one correspondence in performance evaluation of a general class of detection and recognition algorithms. Such a correspondence between ground-truth entities and algorithm declared entities is essential in accurately computing objective performance measures such as the detection, recognition, and false alarm rates. We mathematically define the correspondence by formulating a combinatorial optimal matching problem. In addition to evaluating detection performance, this methodology is also capable of evaluating recognition performance. Our study shows that the proposed principle for detection performance evaluation is simple, general and mathematically sound. The derived performance evaluation technique is widely applicable, precise, consistent and efficient.     

优化蚁群算法在排课中的应用策略

针对高校排课面临的问题和挑战,通过分析排课问题的约束条件,将解决排课问题转化为二分图匹配的问题,并给出优化蚁群算法方案,探索高校排课问题的优化策略。     

On the complexity of short-term production planning and the near-optimality of a sequential assignment problem heuristic approach

In semiconductor manufacturing, the process of short-term production planning requires setting clear and yet challenging and doable goals to each operation and toolset in the process flow per each product type. We demonstrate the complexity of this problem using an experimental study performed with proficient workforce, and then show how the problem can be decomposed, aggregated, and solved using sequential recurrent linear programming assignment problems. We also refer to the improvements that the proposed algorithm has achieved in practice when applied to multiple semiconductor production facilities, and discuss its efficiency and uniqueness as a fast heuristic relative to other proposed methods.     

Computing near-optimal solutions for the dominating subset with minimal weight problem

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.     

A dynamic programming algorithm for tree-like weighted set packing problem

In hierarchical organizations, hierarchical structures naturally correspond to nested sets. That is, we have a collection of sets such that for any two sets, either one of them is a subset of the other, or they are disjoint. In other words, a nested set system forms a hierarchy in the form of a tree structure. The task assignment problem on such hierarchical organizations is a real life problem. In this paper, we introduce the tree-like weighted set packing problem, which is a weighted set packing problem restricted to sets forming tree-like hierarchical structure. We propose a dynamic programming algorithm with cubic time complexity.     

A stochastic neighborhood search approach for airport gate assignment problem

An appropriate and efficient gate assignment is of great importance in airports since it plays a major role in the revenue obtained from the airport operations. In this study, we have focused mainly on maximum gate employment, or in other words minimize the total duration of un-gated flights. Here, we propose a method that combines the benefits of heuristic approaches with some stochastic approach instead of using a purely probabilistic approach to top-down solution of the problem. The heuristic approaches are usually used in order to provide a fast solution of the problem and later stochastic searches are used in order to ameliorate the previous results of the heuristic approach whenever possible. The proposed method generates an assignment order for the whole planes that corresponds to assignment priority. The ordering process is followed by the allocation step. Since, in practice, each airport has its own physical architecture, there have been arisen many constraints mainly concerning airplane types and parking lots in this step. Sequentially handling the plane ordering and allocation phases provides us great modularity in handling the constraints. The effectiveness of the proposed methodology has been tried to be illustrated firstly on fictively generated flight schedule data and secondly on the real world data obtained from a real world application developed for ?stanbul Atatürk Airport.     

On a pair of job-machine assignment problems with two stages

We consider two assignment problems in which a number of jobs are assigned to the same number of machines that operate in parallel, but in two stages. They are known as the ‘2-stage time minimizing assignment problem’ and the ‘bi-level time minimizing assignment problem’. These problems have the following characteristics in common:

• Each of the machines processes one job (non-preemptively, without help of other machines).

• The job-machine assignments are partitioned into two successive stages of parallel processing.

• The objective is to minimize the makespan, the sum of the primary and the secondary completion time.

Both problems can be solved by (a series of) assignment problems. We improve the related computational complexities by applying reoptimization. Under some conditions a quadratic complexity is derived.We introduce a parameter weighing the relative importance of the primary and the secondary cost per time unit. The parametric problems can be solved, for all parameter values simultaneously, within the same reduced time complexity bounds.

Scope and purpose

As it is often important to solve problems quickly, it is essential to reduce the computational complexity of available algorithms, as far as possible. We consider two problems which arise when parallel scheduling is done in two successive stages; they can be tackled by solving a series of linear assignment problems. We show that they can be solved more efficiently, using properties of the classical linear assignment problem.In practice, the cost per time unit in the two stages need not be equal. A parameter controlling the ratio between these costs defines a parametric version of each problem. The algorithms of reduced time complexity can be extended to these parametric problem versions.     

Colony location algorithm for assignment problems

A novel algorithm called Colony Location Algoritban (CLA) is proposed. It mimics the phenomena in biotic community that colonies of species could be located in the places most suitable to their growth. The factors working on the species location such as the nutrient of soil, resource competition between species, growth and decline process, and effect on environment were considered in CLA via the nutrient function, growth and decline rates, environment evaluation and fertilization strategy. CLA was applied to solve the classical assignment problems. The computation results show that CLA can achieve the optimal solution with higher possibility and shorter running time.