检索结果-内蒙古大学图书馆

assignment problem for system with precedence relationships among elements

ELECTRICAL ENGINEERING IN JAPAN 1997年第2期121卷 54-62页

作者： Kaji, T Ohuchi, A Otaru Univ Commerce Otaru Hokkaido Japan Hokkaido Univ Sapporo Hokkaido 060 Japan

We have studied the problem of assign elements to an ordered sequence of stations such that the precedence relations are satisfied. At this time, we can obtain the best evaluation value decided under certain constrained conditions to the assignment. This kind of problem includes the line balancing problem. In addition, this can be adjusted to various problems by changing the constrained condition and objective function. These problems can be shown as a sequential partitions of the nodes of a directed acyclic graph into subsets. We especially consider the problem of finding a minimum total cost of the cut edge under the restriction of the size of block. In this paper, we propose the general framework for sequential partitions of directed acyclic graphs. We also describe an efficient algorithm that can be used to reduce computational requirements and, possibly, storage. We estimate that the complexity of the algorithm is the polynomial order, if the structure of directed acyclic graphs is near parallel. (C) 1997 Scripta Technica, Inc.

关键词： assignment problem sequential partition dynamic programming directed acyclic graph precedence relationship

来源：评论

学校读者我要写书评

暂无评论

assignment problem with conflicts

引用

COMPUTERS & OPERATIONS RESEARCH 2019年 111卷 214-229页

作者： Oncan, Temel Suyak, Zeynep Akyuz, M. Hakan Altinel, I. Kuban Galatasaray Univ Ind Engn Dept TR-34357 Istanbul Turkey Bogazici Univ Ind Engn Dept TR-34342 Istanbul Turkey

We focus on an extension of the assignment problem with additional conflict (pair) constraints in conjunction with the assignment constraints and binary restrictions. Given a bipartite graph with a cost associated with each edge and a conflict set of edge pairs, the assignment problem with conflict constraints corresponds to finding a minimum weight perfect matching without any conflicting edge pair. For example, some chemicals cannot be processed on close processors, food and toxic products cannot be stored neighboring locations at the same storage area, and machines cannot be sent to process jobs without satisfying some spatial constraints. Unlike the well-known assignment problem, this problem is NP-hard. We first introduce a realistic special class and demonstrate its polynomial solvability. Then, we propose a Branch-and-Bound algorithm and a Russian Doll Search algorithm using the assignment problem relaxations for lower bound computations, and introduce combinatorial branching rules based on the conflicting edges in an optimal solution of the relaxations. According to the extensive computational experiments we can say that the proposed algorithms are very efficient. (C) 2019 Elsevier Ltd. All rights reserved.

关键词： assignment problem Integer programming Branch-and-bound Conflicts

来源：评论

学校读者我要写书评

暂无评论

Troubleshooting algorithm for solving assignment problem and its applications

引用

Journal of Systems Engineering and Electronics 2013年第1期24卷 165-172页

作者： Li Zhou Hailin Zou Yancun Yang Qian Gao School of Information and Electrical Engineering Ludong University

A new troubleshooting algorithm for solving assignment problem based on existing algorithms is proposed, and an analysis on the related theory is given. By applying the new troubleshooting algorithm to the Lagrange relaxation algorithm of the multi-dimensional assignment problem of data association for multi-passive-sensor multi-target location systems, and comparing the simulation results with that of the Hungarian algorithm which is the classical optimal solving algorithm, and the multi-layer ordersearching algorithm which is a sub-optimal solving algorithm, the performance and applying conditions of the new algorithm are summarized. Theory analysis and simulation results prove the effectiveness and superiority of the new algorithm.

关键词： assignment problem troubleshooting algorithm data association.

来源：评论

学校读者我要写书评

暂无评论

assignment problem with Preference and an Efficient Solution Method Without Dissatisfaction 10th

Assignment Problem with Preference and an Efficient Solution...

引用

10th KES Conference on Agent and Multi-Agent Systems - Technologies and Applications (KES-AMSTA)

作者： Saito, Kengo Sugawara, Toshiharu Waseda Univ Dept Comp Sci Tokyo 1698555 Japan

ISBN: (纸本)9783319398839;9783319398822

We formulate an assignment problem-solving framework called single-object resource allocation with preferential order (SORA/PO) to incorporate values of resources and individual preferences into assignment problems. We then devise methods to find semi-optimal solutions for SORA/PO problems. The assignment, or resource allocation, problem is a fundamental problem-solving framework used in a variety of recent network and distributed applications. However, it is a combinatorial problem and has a high computational cost to find the optimal solution. Furthermore, SORA/PO problems require solutions in which participating agents express no or few dissatisfactions on the basis of the relationship between relative values and the agents' preference orders. The algorithms described herein can efficiently find a semi-optimal solution that is satisfactory to almost all agents even though its sum of values is close to that of the optimal solution. We experimentally evaluate our methods and the derived solutions by comparing them with tho optimal solutions calculated by CPLEX. We also compare the running times for the solution obtained by these methods.

关键词： Resource allocation problem assignment problem Preference Cardinal and ordinal values

来源：评论

学校读者我要写书评

暂无评论

assignment problem Based on Improved Ant Colony Algorithm

Assignment Problem Based on Improved Ant Colony Algorithm

引用

International Conference on Recent Trends in Materials and Mechanical Engineering (ICRTMME 2011)

作者： Geo, Zhi'e Zhang, Gongjing Qingdao Univ Coll Informat & Engn Qingdao 266071 Peoples R China

ISBN: (纸本)9783037850992

assignment problem is a combinatorial optimization problem. In this paper,a improved ant colony algorithm is proposed to solve the assignment problem. According to the rule of state-shift and strategty of updating pheromone, parameters of the ant colony Algorithm are optimized and changed,the best solution can be found rapidly,the simulative results show that the improvement strategies can well improve convergence speed and quality.

关键词： assignment problem ant colony algorithm optimize parameters dynamic change

来源：评论

学校读者我要写书评

暂无评论

A set of greedy randomized Adaptive Local Search Procedure (GRASP) implementations for the multidimensional assignment problem

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2001年第2期19卷 145-164页

作者： Robertson, AJ TRW Co Inc Aurora CO 80011 USA

The focal problem for centralized multisensor multitarget tracking is the data association problem of partitioning the observations into tracks and false alarms so that an accurate estimate of the true tracks can be recovered. Large classes of these association problems can be formulated as multidimensional assignment problems, which are known to be NP-hard for three dimensions or more. The assignment problems that result from tracking are large scale, sparse and noisy. Solution methods must execute in real-time. The Greedy Randomized Adaptive Local Search Procedure (GRASP) has proven highly effective for solving many classes NP-hard optimization problems. This paper introduces four GRASP implementations for the multidimensional assignment problem, which are combinations of two constructive methods (randomized reduced cost greedy and randomized max regret) and two local search methods (two-assignment-exchange and variable depth exchange). Numerical results are shown for a two random problem classes and one tracking problem class.

关键词： GRASP assignment problem discrete optimization NP-Complete

来源：评论

学校读者我要写书评

暂无评论

An almost robust optimization model for integrated berth allocation and quay crane assignment problem

引用

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE 2021年 104卷 102455-102455页

作者： Xiang, Xi Liu, Changchun Beijing Jiaotong Univ Sch Econ & Management Beijing Peoples R China Natl Univ Singapore Ctr Excellence Modeling & Simulat Next Generat Lo Singapore 117602 Singapore Natl Univ Singapore Dept Ind Syst Engn & Management Singapore 117602 Singapore Natl Univ Singapore Inst Operat Res & Analyt Singapore 117602 Singapore

The integrated berth allocation and quay crane assignment problem is an important issue for the operations management in container terminals. This issue primarily considers the assignment of berthing time, position, and the number of quay cranes in each time segment to ships that must be discharged and loaded at terminals. This study examines such a problem by considering uncertainties in the late arrival of ships and inflation of container quantity. Based on historical data, we first divide the uncertainty set into Knon-overlapping full-dimensional clusters via K-means clustering, and the weight of each cluster is calculated. Then, we formulate an almost robust model by introducing the weighted max penalty function with the objective of minimizing the total cost, which is caused by the deviations from the expected berthing location and departure time. The concept of robustness index is introduced to investigate the trade-offbetween the changes in the objective value and the penalty violation. A decomposition method, which contains a deterministic master problem and a stochastic subproblem, is proposed to solve the problem. In each iteration, the subproblem checks the master problem under different realizations, adds scenarios, and cuts into the master problem if needed. Numerical experiments demonstrate that (i) the proposed method can solve the model efficiently, (ii) the robustness index shows that a significant improvement in objective can be achieved at the expense of a small amount of penalty, (iii) the proposed model can handle uncertainties better than the deterministic, fully robust, and worst-case models in terms of total expected cost, total vessel delays, and utilization rates of the berth and quay crane, and (iv) the proposed method becomes more attractive compared with the first come first served approach as the congestion situation or uncertainty degree increase. (C) 2021 Elsevier Ltd. All rights reserved.

关键词： Integrated berth allocation and quay crane assignment problem Almost robust optimization Decomposition method

来源：评论

学校读者我要写书评

暂无评论

COMPETITIVE NEURAL ARCHITECTURE FOR HARDWARE SOLUTION TO THE assignment problem

引用

NEURAL NETWORKS 1991年第4期4卷 431-442页

作者： EBERHARDT, SP DAUD, T KERNS, DA BROWN, TX THAKOOR, AP CALTECH JET PROP LABCTR SPACE MICROELECTR TECHNOLPASADENACA 91109

A neural network architecture for competitive assignment is presented, with details of a very large scale integration (VLSI) design and characterization of critical circuits fabricated in complementary metal-oxide semiconductor (CMOS). The assignment problem requires that elements of two sets (e.g., resources and consumers) be associated with each other such as to minimize the total cost of the associations. Unlike previous neural implementations, association costs are applied locally to processing units (PUs, i.e., neurons), reducing connectivity to VLSI-compatible O(number of PUs). Also, each element in either set may be independently programmed to associate with one, several, or a range of elements of the other set. A novel method of "hysteretic annealing," effected by gradually increasing positive feedback within each PU, was developed and compared in simulations to mean-field annealing implemented by increasing PU gain over time. The simulations (to size 64 x 64) consistently found optimal or near-optimal solutions, with settling times of about 150 microseconds, except for a few variable-gain annealing trials that exhibited oscillation.

关键词： assignment problem NEURAL NETWORK COMPETITION NEUROPROCESSOR HYSTERESIS ANNEALING VLSI

来源：评论

学校读者我要写书评

暂无评论

Solving the minsum product rate variation problem as an assignment problem

引用

INTERNATIONAL JOURNAL OF FLEXIBLE MANUFACTURING SYSTEMS 2006年第4期18卷 269-284页

作者： Moreno, Natalia Corominas, Albert Univ Politecn Cataluna Dept Business Tossa De Mar 17320 Gerona Spain Inst Ind & Control Engn Barcelona 08028 Spain

In this paper, we consider the Minimum Product Rate Variation problem (PRVP), which consists in sequencing parts of different types so that the sum of discrepancy functions between actual and ideal productions is minimal. Such a problem can be reduced to an assignment problem (AP) with a matrix of a special structure. Following this approach, the efficiency of different algorithms for an AP applied to the minsum PRVP case was compared. As a result, a new algorithm that exploits specific PRVP matrix properties is presented. Computational experiments are presented, including both types of objective functions, symmetric, as described in the literature, and asymmetric. The proposed approach allows, for the first time, obtaining optimal solutions for instances of dimensions up to 10,000 parts of different types to be produced.

关键词： assignment problem just-in-time mixed-model assembly lines product rate variation problem

来源：评论

学校读者我要写书评

暂无评论

Complexity analysis of an assignment problem with controllable assignment costs and its applications in scheduling

引用

DISCRETE APPLIED MATHEMATICS 2011年第12期159卷 1264-1278页

作者： Yedidsion, Liron Shabtay, Dvir Kaspi, Moshe Ben Gurion Univ Negev Beer Sheva Dept Ind Engn & Management Beer Sheva Israel Technion Israel Inst Technol Fac Ind Engn & Management IL-32000 Haifa Israel

We extend the classical linear assignment problem to the case where the cost of assigning agent j to task i is a multiplication of task i's cost parameter by a cost function of agent j. The cost function of agent j 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 NP-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. (C) 2011 Elsevier B.V. All rights reserved.

关键词： assignment problem Scheduling Controllable processing times Complexity Resource allocation Bicriteria optimization

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：