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

An exact constraint programming method for the multi-manned assembly line balancing problem with assignment restrictions

引用

EXPERT SYSTEMS WITH APPLICATIONS 2025年 259卷

作者： Possan Junior, Moacyr Carlos Michels, Adalberto Sato Magatao, Leandro Fed Univ Technol Parana UTFPR Grad Program Elect & Comp Engn CPGEI Curitiba Brazil Univ Melbourne Sch Math & Stat Melbourne Australia Santa Catarina State Univ UDESC Sao Bento Do Sul Brazil

This paper proposes an exact constraint programming (CP) method with an extensive focus on real-world constraints for the Multi-manned Assembly Line Balancing Problem with Assignment Restrictions (MALBPAR). We perform an in-depth literature review to gather examples from real assembly lines and organize the AR regarding tasks, stations, workers, and mounting positions. Our study classifies the AR related to transformed resources and provides a general and unified model. We explore the concept of variable workplaces to dynamically assign workers to mounting positions and aggregate no overlap restrictions to avoid interference between workers. The classic MALBP model is extended by gradually incrementing the number of restrictions. The model variant found in the literature is herein called Partial MALBP-AR. Compared to the previous state-of-the-art Tabu Search Algorithm (TSA) for this problem, the Partial MALBP-AR found twelve additional optimality proofs. Besides the relevant results regarding solution quality, the CP method also has a satisfactory CPU performance. We also propose an entirely new set of AR and test these practical conditions with the so-called Extended MALBP-AR. Such an extended model, which covers all the AR presented here, reached optimality within the computational time limit for 36 out of 38 instances. The worst-case gap for an open instance is 8.20%. The results show a trade-off between the number of deemed restrictions and the computational performance. However, considering the detailed set of AR, we can obtain more representative solutions regarding the final balancing implementation compared to theoretical cases. The method can be used to design experiments, turning certain constraints on and off and allowing managers to evaluate different resource allocation scenarios.

关键词： Combinatorial optimization Scheduling Assembly line balancing Multi-manned station Assignment restrictions constraint programming

来源：评论

学校读者我要写书评

暂无评论

A hybrid constraint programming and cross-entropy approach for balancing U-Shaped disassembly line with flexible workstations and spatial constraints

引用

JOURNAL OF INDUSTRIAL INFORMATION INTEGRATION 2025年 45卷

作者： Zhang, Yu Zhang, Zeqiang Chu, Feng Mammar, Said Southwest Jiaotong Univ Sch Mech Engn Technol & Equipment Rail Transit Operat & Maintena Chengdu 610031 Peoples R China Southwest Jiaotong Univ Tangshan Inst Tangshan 063000 Peoples R China Univ Paris Saclay Univ Evry Blvd Francois Mitterrand F-91000 Evry France

Disassembly lines are an effective means for the large-scale, industrialized recycling of end-of-life products. Among these, U-shaped disassembly lines are particularly noted for their combination of flexibility and production efficiency. This study addresses the U-shaped disassembly line balancing problem, considering the coexistence of separate stations and spatial limitations within workstations. A mixed-integer nonlinear programming model and a constraint programming model are developed to accurately capture this complex problem. Additionally, a novel hybrid constraint programming with a goal-driven cross-entropy optimization algorithm (CP-GDCE) is introduced. This algorithm combines a multi-objective cross-entropy grouping framework, a constraint programming-based heuristic initialization, a multi-point crossover recombination mechanism, and large neighborhood search techniques, significantly enhancing solution efficiency and accuracy. Extensive benchmarking and experimental validation indicate that the CP-GDCE not only excels in addressing the specific problem of this study but also demonstrates superiority in classic disassembly line balancing issues. In 21 test cases, the CP-GDCE achieved superior hypervolume and inverted generational distance values compared to 11 benchmark algorithms. A practical application using a printer disassembly example shows that the proposed U-shaped configuration is highly flexible and efficient, compatible with both traditional U-shaped and straight disassembly lines. This configuration significantly reduces the total length of the disassembly line, improving space utilization and highlighting its practical potential and advantages.

关键词： U-shaped disassembly line Flexible workstation Spatial limitation Mixed-integer programming constraint programming Cross-entropy method

来源：评论

学校读者我要写书评

暂无评论

A multi-stage constraint programming approach to solve clustering problems in open-pit mine planning

引用

ENGINEERING OPTIMIZATION 2025年第4期57卷 1111-1134页

作者： Mariz, Jorge Luiz Valenca Peroni, Rodrigo de Lemos Silva, Ricardo Martins de Abreu Badiozamani, Mohammad Mahdi Askari-Nasab, Hooman Univ Fed Rio Grande do Sul Min Engn Dept Porto Alegre Brazil Univ Fed Pernambuco Comp Ctr Recife Brazil Univ Alberta Sch Min & Petr Engn Edmonton AB Canada

The open-pit mine sequencing considering blocks with precedence is an NP-hard problem, which can be subdivided into long-, medium- and short-term plans, and requires different information and constraints in each stage. Through the aggregation of blocks into mining cuts, the size of the mine sequencing problem can be reduced and operational constraints can be added. In this study, a multi-stage constraint programming approach to tackle the mining cut clustering problem through a mixed integer linear programming model is proposed, as well as a geometric propagation heuristic to refine the solution. Unlike previously published studies, this approach optimizes the assignment of blocks to clusters and corrects their boundaries considering the size of the mining equipment. The methodology was validated on a real gold-ore data set. Feasible solutions were obtained in an acceptable computation time, while solutions which allowed more clusters increased their objective function and profit by up to 60%.

关键词： Short-term mine planning mining cut clustering constraint programming geometric propagation heuristic

来源：评论

学校读者我要写书评

暂无评论

The dual-resource-constrained re-entrant flexible flow shop a constraint programming approach and a hybrid genetic algorithm

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2025年第5期63卷 1803-1824页

作者： Mlekusch, Johanna Hartl, Richard F. Univ Vienna Dept Business Decis & Analyt A-1010 Vienna Austria

The dual-resource-constrained re-entrant flexible flow shop scheduling problem represents a specialised variant of the flow shop scheduling problem, inspired by real-world scenarios in screen printing industries. Besides the well-known flow shop structure, stages consist of identical parallel machines and operations may re-enter the same stage multiple times before completion. Moreover, each machine must be operated by a skilled worker, making it a dual-resource-constrained problem according to the existing literature. The objective is to minimise the total length of the production schedule. To address this problem, our study employs two methods: a constraint programming model and a hybrid genetic algorithm with a single-level solution representation and an efficient decoding heuristic. To evaluate the performance of our methods, we conducted a computational study using different problem instances. Our findings demonstrate that the proposed hybrid genetic algorithm consistently delivers high-quality solutions, particularly for large instances, while also maintaining a short computational time. Additionally, our methods improve existing benchmark results for instances from the literature for a subclass of the problem. Furthermore, we provide managerial insights into how dual-resource constraints affect the solution quality and the efficiency associated with different workforce configurations in the described production setting.

关键词： Production flexible re-entrant flow shop scheduling dual-resource hybrid genetic algorithm constraint programming

来源：评论

学校读者我要写书评

暂无评论

A constraint programming-based lower bounding procedure for the job shop scheduling problem

引用

COMPUTERS & OPERATIONS RESEARCH 2025年 177卷

作者： Yuraszeck, Francisco Mejia, Gonzalo Rossit, Daniel Alejandro Luer-Villagra, Armin Univ Andres Bello Dept Engn Sci Quillota 980 Vina Del Mar 2531015 Chile Univ La Sabana Fac Engn Campus Puente Comun Km 7 Autopista Norte Bogota Chia 250001 Colombia Univ Nacl UNS Dept Engn Bahia Blanca Argentina Univ Nacl Sur UNS CONICET INMABB Bahia Blanca Argentina Univ Andres Bello Dept Engn Sci Autopista Concepc Talcahuano 7100 Talcahuano Chile

This paper presents a novel constraint programming (CP) approach to obtain strong lower bounds for the Job Shop Scheduling Problem (JSSP) under the makespan criterion. Our approach comprises two phases. In the first phase, a relaxation of the original problem is solved, while in the second phase, this relaxation is iteratively tightened until a time limit is reached or no better bounds are found. We tested our procedure with 80 JSSP open instances, and the results validated our approach as we were able to find 7 new lower bounds and prove optimality in one instance.

关键词： Scheduling Job shop Lower bound Resource-constrained project scheduling problem constraint programming

来源：评论

学校读者我要写书评

暂无评论

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

引用

ACM TRANSACTIONS ON INTERACTIVE INTELLIGENT SYSTEMS 2024年第3期14卷 1-33页

作者： Lawless, Connor Schoeffer, Jakob Le, Lindyi Rowan, Kael Sen, Shilao Hill, Cristina St. Suh, Jina Sarrafzadeh, Bahareh Cornell Univ Ithaca NY 14850 USA Univ Texas Austin Austin TX USA Microsoft Redmond WA USA Microsoft Res Redmond WA USA Macalester Coll St Paul MN USA

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.

关键词： Decision support large language models constraint programming preference elicitation meeting scheduling

来源：评论

学校读者我要写书评

暂无评论

A multi-objective constraint programming approach to address clustering problems in mine planning

引用

ENGINEERING COMPUTATIONS 2024年第10期41卷 2682-2706页

作者： Mariz, Jorge Luiz Valenca Peroni, Rodrigo de Lemos Silva, Ricardo Martins de Abreu Badiozamani, Mohammad Mahdi Askari-Nasab, Hooman Univ Fed Rio Grande Do Sul Min Engn Dept Porto Alegre Brazil Univ Alberta Sch Min & Petr Engn Dept Civil & Environm Engn Edmonton AB Canada Univ Alberta Sch Min & Petr Engn Edmonton AB Canada

Purpose - The mine sequencing problem is NP-hard. Therefore, simplifying it is necessary. One way to do this is to employ clusters as input instead of individual blocks. The mining cut clustering problem has been little addressed in the literature, and the solutions used are almost always heuristic. We solve the mining cut clustering problem, which is NP-hard, through single- and multi-objective optimization, finding results that are local optima in acceptable computational time. Design/methodology/approach - We first elaborate an ILP-based model to address the mining cut clustering problem. We employ a mono-objective approach and two multi-objective approaches, solving all these models by constraint programming. To choose the best solutions generated by multi-objective approaches, we employ two multi-criteria decision analysis approaches, considering different weight configurations. We developed a case study using real data. Findings - We verified that the approaches based on multi-objective optimization performed better than the mono-objective approach for the economic return criterion. The weighted-sum multi-objective approach presented the best results considering all objective functions used. Once viable solutions were obtained through multi-objective optimization, multi-criteria decision analysis approaches almost always selected the same solution. We obtained solutions that are local optima in acceptable computational time. Research limitations/implications This study solves an instance with 80 blocks. Consequently, it is aimed at short-term mine planning. The methodology has not yet been evaluated in large instances related to medium- and long-term mine planning. Originality/value - This is the first time that multi-objective optimization has been employed to solve the mining cut custering problem. Even other problems related to mine planning were, at most, solved by goal programming, so that multi-objective optimization is a knowledge that is not widespread

关键词： Mine planning Operational mine sequencing Mining cut clustering Multi-objective optimization constraint programming

来源：评论

学校读者我要写书评

暂无评论

Invariant polydiagonal subspaces of matrices and constraint programming

引用

constraintS 2024年第3-4期29卷 300-314页

作者： Neuberger, John M. Sieben, Nandor Swift, James W. No Arizona Univ Dept Math & Stat Flagstaff AZ 86011 USA

In a polydiagonal subspace of the Euclidean space, certain components of the vectors are equal (synchrony) or opposite (anti-synchrony). Polydiagonal subspaces invariant under a matrix have many applications in graph theory and dynamical systems, especially coupled cell networks. We describe invariant polydiagonal subspaces in terms of coloring vectors. This approach gives an easy formulation of a constraint satisfaction problem for finding invariant polydiagonal subspaces. Solving the resulting problem with existing state-of-the-art constraint solvers greatly outperforms the currently known algorithms.

关键词： constraint programming Synchrony Anti-synchrony Invariant polydiagonal subspace Equitable partition

来源：评论

学校读者我要写书评

暂无评论

A constraint programming framework for preliminary mission analysis: Applications for constellation-servicing active debris removal

引用

ADVANCES IN SPACE RESEARCH 2024年第7期74卷 3060-3080页

作者： Barea, Adrian Gonzalo, Juan Luis Colombo, Camilla Urrutxua, Hodei Univ Rey Juan Carlos Aerosp Syst & Transport Res Grp Fuenlabrada Spain Politecn Milan Dept Aerosp Sci & Technol Milan Italy

constraint programming is a classical artificial intelligence paradigm characterised by its flexibility for the modelling of complex problems. In the field of space operations, this approach has been successfully used for mission planning and scheduling. This manuscript proposes a framework that leverages the strengths of constraint programming for the preliminary analysis of space missions, introducing some modifications to tailor it to the application at hand. Specifically, it uses constraint propagation and search techniques to thoroughly explore the configuration space of a mission in an efficient manner. Consequently, it is able to quantify the performance of precomputed mission choices with respect to the mission requirements, as well as generate new ones that optimise such performance. The proposed methodology has been particularised for two application cases involving active debris removal missions for large constellations in low Earth orbit, namely, a chaser case and a mothership case. The chaser case considers a servicing satellite that rendezvouses with the failed satellites of the constellation and directly transports them to a disposal orbit. The mothership case comprises a servicing satellite that installs deorbiting kits in each of the failed satellites, except for the one removed in the last place. This way, the servicing satellite will only transport this object, while the deorbiting kits will carry out the disposal of the rest of them. This methodology has been successfully used to evaluate a preliminary mission analysis of both application cases developed under ESA's Sunrise project. (c) 2024 COSPAR. Published by Elsevier B.V. This is an open access article under the CC BY license (http://***/licenses/by/4.0/).

关键词： Active space debris removal Constellation servicing Mission analysis constraint programming

来源：评论

学校读者我要写书评

暂无评论

Solving the three-dimensional open-dimension rectangular packing problem: A constraint programming model

引用

COMPUTERS & OPERATIONS RESEARCH 2024年 167卷

作者： Martin, Mateus de Queiroz, Thiago Alves Morabito, Reinaldo Univ Fed Fluminense Dept Engn Prod Rua Domingos Silverio 135 BR-25650050 Petropolis RJ Brazil Univ Fed Catalao Inst Matemat & Tecnol Ave Dr Lamartine P Avelar 1120 BR-75704020 Catalao GO Brazil Univ Fed Sao Carlos Dept Engn Prod Via Washington Luiz km 235 BR-13565905 Sao Carlos SP Brazil

This paper addresses the three-dimensional open -dimension rectangular packing problem (3D-ODRPP). This problem addresses a set of rectangular boxes of given dimensions and a rectangular container of open dimensions. The objective is to pack all boxes orthogonally into the container while minimizing the container volume. Real -world applications of the 3D-ODRPP arise in production systems with operations of shipping or moving. The literature has presented mainly mixed -integer programming (MIP) formulations and their linearization techniques for the problem allied with general-purpose optimization solvers. To model and solve the 3D-ODRPP, we propose a constraint programming model based on a position -free modeling approach with logic operators. We ran computational experiments to assess the performance of the proposed model compared to the benchmark MIP models from instances of the literature. The results show our approach is competitive in different sets of problem instances in terms of reaching optimality as well as providing satisfactory feasible solutions quickly.

关键词： Cutting and Packing Three-dimensional rectangular packing Open-dimension problems constraint programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：