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

Combined planning and scheduling in a divergent production system with co-production: A case study in the lumber industry

引用

COMPUTERS & OPERATIONS RESEARCH 2011年第9期38卷 1238-1250页

作者： Gaudreault, Jonathan Frayret, Jean-Marc Rousseau, Alain D'Amours, Sophie Univ Laval FORAC Res Consortium Quebec City PQ G1K 7P4 Canada

Many research initiatives carried out in production management consider process planning and operations scheduling as two separate and sequential functions. However, in certain contexts, the two functions must be better integrated. This is the case in divergent production systems with co-production (i.e. production of different products at the same time from a single product input) when alternative production processes are available. This paper studies such a context and focuses on the case of drying and finishing operations in a softwood lumber facility. The situation is addressed using a single model that simultaneously performs process planning and scheduling. We evaluate two alternative formulations. The first one is based on mixed integer programming (MIP) and the second on constraint programming (CP). We also propose a search procedure to improve the performance of the CP approach. Both approaches are compared with respect to their capacity to generate good solutions in short computation time. (C) 2010 Elsevier Ltd. All rights reserved.

关键词： Integrated planning and scheduling Mathematical programming Constraint programming Wood drying and finishing anytime algorithm Lumber industry

来源：评论

学校读者我要写书评

暂无评论

Progressive accommodation of parametric faults in linear quadratic control

引用

AUTOMATICA 2007年第12期43卷 2070-2076页

作者： Staroswiecki, Marcel Yang, Hao Jiang, Bin Univ Paris Sud CNRS ENS USTLSATIE F-94235 Cachan France Nanjing Univ Aeronaut & Astronaut Coll Automat Engn Nanjing 210016 Peoples R China

In this paper, a strategy based on the linear quadratic design, which progressively accommodates the feedback control law, is proposed. It significantly reduces the loss of performance that results from the time delay needed by fault accommodation algorithms to provide a solution. An aircraft example is given to illustrate the efficiency of progressive accommodation. (c) 2007 Elsevier Ltd. All rights reserved.

关键词： fault tolerant control linear quadratic control anytime algorithm progressive accommodation

来源：评论

学校读者我要写书评

暂无评论

Some special heuristics for discrete optimization problems

Some special heuristics for discrete optimization problems

引用

8th International Conference on Enterprise Information Systems (ICEIS 2006)

作者： Melnikov, Boris Radionov, Alexey Gumayunov, Viktor Togliatti State Univ Dept Math & Informat Sci Tolyatti 445667 Russia

ISBN: (纸本)9728865422

In previous paper we considered some heuristic methods of decision-making for various discrete optimization problems;all these heuristics should be considered as the combination of them and form a common multi-heuristic approach to the various problems. And in this paper, we begin to consider local heuristics, which are different for different problems. At first, we consider two problems of minimization: for nondeterministic finite automata and for disjunctive normal forms. Our approach can be considered as an alternative to the methods of linear programming, multi-agent optimization, and neuronets.

关键词： anytime algorithm discrete optimization problem local heuristics minimization nondeterministic finite automata disjunctive normal forms

来源：评论

学校读者我要写书评

暂无评论

CABOB: A fast, optimal algorithm for winner determination in combinatorial auctions

引用

MANAGEMENT SCIENCE 2005年第3期51卷 374-390页

作者： Sandholm, T Suri, S Gilpin, A Levine, D Carnegie Mellon Univ Dept Comp Sci Pittsburgh PA 15213 USA Univ Calif Santa Barbara Dept Comp Sci Santa Barbara CA 93106 USA CombineNet Inc Pittsburgh PA 15222 USA

Combinatorial auctions where bidders can bid on bundles of items' can lead to more economically efficient allocations, but determining the winners is NP-complete and inapproximable. We present CABOB, a sophisticated optimal search algorithm for the problem. It uses decomposition techniques, upper and lower, bounding (also across components), elaborate and dynamically chosen bid-ordering heuristics, and a host of structural observations. CABOB attempts to capture structure in any instance. without making assumptions about the instance distribution. Experiments against the fastest prior algorithm, CPLEX 8.0, show that CABOB is often faster, seldom drastically slower, and in many cases drastically faster-especially in cases with structure. CABOB's search runs in linear space and has significantly better anytime performance than CPLEX We also uncover interesting aspects of the problem itself. First, problems with short bids, which were hard for the first generation of specialized algorithms, are easy. Second, almost all of the CATS distributions are easy, and the run time is virtually unaffected by the number of goods. Third, we test several random restart strategies, showing that they do not help on this problem-the run-time distribution does not have a heavy tail.

关键词： auction combinatorial auction winner determination winner-determination algorithm search branch and bound MIP anytime algorithm branching heuristics dynamically chosen heuristic bounding across components random restart

来源：评论

学校读者我要写书评

暂无评论

Bargaining with limited computation: Deliberation equilibrium

引用

ARTIFICIAL INTELLIGENCE 2001年第2期132卷 183-217页

作者： Larson, K Sandholm, T Carnegie Mellon Univ Dept Comp Sci Pittsburgh PA 15213 USA

We develop a normative theory of interaction-negotiation in particular-among self-interested computationally limited agents where computational actions are game theoretically treated as part of an agent's strategy. We focus on a 2-agent setting where each agent has an intractable individual problem, and there is a potential gain from pooling the problems, giving rise to an intractable joint problem. At any time, an agent can compute to improve its solution to its own problem, its opponent's problem, or the joint problem. At a deadline the agents then decide whether to implement the joint solution, and if so, how to divide its value (or cost). We present a fully normative model for controlling anytime algorithms where each agent has statistical performance profiles which are optimally conditioned on the problem instance as well as on the path of results of the algorithm run so far. Using this model, we introduce a solution concept, which we call deliberation equilibrium. It is the perfect Bayesian equilibrium of the game where deliberation actions are part of each agent's strategy. The equilibria differ based on whether the performance profiles are deterministic or stochastic, whether the deadline is known or not, and whether the proposer is known in advance or not. We present algorithms for finding the equilibria. Finally, we show that there exist instances of the deliberation-bargaining problem where no pure strategy equilibria exist and also instances where the unique equilibrium outcome is not Pareto efficient. (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： automated negotiation multiagent systems game theory resource-bounded reasoning bounded rationality bargaining anytime algorithm

来源：评论

学校读者我要写书评

暂无评论

A complete anytime algorithm for number partitioning

引用

ARTIFICIAL INTELLIGENCE 1998年第2期106卷 181-203页

作者： Korf, RE Univ Calif Los Angeles Dept Comp Sci Los Angeles CA 90095 USA

Given a set of numbers, the two-way number partitioning problem is to divide them into two subsets, so that the sum of the numbers in each subset are as nearly equal as possible. The problem is NP-complete. Based on a polynomial-time heuristic due to Karmarkar and Karp, we present a new algorithm, called Complete Karmarkar-Karp (CKK), that optimally solves the general number-partitioning problem, and significantly outperforms the best previously-known algorithms for large problem instances. For numbers with twelve significant digits or less, CKK can optimally solve two-way partitioning problems of arbitrary size in practice. For numbers with greater precision, CKK first returns the Karmarkar-Karp solution, then continues to find better solutions as time allows. Over seven orders of magnitude improvement in solution quality is obtained in less than an hour of running time. Rather than building a single solution one element at a time, or modifying a complete solution, CKK constructs subsolutions, and combines them together in all possible ways. This approach may be effective for other NP-hard problems as well. (C) 1998 Elsevier Science B.V. All rights reserved.

关键词： number partitioning anytime algorithm NP-complete

来源：评论

学校读者我要写书评

暂无评论

Agents in electronic commerce: Component technologies for automated negotiation and coalition formation

引用

AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS 2000年第1期3卷 73-96页

作者： Sandholm, T Washington Univ Dept Comp Sci St Louis MO 63130 USA

Automated negotiation and coalition formation among self-interested agents are playing an increasingly important role in electronic commerce. Such agents cannot be coordinated by externally imposing their strategies. Instead the interaction protocols have to be designed so that each agent is motivated to follow the strategy that the protocol designer wants it to follow. This paper reviews six component technologies that we have developed for making such interactions less manipulable and more efficient in terms of the computational processes and the outcomes: 1. OCSM-contracts in marginal cost based contracting, 2. leveled commitment contracts, 3. anytime coalition structure generation with worst case guarantees, 4. trading off computation cost against optimization quality within each coalition, 5. distributing search among insincere agents, and 6. unenforced contract execution. Each of these technologies represents a different way of battling self-interest and combinatorial complexity simultaneously. This is a key battle when multi-agent systems move into large-scale open settings.

关键词： multiagent systems electronic commerce negotiation contracting coalition formation game theory anytime algorithm resource-bounded reasoning

来源：评论

学校读者我要写书评

暂无评论

Agents in electronic commerce: Component technologies for automated negotiation and coalition formation

Agents in electronic commerce: Component technologies for au...

引用

3rd International Conference on Multi-Agent Systems (ICMAS'98)

作者： Sandholm, T Washington Univ Dept Comp Sci St Louis MO 63130 USA

ISBN: (纸本)081868500X

关键词： multiagent systems electronic commerce negotiation contracting coalition formation game theory anytime algorithm resource-bounded reasoning

来源：评论

学校读者我要写书评

暂无评论

Coalition structure generation with worst case guarantees

引用

ARTIFICIAL INTELLIGENCE 1999年第1-2期111卷 209-238页

作者： Sandholm, T Larson, K Andersson, M Shehory, O Tohmé, F Washington Univ Dept Comp Sci St Louis MO 63130 USA Carnegie Mellon Univ Inst Robot Pittsburgh PA 15213 USA

Coalition formation is a key topic in multiagent systems. One may prefer a coalition structure that maximizes the sum of the values of the coalitions, but often the number of coalition structures is too large to allow exhaustive search for the optimal one. Furthermore, finding the optimal coalition structure is NP-complete. But then, can the coalition structure found via a partial search be guaranteed to be within a bound from optimum? We show that none of the previous coalition structure generation algorithms can establish any bound because they search fewer nodes than a threshold that we show necessary for establishing a bound. We present an algorithm that establishes a tight bound within this minimal amount of search, and show that any other algorithm would have to search strictly more. The fraction of nodes needed to be searched approaches zero as the number of agents grows. If additional time remains, our anytime algorithm searches further, and establishes a progressively lower tight bound. Surprisingly, just searching one more node drops the bound in half. As desired, our algorithm lowers the bound rapidly early on, and exhibits diminishing returns to computation. It also significantly outperforms its obvious contenders. Finally, we show how to distribute the desired search across self-interested manipulative agents. (C) 1999 Elsevier Science B.V. All rights reserved.

关键词： coalition formation anytime algorithm multiagent systems game theory negotiation distributed AI resource-bounded reasoning

来源：评论

学校读者我要写书评

暂无评论

Learning while solving problems in best first search

引用

IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART A-SYSTEMS AND HUMANS 1998年第4期28卷 535-542页

作者： Sarkar, S Chakrabarti, PP Ghose, S Indian Inst Technol Dept Comp Sci & Engn Guwahati 781001 India Indian Inst Technol Dept Comp Sci & Engn Kharagpur 721302 W Bengal India

We investigate the role of learning in search-based systems for solving optimization problems. Many AI problem solving systems solve problems repeatedly from the same domain. If the problems come from the same distribution in the learning phase and the problem solving phase, the problem solver can acquire information while solving problems, which can be used to solve subsequent problems faster. We use a learning model, where the values of a set of features can be used to induce a clustering of the problem state space. The feasible set of h* values corresponding to each cluster is called h*set. If we relax the optimality guarantee, and tolerate a risk factor, the distribution of h*set can be used to expedite search and produce results within a given risk of suboptimality. The offline learning method consists of solving a batch of problems by using A* to learn the distribution of the h*set in the learning phase. This distribution can be used to solve the-rest of the problems effectively. We show how the knowledge acquisition phase can be integrated with the problem solving phase. We present a continuous on-line learning scheme that uses an "anytime" algorithm to learn continuously while solving problems. The system starts with initial assumed distributions of h*set which are used to solve the initial problems. The results are used to update the distributions continuously and with time the distributions converge.

关键词： anytime algorithm best first search continuous learning heuristic features learning problem solving

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：