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

Grand challenges for constraint programming

constraintS 2014年第2期19卷 150-162页

作者： Freuder, Eugene C. O'Sullivan, Barry Univ Coll Cork Dept Comp Sci Cork Constraint Computat Ctr Cork Ireland

Every field should have its Grand Challenges. After discussing some general "why and how" issues, with brief reference to some sample challenges, we devote attention to the challenges raised by the new world of "BigData" and to some new ways of approaching the classic Grand Challenge of the Holy Grail (where one merely states the problem and the computer solves it). There can, of course, never be a definitive catalogue of Grand Challenges. The ultimate Grand Challenge is for everyone working on constraint programming to look up on occasion from their everyday pursuits to consider how they might contribute to a Grand Challenge, and even to try their hand at formulating their own Grand Challenges.

关键词： Grand challenges in constraint programming constraint programming Big data

来源：评论

学校读者我要写书评

暂无评论

Problem Specific Variable Selection Rules for constraint programming: A Type II Mixed Model Assembly Line Balancing Problem Case

引用

APPLIED ARTIFICIAL INTELLIGENCE 2020年第7期34卷 564-584页

作者： Alakas, Haci Mehmet Toklu, Bilal Kirikkale Univ Fac Engn Dept Ind Engn Ankara Yolu 7 Km TR-71451 Kirikkale Turkey Gazi Univ Fac Engn Dept Ind Engn Ankara Turkey

ABSRACT The main idea of constraint programming (CP) is to determine a solution (or solutions) of a problem assigning values to decision variables satisfying all constraints. Two sub processes, an enumeration strategy and a consistency, run under the constraint programming main algorithm. The enumeration strategy which is managing the order of variables and values to build a search tree and possible solutions is crucial process in CP. In this study problem-based specific variable selection rules are studied on a mixed model assembly line balancing problem. The 18 variable selection rules are generated in three main categories by considering the problem input parameters. These rules are tested with benchmark problems in the literature and experimental results are compared with the results of mathematical model and standard CP algorithm. Also, benchmark problems are run with two CP rules to compare experimental results. In conclusion, experimental results are shown that the outperform rules are listed and also their specifications are defined to guide to researchers who solve optimization problems with CP.

关键词： constraint programming Feature selection Program

来源：评论

学校读者我要写书评

暂无评论

Implementing logical connectives in constraint programming

引用

ARTIFICIAL INTELLIGENCE 2010年第16-17期174卷 1407-1429页

作者： Jefferson, Christopher Moore, Neil C. A. Nightingale, Peter Petrie, Karen E. Univ St Andrews Sch Comp Sci St Andrews KY16 9SX Fife Scotland Univ Dundee Sch Comp Dundee DD1 4HN Scotland

Combining constraints using logical connectives such as disjunction is ubiquitous in constraint programming, because it adds considerable expressive power to a constraint language. We explore the solver architecture needed to propagate such combinations of constraints efficiently. In particular we describe two new features named satisfying sets and constraint trees. We also make use of movable triggers (Gent et al., 2006) [1], and with these three complementary features we are able to make considerable efficiency gains. A key reason for the success of Boolean Satisfiability (SAT) solvers is their ability to propagate OR constraints efficiently, making use of movable triggers. We successfully generalise this approach to an OR of an arbitrary set of constraints, maintaining the crucial property that at most two constraints are active at any time, and no computation at all is done on the others. We also give an AND propagator within our framework, which may be embedded within the OR. Using this approach, we demonstrate speedups of over 10,000 times in some cases, compared to traditional constraint programming approaches. We also prove that the OR algorithm enforces generalised arc consistency (GAC) when all its child constraints have a GAC propagator, and no variables are shared between children. By extending the OR propagator, we present a propagator for ATLEASTK, which expresses that at least k of its child constraints are satisfied in any solution. Some logical expressions (e.g. exclusive-or) cannot be compactly expressed using AND, OR and ATLEASTK. Therefore we investigate reification of constraints. We present a fast generic algorithm for reification using satisfying sets and movable triggers. (C) 2010 Published by Elsevier B.V.

关键词： constraint programming constraint satisfaction problems Propagation algorithms Logical connectives

来源：评论

学校读者我要写书评

暂无评论

Cell formation in group technology using constraint programming and Boolean satisfiability

引用

EXPERT SYSTEMS WITH APPLICATIONS 2012年第13期39卷 11423-11427页

作者： Soto, Ricardo Kjellerstrand, Hakan Duran, Orlando Crawford, Broderick Monfroy, Eric Paredes, Fernando Pontificia Univ Catolica Valparaiso Valparaiso Chile Univ Autonoma Chile Santiago Chile Univ Tecn Federico Santa Maria Santiago Chile Univ Diego Portales Escuela Ingn Ind Santiago Chile

Cell formation consists in organizing a plant as a set of cells, each of them containing machines that process similar types or families of parts. The idea is to minimize the part flow among cells in order to reduce costs and increase productivity. The literature presents different approaches devoted to solve this problem, which are mainly based on mathematical programming and on evolutionary computing. Mathematical programming can guarantee a global optimal solution, however at a higher computational cost than an evolutionary algorithm, which can assure a good enough optimum in a fixed amount of time. In this paper, we model and solve this problem by using state-of-the-art constraint programming (CP) techniques and Boolean satisfiability (SAT) technology. We present different experimental results that demonstrate the efficiency of the proposed optimization models. Indeed, CP and SAT implementations are able to reach the global optima in all tested instances and in competitive runtime. (c) 2012 Elsevier Ltd. All rights reserved.

关键词： Manufacturing cells Machine grouping constraint programming Boolean satisfiability

来源：评论

学校读者我要写书评

暂无评论

Investigating constraint programming and hybrid methods for real world industrial test laboratory scheduling

引用

JOURNAL OF SCHEDULING 2024年第6期27卷 607-622页

作者： Geibinger, Tobias Mischek, Florian Musliu, Nysret TU Wien Christian Doppler Lab Artificial Intelligence & Op Databases & Artificial Intelligence Grp Favoritenstr 9-11 A-1040 Vienna Austria

In this paper we deal with a complex real world scheduling problem closely related to the well-known Resource-Constrained Project Scheduling Problem (RCPSP). The problem concerns industrial test laboratories in which a large number of tests are performed by qualified personnel using specialised equipment, while respecting deadlines and other constraints. We present different constraint programming models and search strategies for this problem. Furthermore, we propose a Very Large Neighborhood Search approach based on our CP methods. Our models are evaluated using CP solvers and a MIP solver both on real-world test laboratory data and on a set of generated instances of different sizes based on the real-world data. Further, we compare the exact approaches with VLNS and a Simulated Annealing heuristic. We could find feasible solutions for all instances and several optimal solutions and we show that using VLNS we can improve upon the results of the other approaches.

关键词： RCPSP Resource constrained project scheduling problem Project scheduling constraint programming VLNS Very large neighborhood search

来源：评论

学校读者我要写书评

暂无评论

A constraint programming model for the scheduling and workspace layout design of a dual-arm multi-tool assembly robot

引用

constraintS 2023年第2期28卷 71-104页

作者： Wessen, Johan Carlsson, Mats Schulte, Christian Flener, Pierre Pecora, Federico Matskin, Mihhail ABB Corp Res Vasteras Sweden RISE Res Inst Sweden Uppsala Sweden KTH Royal Inst Technol Stockholm Sweden Uppsala Univ Uppsala Sweden Orebro Univ Orebro Sweden KTH Royal Inst Technol Stockholm Sweden

The generation of a robot program can be seen as a collection of sub-problems, where many combinations of some of these sub-problems are well studied. The performance of a robot program is strongly conditioned by the location of the tasks. However, the scope of previous methods does not include workspace layout design, likely missing high-quality solutions. In industrial applications, designing robot workspace layout is part of the commissioning. We broaden the scope and show how to model a dual-arm multi-tool robot assembly problem. Our model includes more robot programming sub-problems than previous methods, as well as workspace layout design. We propose a constraint programming formulation in MiniZinc that includes elements from scheduling and routing, extended with variable task locations. We evaluate the model on realistic assembly problems and workspaces, utilizing the dual-arm YuMi robot from ABB Ltd. We also evaluate redundant constraints and various formulations for avoiding arm-to-arm collisions. The best model variant quickly finds high-quality solutions for all problem instances. This demonstrates the potential of our approach as a valuable tool for a robot programmer.

关键词： Assembly manufacturing constraint programming Robot planning and scheduling Workspace layout design

来源：评论

学校读者我要写书评

暂无评论

A constraint programming model with time uncertainty for cooperative flight departures

引用

TRANSPORTATION RESEARCH PART C-EMERGING TECHNOLOGIES 2018年第Nov.期96卷 170-191页

作者： Schefers, Nina Ramos Gonzalez, Juan Jose Folch, Pau Luis Munoz-Gamarra, Jose Univ Autonoma Barcelona Tech Innovat Cluster Aeronaut Management Barcelona Spain Aslogic Dept Res & Innovat Rubi Spain

The lack of a proper integration of strategic Air Traffic Management decision support tools with tactical Air Traffic Control interventions usually generates a negative impact on the Reference Business Trajectory adherence, and in consequence affects the potential of the Trajectory-Based Operations framework. In this paper, a new mechanism relaying on Reference Business Trajectories as a source of data to reduce the amount of Air Traffic Controller interventions at the tactical level while preserving Air Traffic Flow Management planned operations is presented. Artificial Intelligence can enable constraint programming as it is a powerful paradigm for solving complex, combinatorial search problems. The proposed methodology takes advantage of constraint programming and fosters adherence of Airspace User's trajectory preferences by identifying tight interdependencies between trajectories and introducing a new mechanism to improve the aircraft separation at concurrence events considering time uncertainty. The underlying philosophy is to capitalize present degrees of freedom between layered Air Traffic Management planning tools, when sequencing departures at the airports by considering the benefits of small time stamp changes in the assigned Calculated Take-Off Time departures and to enhance Trajectory-Based Operations concepts.

关键词： Air Traffic Management Trajectory Based Operations Decision Support Tool constraint programming Trajectory Prediction Uncertainties Predictive Analysis Conflict Detection and Resolution Artificial Intelligence Data Analysis Air Transportation Planning System-level Simulation Reference Business Trajectories

来源：评论

学校读者我要写书评

暂无评论

A constraint programming model for food processing industry: a case for an ice cream processing facility

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2019年第21期57卷 6648-6664页

作者： Wari, Ezra Zhu, Weihang Lamar Univ Dept Ind Engn Beaumont TX 77710 USA Univ Houston Dept Engn Technol Houston TX 77004 USA

This paper presents a constraint programming (CP) scheduling model for an ice cream processing facility. CP is a mathematical optimisation tool for solving problems either for optimality (for small-size problems) or good quality solutions (for large-size problems). For practical scheduling problems, a single CP solution model can be used to optimise daily production or production horizon extending for months. The proposed model minimises a makespan objective and consists of various processing interval and sequence variables and a number of production constraints for a case from a food processing industry. Its performance was compared to a Mixed Integer Linear programming (MILP) model from the literature for optimality, speed, and competence using the partial capacity of the production facility of the case study. Furthermore, the model was tested using different product demand sizes for the full capacity of the facility. The results demonstrate both the effectiveness, flexibility, and speed of the CP models, especially for large-scale models. As an alternative to MILP, CP models can provide a reasonable balance between optimality and computation speed for large problems.

关键词： constraint programming scheduling ice cream processing food processing scheduling

来源：评论

学校读者我要写书评

暂无评论

What do constraint programming Users Want to See? Exploring the role of Visualisation in Profiling of Models and Search

引用

IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS 2017年第1期23卷 281-290页

作者： Goodwin, Sarah Mears, Christopher Dwyer, Tim de la Banda, Maria Garcia Tack, Guido Wallace, Mark Monash Univ Adapt Visualisat Lab Clayton Vic 3800 Australia Monash Univ Fac Informat Technol Clayton Vic 3800 Australia

constraint programming allows difficult combinatorial problems to be modelled declaratively and solved automatically. Advances in solver technologies over recent years have allowed the successful use of constraint programming in many application areas. However, when a particular solver's search for a solution takes too long, the complexity of the constraint program execution hinders the programmer's ability to profile that search and understand how it relates to their model. Therefore, effective tools to support such profiling and allow users of constraint programming technologies to refine their model or experiment with different search parameters are essential. This paper details the first user-centred design process for visual profiling tools in this domain. We report on: our insights and opportunities identified through an on-line questionnaire and a creativity workshop with domain experts carried out to elicit requirements for analytical and visual profiling techniques;our designs and functional prototypes realising such techniques;and case studies demonstrating how these techniques shed light on the behaviour of the solvers in practice.

关键词： visual analytics user-centred design profiling constraint programming tree visualisations

来源：评论

学校读者我要写书评

暂无评论

A new two-stage constraint programming approach for open shop scheduling problem with machine blocking

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2023年第24期61卷 8560-8579页

作者： Abreu, Levi R. Nagano, Marcelo S. Prata, Bruno A. Univ Sao Paulo Dept Prod Engn Sao Carlos Brazil Univ Fed Ceara Dept Ind Engn Fortaleza Brazil

In this paper, a variant of the open shop scheduling problem is considered in which the intermediate storage is forbidden among two adjacent production stages (zero buffer or machine blocking constraint). The performance measure is to minimise the maximal completion time of the jobs (makespan). Since this is an NP-hard problem, a two-stage constraint programming approach is proposed as a new exact method. Computational experiments were carried out on 222 literature problem instances in order to test the performance of the proposed algorithm. The relative deviation is adopted as the performance criteria. Computational results point to the ability of the proposed method to solve large-sized instances in comparison with the developed mixed-integer linear programming model and a simple constraint programming model, both with user cuts. In all set of instances, the proposed two-stage method performed better than benchmarking methods and integer programming models, with average relative deviation regarding objective values as lower as 12%. In addition, the results point to a competitive efficiency in computational times of the proposed method with less than 200 s in the most instances to obtain the optimal solution, in comparison to competitive metaheuristics from literature of the problem, for the tested test instances.

关键词： Production scheduling constraint programming two-stage zero buffer blocking

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：