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

30th International Conference on Principles and Practice of constraint programming, CP 2024

作者： Anders, Markus Brenner, Sofia Rattan, Gaurav TU Darmstadt Germany University of Twente Enschede Netherlands

ISBN: (纸本)9783959773362

Symmetry breaking is a widely popular approach to enhance solvers in constraint programming, such as those for SAT or MIP. Symmetry breaking predicates (SBPs) typically impose an order on variables and single out the lexicographic leader (lex-leader) in each orbit of assignments. Although it is NP-hard to find complete lex-leader SBPs, incomplete lex-leader SBPs are widely used in practice. In this paper, we investigate the complexity of computing complete SBPs, lex-leader or otherwise, for SAT. Our main result proves a natural barrier for efficiently computing SBPs: efficient certification of graph non-isomorphism. Our results explain the difficulty of obtaining short SBPs for important CP problems, such as matrix-models with row-column symmetries and graph generation problems. Our results hold even when SBPs are allowed to introduce additional variables. We show polynomial upper bounds for breaking certain symmetry groups, namely automorphism groups of trees and wreath products of groups with efficient SBPs. © Markus Anders, Sofia Brenner, and Gaurav Rattan.

关键词： constraint programming

来源：评论

学校读者我要写书评

暂无评论

Balancing collaborative human-robot assembly lines to optimise cycle time and ergonomic risk

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2022年第1期60卷 25-47页

作者： Stecke, Kathryn E. Mokhtarzadeh, Mahdi Univ Texas Dallas Naveen Jindal Sch Management Dept Operat Management Richardson TX 75080 USA

Human-robot collaboration can enhance productivity of production lines and reduce human ergonomic risk. The numbers and types of robots and stations in which robots are allocated need to be determined. Operations should be scheduled carefully when a human and robot work on a part in a station to obtain a feasible operation allocation with the highest efficiency and lowest ergonomic risk. A mixed-integer linear programming model, constraint programming model, and Benders decomposition algorithm were developed to analyse advantages of collaborative robots in assembly lines. An energy expenditure method was used to evaluate ergonomic risk. By scheduling and balancing collaborative human-robot assembly lines, operational advantages and scheduling constraints from human-robot collaboration were studied when immobile and mobile robots are used. Regression lines were developed that can help managers determine how many and what types of robots are best for a line and what the impact of robot mobility on robot and line performance can be. The best configuration for equipping a line with collaborative robots is when (number of robots)/(number of stations) is near .7 and about 37% of robots are mobile. Robots can be efficiently used in lines with both a small and large number of passive resources and in simple and mixed-model lines.

关键词： Assembly line balancing human-robot collaboration mobile robots constraint programming Benders decomposition

来源：评论

学校读者我要写书评

暂无评论

Mathematical models for the minimization of open stacks problem

引用

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH 2022年第5期29卷 2944-2967页

作者： Martin, Mateus Yanasse, Horacio Hideki Pinto, Maria Jose Univ Fed Sao Paulo Inst Ciencia & Tecnol Ave Cesare Mansueto Giulio Lattes 1201 BR-12247014 Sao Jose Dos Campos SP Brazil Inst Estudos Avancados IEAv Div C4ISR Trevo Coronel Aviador Jose Alberto Albano Amarant BR-12228001 Sao Jose Dos Campos SP Brazil

In this paper, we address the minimization of open stacks problem (MOSP). This problem often appears during production planning of manufacturing industries, such as in the cutting of objects to comply with space constraints around the cutting machine in the glass, furniture, and metallurgical industries. During the processing of the cutting patterns, all the copies of a demanded item are stored in a stack usually placed near the cutting machine. One stack for each type of demanded item, that is, different items do not share the same stack. In this sense, the MOSP consists of finding an optimal sequence of a given set of cutting patterns, while minimizing the maximum number of simultaneously open stacks. To effectively model and solve the problem, we present a novel integer linear programming (ILP) formulation based on a graph representation of the problem. We derive an ILP formulation from the modeling approach of Faggioli and Bentivoglio for the MOSP. Then we develop a simple constraint programming model based on interval variables and renewable resources. We performed computational experiments to evaluate the proposed approaches in comparison with other ILP formulations from the literature. Using a general-purpose solver, the proposed approaches perform well in terms of solution quality and computational time in comparison to the benchmark models for small and moderate-sized problem instances.

关键词： pattern sequencing problems integer linear programming MOSP graph constraint programming interval variables

来源：评论

学校读者我要写书评

暂无评论

Towards Prevention of Sportsmen Burnout:Formal Analysis of Sub-Optimal Tournament Scheduling

引用

Computers, Materials & Continua 2022年第1期70卷 1509-1526页

作者： Syed Rameez Naqvi Adnan Ahmad S.M.Riazul Islam Tallha Akram M.Abdullah-Al-Wadud Atif Alamri Department of Electrical and Computer Engineering COMSATS University IslamabadWah CampusWah47040Pakistan Department of Computer Science and Engineering Sejong UniversitySeoul05006Korea Department of Software Engineering College of Computer and Information SciencesKing Saud UniversityRiyadh11543Saudi Arabia Research Chair of Pervasive and Mobile Computing King Saud UniversityRiyadh11543Saudi Arabia

Scheduling a sports tournament is a complex optimization problem,which requires a large number of hard constraints to *** the availability of several such constraints in the literature,there remains a gap sincemost of the new sports events pose their own unique set of requirements,and demand novel *** talking of the strictly time bound events,ensuring fairness between the different teams in terms of their rest days,traveling,and the number of successive games they play,becomes a difficult task to resolve,and demands *** this work,we present a similar situation with a recently played sports event,where a suboptimal schedule favored some of the sides more than the *** introduce various competitive parameters to draw a fairness comparison between the sides and propose a weighting criterion to point out the sides that enjoyed this schedule more than the ***,we use root mean squared error between an ideal schedule and the actual ones for each side to determine unfairness in the distribution of rest days across their entire *** latter is crucial,since successively playing a large number of games may lead to sportsmen burnout,which must be prevented.

关键词： Sports scheduling optimization constraint programming fatigue analysis

来源：评论

学校读者我要写书评

暂无评论

Incomplete MaxSAT approaches for combinatorial testing

引用

JOURNAL OF HEURISTICS 2022年第4期28卷 377-431页

作者： Ansotegui, Carlos Manya, Felip Ojeda, Jesus Salvia, Josep M. Torres, Eduard Univ Lleida Log & Optimizat Grp LOG Lleida Spain CSIC Artificial Intelligence Res Inst IIIA Campus UAB Bellaterra 08193 Spain

We present a Satisfiability (SAT)-based approach for building Mixed Covering Arrays with constraints of minimum length, referred to as the Covering Array Number problem. This problem is central in Combinatorial Testing for the detection of system failures. In particular, we show how to apply Maximum Satisfiability (MaxSAT) technology by describing efficient encodings for different classes of complete and incomplete MaxSAT solvers to compute optimal and suboptimal solutions, respectively. Similarly, we show how to solve through MaxSAT technology a closely related problem, the Tuple Number problem, which we extend to incorporate constraints. For this problem, we additionally provide a new MaxSAT-based incomplete algorithm. The extensive experimental evaluation we carry out on the available Mixed Covering Arrays with constraints benchmarks and the comparison with state-of-the-art tools confirm the good performance of our approaches.

关键词： Combinatorial testing Maximum satisfiability constraint programming

来源：评论

学校读者我要写书评

暂无评论

Complete symmetry breaking constraints for the class of uniquely Hamiltonian graphs

引用

constraintS 2022年第1-2期27卷 8-28页

作者： Itzhakov, Avraham Codish, Michael Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel

This paper introduces, for the first time, a complete symmetry breaking constraint of polynomial size for a significant class of graphs: the class of uniquely Hamiltonian graphs. We introduce a canonical form for uniquely Hamiltonian graphs and prove that testing whether a given uniquely Hamiltonian graph is canonical can be performed efficiently. Based on this canonicity test, we construct a complete symmetry breaking constraint of polynomial size which is satisfied only by uniquely Hamiltonian graphs which are canonical. We apply the proposed symmetry breaking constraint to show new results regarding the class of uniquely Hamiltonian graphs. We also show that the proposed approach applies almost directly for the class of graphs which contain any cycle of known length where it shown to result in a partial symmetry breaking constraint. Given that it is unknown if there exist complete symmetry breaking constraints for graphs of polynomial size, this paper makes a first step in the direction of identifying specific classes of graphs for which such constraints do exist.

关键词： Symmetry breaking constraint programming Uniquely Hamiltonian graphs Isomorph-free graph generation

来源：评论

学校读者我要写书评

暂无评论

Novel MILP and CP models for distributed hybrid flowshop scheduling problem with sequence-dependent setup times

引用

SWARM AND EVOLUTIONARY COMPUTATION 2022年第0期71卷

作者： Meng, Leilei Gao, Kaizhou Ren, Yaping Zhang, Biao Sang, Hongyan Chaoyong, Zhang Liaocheng Univ Sch Comp Sci Liaocheng 252000 Peoples R China Macau Univ Sci & Technol Macau Inst Syst Engn Macau 999078 Peoples R China Jinan Univ Sch Intelligent Syst Sci & Engn Dept Ind Engn Zhuhai 519070 Peoples R China Huazhong Univ Sci & Technol State Key Lab Digital Manufacturing Equipment & Te Wuhan 430074 Peoples R China

As regards distributed hybrid flow shop scheduling with sequence-dependent setup times (DHFSP-SDST), three novel mixed-integer linear programming (MILP) models and a constraint programming (CP) model are formulated for the same-factory and different-factory environments. The three novel MILP models are based on two different modeling ideas. The existing MILP model and the three proposed MILP models are compared in detail from several aspects, such as binary decision variables, continuous decision variables, constraints, solution performance and solution time. By solving the benchmarks in existing studies, the effectiveness and superiority of the proposed MILP and CP models are proved. Experimental results show that the MILP model of sequence-based modeling idea performs best, the MILP model of adjacent sequence-based modeling idea takes the second place and the existing MILP model of position-based modeling idea performs worst. The CP model is more efficient and effective than MILP models. In addition, compared with the existing meta-heuristic algorithms (e.g., DABC and IABC), the proposed MILP models prove the optimal solutions of 37 instances and improve 17 current best solutions. The CP model solves all the 45 instances to optimality and improves 19 current best solutions for benchmarks in the existing studies

关键词： Distributed hybrid flow shop scheduling Setup time Mixed-integer linear programming constraint programming Modeling idea

来源：评论

学校读者我要写书评

暂无评论

A Novel Fitness Function for Automated Software Test Case Generation Based on Nested constraint Hardness

A Novel Fitness Function for Automated Software Test Case Ge...

引用

Genetic and Evolutionary Computation Conference (GECCO)

作者： Bui Thi Mai Anh Do Van Tri Bui Quoc Trung Hanoi Univ Sci & Technol Sch Informat & Commun Technol Hanoi Vietnam

ISBN: (纸本)9798400701207

Search-Based Software Testing (SBST) has drawn a lot of interests as a powerful approach for automated test data generation. One major limitation of search-based methods is that they may get stuck in local optima and become inefficient if the fitness function does not provide any direction toward a test target, particularly when dealing with hard branch targets (e.g., nested predicates). Recent research has focused on enhancing the fitness function by taking branch hardness into account in order to direct the evolutionary process. However, either the characteristics of constraints (e.g., their involved variables' domain) are not taken into account or the difficulty level of a branch is separately studied. In this paper, we aim to address the test data generation with a focus on hard branches by proposing a novel fitness function based on nested constraints (i.e., including the target constraint and those that impact its coverage) and the domain sizes of their variables. The empirical study promises efficiency and effectiveness for the new fitness function. Our proposed approach outperforms its counterparts significantly, particularly for the branches that are difficult to be covered.

关键词： software search based testing constraint programming genetic algorithm automated testcase generation

来源：评论

学校读者我要写书评

暂无评论

Optimization Strategies for Resource-Constrained Project Scheduling Problems in Underground Mining

引用

INFORMS JOURNAL ON COMPUTING 2022年第6期34卷 3042-3058页

作者： Hill, Alessandro Brickey, Andrea J. Cipriano, Italo Goycoolea, Marcos Newman, Alexandra Calif Polytech State Univ San Luis Obispo Dept Ind & Mfg Engn San Luis Obispo CA 93407 USA South Dakota Sch Mines & Technol Min Engn & Management Rapid City SD 57701 USA Univ Adolfo Ibanez Alicanto Labs Santiago 7941169 Chile Univ Adolfo Ibanez Sch Business Santiago 7941169 Chile Colorado Sch Mines Dept Mech Engn Golden CO 80401 USA

Effective computational methods are important for practitioners and researchers working in strategic underground mine planning. We consider a class of problems that can be modeled as a resource-constrained project scheduling problem with optional activities;the objective maximizes net present value. We provide a computational review of math programming and constraint programming techniques for this problem, describe and implement novel problem-size reductions, and introduce an aggregated linear program that guides a list scheduling algorithm running over unaggregated instances. Practical, large-scale planning problems cannot be processed using standard optimization approaches. However, our strategies allow us to solve them to within about 5% of optimality in several hours, even for the most difficult instances.

关键词： underground mine planning resource-constrained project scheduling constraint programming mathematical programming

来源：评论

学校读者我要写书评

暂无评论

Workforce planning and production scheduling in a reconfigurable manufacturing system facing the COVID-19 pandemic

引用

JOURNAL OF MANUFACTURING SYSTEMS 2022年 63卷 563-574页

作者： Vahedi-Nouri, Behdin Tavakkoli-Moghaddam, Reza Hanzalek, Zdenek Dolgui, Alexandre Univ Tehran Coll Engn Sch Ind Engn Tehran Iran Czech Tech Univ IID CIIRC Prague Czech Republic IMT Atlantique LS2N CNRS Nantes France

Due to the outbreak of the COVID-19 pandemic, the manufacturing sector has been experiencing unprecedented issues, including severe fluctuation in demand, restrictions on the availability and utilization of the workforce, and governmental regulations. Adopting conventional manufacturing practices and planning approaches under such circumstances cannot be effective and may jeopardize workers' health and satisfaction, as well as the continuity of businesses. Reconfigurable Manufacturing System (RMS) as a new manufacturing paradigm has demonstrated a promising performance when facing abrupt market or system changes. This paper investigates a joint workforce planning and production scheduling problem during the COVID-19 pandemic by leveraging the adaptability and flexibility of an RMS. In this regard, workers' COVID-19 health risk arising from their allocation, and workers' preferences for flexible working hours are incorporated into the problem. Accordingly, first, novel Mixed-Integer Linear programming (MILP) and constraint programming (CP) models are developed to formulate the problem. Next, exploiting the problem's intrinsic characteristics, two properties of an optimal solution are identified. By incorporating these properties, the initial MILP and CP models are considerably improved. Afterward, to benefit from the strengths of both improved models, a novel hybrid MILP-CP solution approach is devised. Finally, comprehensive computational experiments are conducted to evaluate the performance of the proposed models and extract useful managerial insights on the system flexibility.

关键词： Scheduling Workforce planning COVID-19 pandemic Reconfigurable manufacturing system Reconfigurable machine tool constraint programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：