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

Improving the Efficiency of Euclidean TSP Solving in constraint programming by Predicting Effective Nocrossing constraints 1

引用

19th International Conference of the Italian-Association-for-Artificial-Intelligence (AIxIA)

作者： Bellodi, Elena Bertagnon, Alessandro Gavanelli, Marco Zese, Riccardo Univ Ferrara Dept Engn Via G Saragat 1 I-44122 Ferrara Italy

ISBN: (数字)9783030770914

ISBN: (纸本)9783030770914;9783030770907

The Traveling Salesperson Problem (TSP) is a well-known problem addressed in the literature through various techniques, including Integer Linear programming, constraint programming (CP) and Local Search. Many real life instances belong to the subclass of Euclidean TSPs, in which the nodes to be visited are points in the Euclidean plane, and the distance between them is the Euclidean distance. A well-known property of the Euclidean TSP is that no crossings can exist in an optimal solution. In a previous publication, we exploited this property to speed-up the solution of Euclidean instances in CP, by imposing a quadratic number of so-called no-overlapping constraints. In this work, we observe that not all the no-overlapping constraints are equally useful: by experimental analysis, some of them provide a speed-up, while others only introduce overhead. Thus, it is important to define a way to classify useful constraints. To do so, we use machine learning approaches with the objective to impose only those no-overlapping constraints that have been classified as effective. We compare two classifiers based on Random Forest and Neural Networks, which show to be effective, with a slight prevalence for Random Forest.

关键词： constraint programming Euclidean TSP Supervised machine learning Random forest Neural networks Redundant constraints

来源：评论

学校读者我要写书评

暂无评论

A Computational Study of constraint programming Approaches for Resource-Constrained Project Scheduling with Autonomous Learning Effects 1

引用

18th International Conference on the Integration of constraint programming, Artificial Intelligence, and Operations Research (CPAIOR)

作者： Hill, Alessandro Ticktin, Jordan Vossen, Thomas W. M. Calif Polytech State Univ San Luis Obispo Ind & Mfg Engn San Luis Obispo CA 93407 USA Univ Colorado Leeds Sch Business Boulder CO USA

ISBN: (数字)9783030782306

ISBN: (纸本)9783030782306;9783030782290

It is well-known that experience can lead to increased efficiency, yet this is largely unaccounted for in project scheduling. We consider project scheduling problems where the duration of activities can be reduced when scheduled after certain other activities that allow for learning relevant skills. Since per-period availabilities of renewable resources are limited and precedence requirements have to be respected, the resulting optimization problems generalize the resource-constrained project scheduling problem. We introduce four constraint programming formulations that incorporate the alternative learning-based job durations via logical constraints, dynamic interval lengths, multiple job modes, and a bi-objective reformulation, respectively. To provide tight optimality gaps for larger problem instances, we further develop five lower bounding techniques based on model relaxations. We also devise a destructive lower bounding method. We perform an extensive computational study across thousands of instances based on the PSPlib to quantify the impact of project size, potential learning occurrences, and learning effects on the optimal project duration. In addition, we compare formulation strength and quality of the obtained lower bounds using a state-of-the-art constraint programming solver.

关键词： Resource-constrained project scheduling Autonomous learning constraint programming

来源：评论

学校读者我要写书评

暂无评论

A constraint programming approach and a hybrid of genetic and K-means algorithms to solve the p-hub location-allocation problems

引用

INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE AND ENGINEERING MANAGEMENT 2021年第2期16卷 123-133页

作者： Rabbani, Masoud Mokhtarzadeh, Mahdi Manavizadeh, Neda Univ Tehran Coll Engn Sch Ind Engn Tehran Iran KHATAM Univ Dept Ind Engn Tehran Iran

p-Hub location-allocation problem is one of the most interesting subjects in the location theory. Hubs act as switching points to reduce the transportation cost. In this study, two new solution methods, a constraint programming (CP) based model and a hybrid of k-means and genetic algorithm (KGA), are developed to generate exact and approximate solutions, respectively. The proposed CP formulation is more understandable and straightforward in comparison with the MIP model. The experimental results indicate that the CP model uses the memory of the computer (RAM) more efficiently, which enables us to solve the medium size problems. But, in terms of run time, this method cannot be superior to the MIP model. The CP formulation is also extended for the multi allocation p-hub location problem. K-means algorithm, a well-known algorithm for clustering data, is used to generate initial solutions of GA. Furthermore, a new adaptive crossover operator, which is based on the k-means algorithm, is proposed. The experimental results indicate that the KGA algorithm is superior to the GA, regarding time, objective value, and quality of solution measures.

关键词： constraint programming genetic algorithm K-means algorithm p-hub location-allocation

来源：评论

学校读者我要写书评

暂无评论

Applying constraint programming to the Multi-mode Scheduling Problem in Harvest Logistics 12th

Applying Constraint Programming to the Multi-mode Scheduling...

引用

12th International Conference on Computational Logistics (ICCL)

作者： Bender, Till Wittwer, David Schmidt, Thorsten Tech Univ Dresden Tech Logist D-01062 Dresden Germany

ISBN: (纸本)9783030876722;9783030876715

In this paper, we present a constraint programming (CP) based model for scheduling forage harvesters and transport vehicles during corn harvest. The key aspects are the synchronization of the two resource types and a forage harvester utilization depending on the number of transport vehicles supporting the harvester. The process is modelled as a pre-emptive multi-mode resource-constraint project scheduling problem with fast-tracking, sequence-dependent time lags and synchronization. We use the specialized scheduling features of CP Optimizer for modelling and solving the harvest logistics problem. The results show the suitability of the CP-based approach for modelling the problem in terms of representability of its characteristics. In computational experiments, a solution is found for any of the test instances. Proving optimality, however, is found to be difficult, especially for larger instances. Further variants of the model without pre-emption and fast-tracking and with fewer modes per activity are introduced and tested, showing improvements in computation time and the number of optimal solutions found for the prior variant.

关键词： Harvest logistics constraint programming Resource-constraint project scheduling

来源：评论

学校读者我要写书评

暂无评论

Using constraint programming to address the operational aircraft line maintenance scheduling problem

引用

JOURNAL OF AIR TRANSPORT MANAGEMENT 2024年 115卷

作者： Sciau, Jean -Baptiste Goyon, Agathe Sarazin, Alexandre Bascans, Jeremy Prud'homme, Charles Lorca, Xavier Airbus Protect 36 Rue Grimaud F-31700 Blagnac France IMT Atlantique 4 Rue Alfred Kastler Nantes 44300 France IMT Mines Albi All Sci F-81000 Albi France

Maintenance plays a major role in air transport management. Airlines are looking to reduce aircraft unavailability. Optimizing maintenance is a perspective to increase the operational potential of aircraft and offers novel managerial implications. Maintenance tasks are traditionally organized in periodic blocks of activities. In the modern aviation, more and more maintenance jobs can be performed between two flights, which is called Line Maintenance Scheduling Problem (LMSP). The expected goal of our paper is to propose an operational schedule that can be directly executed by maintainers, i.e. assigning a start time to each elementary activity and a resource to perform it. This new problem is named Operational Aircraft Line Maintenance Scheduling Problem (OALMSP). A scheduling assistant could help airlines to reduce maintenance costs and resource management. Planners have to respect task deadlines imposed by regulations, precedence constraints between certain operations and also ensure the availability of resources in order to perform specific actions. This problem is an extension of a Resource Constrained Project Scheduling Problem (RCPSP). In this article, we propose an industrial application of an automatic aircraft line maintenance scheduler based on a constraint programming (CP) model. The flexibility of our approach means we can easily adapt to airline use cases without changing the properties of the model. The optimization problem is generally made up of several objectives ordered according to their importance. The objectives are respectively to plan as many tasks as possible according to their priority, then to minimize both the use of resources and the deviation time between scheduled dates and target dates of tasks. The lexicographical order enables the use of human reasoning and the management of business priorities. A constructive search strategy is designed to compute a satisfying schedule within an acceptable execution time for industry application. A

关键词： Aircraft line maintenance planning Operational maintenance Optimization scheduling Industrial use case Multi-objective constraint programming

来源：评论

学校读者我要写书评

暂无评论

Two-sided disassembly line balancing problem with sequence-dependent setup time: A constraint programming model and artificial bee colony algorithm

引用

EXPERT SYSTEMS WITH APPLICATIONS 2022年 203卷

作者： Cil, Zeynel Abidin Kizilay, Damla Li, Zixiang Oztop, Hande Izmir Democracy Univ Dept Ind Engn Izmir Turkey Wuhan Univ Sci & Technol Key Lab Met Equipment & Control Technol Wuhan Hubei Peoples R China Wuhan Univ Sci & Technol Hubei Key Lab Mech Transmiss & Mfg Engn Wuhan Hubei Peoples R China Izmir Democracy Univ Dept Ind Engn Gursel Aksel Bulvari 14 TR-35140 Izmir Turkey

The large-size products can allow workers to perform tasks on both sides of the line. Hence, a two-sided disassembly line is preferred to ensure several advantages, such as a shorter line. The two-sided disassembly line balancing problem (TDLBP) is relatively new in the literature. This study considers the two-sided disas-sembly line balancing problem with sequence-dependent setup time (TDLBP-SDST) to reflect the real practice better, as sequence-dependent setup times may exist between tasks in many real-life applications. To the authors' best knowledge, sequence-dependent setup time has not been considered for the TDLBP in the current literature. The proposed problem creates a more complicated problem. Therefore, proposing effective solution techniques is more critical for obtaining better results. This study proposes two new mixed-integer linear programming models and a novel constraint programming (CP) model to define and solve the TDLBP-SDST. A genetic algorithm, an artificial bee colony algorithm, and the improved versions of these two algorithms are also developed to solve the large-size problems due to the NP-hardness of the TDLBP-SDST. Furthermore, a novel CP model is proposed for the standard TDLBP without considering sequence-dependent setup times. Initially, we compare the performance of the proposed CP model to those of the previous state-of-the-art methods in the literature for the TDLBP without sequence-dependent setup time. The computational results show that the proposed CP model out-performs all the other solution methods and reports the best-known results for all existing benchmark instances for the TDLBP. Then, we present the computational results of the proposed models and algorithms for the TDLBP-SDST. Computational study on a comprehensive set of generated instances indicates that the proposed solution methods effectively solve the TDLBP-SDST.

关键词： Two-sided disassembly line Line balancing Sequence -dependent setup time constraint programming Metaheuristic algorithms Mixed -integer linear programming

来源：评论

学校读者我要写书评

暂无评论

Integration of constraint programming and ModelBased Approach for System Synthesis 15

Integration of Constraint Programming and ModelBased Approac...

引用

15th Annual IEEE International Systems Conference (SysCon)

作者： Pierre-Alain, Yvars Laurent, Zimmer Inst Super Mecan Paris SupMeca EA7393 QUARTZ St Ouen France Dassault Aviat Direct Prospect St Ouen France

ISBN: (纸本)9781665444392

Most of the work in the field of Model-Based System Engineering for the design of technical systems consists of implementing solution-oriented approaches. Several system modeling languages are available to represent fully defined systems from several points of view. It is also possible to link these descriptions with simulation or analysis tools to evaluate the solutions thus described. After having studied the limits of this way of designing system, we propose in this paper an approach oriented to the description of the design problem to be solved, through an adapted formalism called DEPS. This formalism allows a model-based approach for architecture and system synthesis. DEPS (Design Problem Specification) addresses problems of sizing, configuration, resource allocation and more generally of architecture generation or synthesis encountered in system design. The systems considered can be physical systems, software-intensive systems or mixed systems (embedded, mechatronical, cyber-physical). This language combines structural modeling features specific to object-oriented languages with problem specification features from constraint programming. We also present an integrated approach through the DEPS Studio environment, allowing DEPS modeling, model compilation and solving using an integrated constraint programming solver. This integration allows, among other things, the development and the debugging of models directly in DEPS rather than in the language of an external solver. The approach is illustrated on a simple case of electrical system synthesis.

关键词： constraint programming model based system synthesis problem modeling problem solving

来源：评论

学校读者我要写书评

暂无评论

A constraint programming model for makespan minimisation in batch manufacturing pharmaceutical facilities

引用

COMPUTERS & CHEMICAL ENGINEERING 2022年 156卷 107565-107565页

作者： Awad, Mohamed Mulrennan, Konrad Donovan, John Macpherson, Russell Tormey, David Inst Technol Sligo Ctr Precis Engn Mat & Mfg Res Sligo Ireland GlaxoSmithKline Sligo Ireland

This work introduces a constraint programming (CP) model to minimise the makespan of a large scheduling problem in batch pharmaceutical manufacturing facilities. The model included campaign manufacturing, sequence-dependent changeover, forbidden product-equipment assignment, non-working periods, limited renewable resources, finite intermediate/non-intermediate storage policies and preemptive and non-preemptive operations. The model was tested by scheduling two real examples. Each example consisted of two cases. Case A used the actual number of workers per shift. Case B involved reorganising the shift pattern of the workers. The results from the model were qualitatively validated and compared with the baseline schedules. The makespan of the first example decreased by 24.35% for case 1.A and 38.63% for case 1.B. The second example reported a 2.17% decrease in makespan for case 2.A and 16.67% decrease for case 2.B. This demonstrates the success of the proposed model as a simulation tool to identify the manufacturing bottlenecks by running what-if scenarios. (c) 2021 Elsevier Ltd. All rights reserved.

关键词： Batch production scheduling Multi-product Flow-shop environment constraint programming Pharmaceuticals Makespan minimisation

来源：评论

学校读者我要写书评

暂无评论

Combining constraint programming and Temporal Decomposition Approaches - Scheduling of an Industrial Formulation Plant 1

引用

18th International Conference on the Integration of constraint programming, Artificial Intelligence, and Operations Research (CPAIOR)

作者： Klanke, Christian Bleidorn, Dominik R. Yfantis, Vassilios Engell, Sebastian TU Dortmund Univ Fac Biochem & Chem Engn Proc Dynam & Operat Grp Emil Figge Str 70 D-44229 Dortmund Germany INOSIM Joseph Von Fraunhofer Str 20 D-44227 Dortmund Germany Tech Univ Kaiserslautern Dept Mech & Proc Engn Chair Machine Tools & Control Syst Gottlieb Daimler Str 42 D-67663 Kaiserslautern Germany

ISBN: (数字)9783030782306

ISBN: (纸本)9783030782306;9783030782290

This contribution deals with the development of a constraint programming (CP) model and solution strategy for a two-stage industrial formulation plant with parallel production units for crop protection chemicals. Optimal scheduling of this plant is difficult: a high number of units and operations have to be scheduled while at the same time a high degree of coupling between the operations is present due to the need for synchronizing charging and discharging operations. In the investigated problem setting the formulation lines produce several intermediates that are filled into a variety of types of final containers by filling stations. Formulation lines and filling stations each consist of parallel, non-identical sets of equipment units. Buffer tanks are used to decouple the two stages, to increase the capacity utilization of the overall plant. The CP model developed in this work solves small instances of the scheduling problem monolithically. To deal with large instances a decomposition algorithm is developed. The overall set of batches is divided into subsets which are scheduled iteratively. The algorithm is designed in a moving horizon fashion, in order to counteract the disadvantages of the limited lookahead that order-based decomposition approaches typically suffer from. The results show that the complex scheduling problem can be solved within acceptable solution times and that the proposed moving horizon strategy (MHS) yields additional benefits in terms of solution quality.

关键词： constraint programming Moving-horizon Decomposition algorithm Batch process scheduling

来源：评论

学校读者我要写书评

暂无评论

"I Want It That Way": Enabling Interactive Decision Support Using Large Language Models and constraint programming

arXiv

引用

arXiv 2023年

作者： Lawless, Connor Schoeffer, Jakob Le, Lindy Rowan, Kael Sen, Shilad Hill, Cristina St Suh, Jina Sarrafzadeh, Bahareh Cornell University United States University of Texas Austin United States Microsoft United States Microsoft Research United States Macalester College United States

A critical factor in the success of many decision support systems is the accurate modeling of user preferences. Psychology research has demonstrated that users often develop their preferences during the elicitation process, highlighting the pivotal role of system-user interaction in developing personalized systems. This paper introduces a novel approach, combining Large Language Models (LLMs) with constraint programming to facilitate interactive decision support. We study this hybrid framework through the lens of meeting scheduling, a time-consuming daily activity faced by a multitude of information workers. We conduct three studies to evaluate the novel framework, including a diary study to characterize contextual scheduling preferences, a quantitative evaluation of the system’s performance, and a user study to elicit insights with a technology probe that encapsulates our framework. Our work highlights the potential for a hybrid LLM and optimization approach for iterative preference elicitation, and suggests design considerations for building systems that support human-system collaborative decision-making processes. Copyright © 2023, The Authors. All rights reserved.

关键词： constraint programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：