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

FlexBeamOpt: Hybrid solution methodologies for high-throughput GEO satellite beam laydown and resource allocation

INTERNATIONAL JOURNAL OF SATELLITE COMMUNICATIONS AND NETWORKING 2023年第6期41卷 515-538页

作者： Gaudry, Angus Li, Ryan Mak-Hau, Vicky Deakin Univ Sch Informat Technol Waurn Ponds Australia

Modern satellite communication systems are required to serve heterogeneous and geographically dispersed user demands with limited resources. In this paper, we investigate methodologies for dynamic resource allocation in Geosynchronous Earth Orbit (GEO) High-throughput Satellite (HTS) systems. We designed three solution approaches FlexBeamOpt v1, FlexBeamOpt v2, and FlexBeamOpt v3, each as a hybridization of custom heuristics, integer linear programming, and/or constraint programming. We test the performance of the three approaches on 12 test instances that vary in user distribution (realistic, random, and clustered), user numbers (500 vs. 5000 users), and demand distribution (uniform vs. random). We observed that FlexBeamOpt v1 consistently outperformed FlexBeamOpt v2 and FlexBeamOpt v3 in terms of demand coverage and number of users covered for realistic and random user distribution test instances but at the cost of computation time. FlexBeamOpt v3 is the fastest in these instances. For clustered user distribution instances, FlexBeamOpt v3 performed better in terms of demand coverage and number of users covered, at the cost of using more beams. For these test instances, FlexBeamOpt v2 is the fastest in terms of computation time while providing a comparable solution quality.

关键词： constraint programming custom heuristics flexible beams GEO satellites integer programming resource allocation

来源：评论

学校读者我要写书评

暂无评论

A System for Automated Industrial Test Laboratory Scheduling

引用

ACM TRANSACTIONS ON INTELLIGENT SYSTEMS AND TECHNOLOGY 2023年第1期14卷 1-27页

作者： Danzinger, Philipp Geibinger, Tobias Janneau, David Mischek, Florian Musliu, Nysret Poschalko, Christian TU Wien DBAI Christian Doppler Lab Artificial Intelligence & O Karlspl 13 A-1040 Vienna Austria Robert Bosch AG Gollnergasse 15-17 A-1030 Vienna Austria

Automated scheduling solutions are tremendously important for the efficient operation of industrial laboratories. The Test Laboratory Scheduling Problem (TLSP) is an extension of the well-known Resource Constrained Project Scheduling Problem (RCPSP) and captures the specific requirements of such laboratories. In addition to several new scheduling constraints, it features a grouping phase, where the jobs to be scheduled are assembled from smaller units. In this work, we introduce an innovative scheduling system that allows the efficient and flexible generation of schedules for TLSP. It features a new constraint programming model that covers both the grouping and the scheduling aspect, as well as a hybrid Very Large Neighborhood Search that internally uses the CP model. Our experimental results on generated and real-world benchmark instances show that good results can be obtained even compared to settings which have a good grouping already provided, including several new best known solutions for these instances. Our algorithms for TLSP have been successfully implemented in a real-world industrial test laboratory. We provide a detailed description of the deployed system as well as additional useful soft constraints supported by the solvers and general lessons learned. This includes a discussion of the choice of soft constraint weights, with an analysis on the impact and relation of different objectives to each other. Our experiments show that some soft constraints complement each other well, while others require explicit trade-offs via their relative weights.

关键词： Test laboratory scheduling RCPSP constraint programming very large neighborhood search

来源：评论

学校读者我要写书评

暂无评论

Computing relaxations for the three-dimensional stable matching problem with cyclic preferences

引用

constraintS 2023年第2期28卷 138-165页

作者： Cseh, Agnes Escamocher, Guillaume Quesada, Luis Ctr Econ & Reg Stud Inst Econ Budapest Hungary Univ Bayreuth Dept Math Bayreuth Germany Insight Ctr Data Analyt Cork Ireland Univ Coll Cork Sch Comp Sci & Informat Technol Cork Ireland

constraint programming has proven to be a successful framework for determining whether a given instance of the three-dimensional stable matching problem with cyclic preferences (3dsm-cyc) admits a solution. If such an instance is satisfiable, constraint models can even compute its optimal solution for several different objective functions. On the other hand, the only existing output for unsatisfiable 3dsm-cyc instances is a simple declaration of impossibility. In this paper, we explore four ways to adapt constraint models designed for 3dsm-cyc to the maximum relaxation version of the problem, that is, the computation of the smallest part of an instance whose modification leads to satisfiability. We also extend our models to support the presence of costs on elements in the instance, and to return the relaxation with lowest total cost for each of the four types of relaxation. Empirical results reveal that our relaxation models are efficient, as in most cases, they show little overhead compared to the satisfaction version.

关键词： Three-dimensional stable matching with cyclic preferences 3dsm-cyc constraint programming Relaxation Almost stable matching

来源：评论

学校读者我要写书评

暂无评论

constraint programming approach to quay crane scheduling problem

引用

TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW 2013年 59卷 108-122页

作者： Unsal, Ozgur Oguz, Ceyda Koc Univ Coll Engn Istanbul Turkey

This study presents a constraint programming (CP) model for the quay crane scheduling problem (QCSP), which occurs at container terminals, with realistic constraints such as safety margins, travel times and precedence relations. Next, QCSP with time windows and integrated crane assignment and scheduling problem, are discussed. The performance of the CP model is compared with that of algorithms presented in QCSP literature. The results of the computational experiments indicate that the CP model is able to produce good results while reducing the computational time, and is a robust and flexible alternative for different types of crane scheduling problems. (C) 2013 Elsevier Ltd. All rights reserved.

关键词： Quay crane scheduling constraint programming Container terminals Ready times Time windows

来源：评论

学校读者我要写书评

暂无评论

Optimizing Parallel Task Execution for Multi-Agent Mission Planning

引用

IEEE ACCESS 2023年 11卷 24367-24381页

作者： Miloradovic, Branko Curuklu, Baran Ekstrom, Mikael Papadopoulos, Alessandro Vittorio Malardalen Univ Div Intelligent Future Technol S-72220 Vasteras Sweden

Multi-agent systems have received a tremendous amount of attention in many areas of research and industry, especially in robotics and computer science. With the increased number of agents in missions, the problem of allocation of tasks to agents arose, and it is one of the most fundamental classes of problems in robotics, formally known as the Multi-Robot Task Allocation (MRTA) problem. MRTA encapsulates numerous problem dimensions, and it aims at providing formulations and solutions to various problem configurations, i.e., complex multi-agent missions. One dimension of the MRTA problem has not caught much of the research attention. In particular, problem configurations including Multi-Task (MT) robots have been neglected. However, the increase in computational power, in robotic systems, has allowed the utilization of parallel task execution. This in turn had the benefit of allowing the creation of more complex robotic missions;however, it came at the cost of increased problem complexity. Our contribution to the aforementioned domain can be grouped into three categories. First, we model the problem using two different approaches, Integer Linear programming and constraint programming. With these models, we aim at filling the gap in the literature related to the formal definition of MT robot problem configuration. Second, we introduce the distinction between physical and virtual tasks and their mutual relationship in terms of parallel task execution. This distinction allows the modeling of a wider range of missions while exploiting possible parallel task execution. Finally, we provide a comprehensive performance analysis of both models, by implementing and validating them in CPLEX and CP Optimizer on the set of problems. Each problem consists of the same set of test instances gradually increasing in complexity, while the percentage of virtual tasks in each problem is different. The analysis of the results includes exploration of the scalability of both models and solv

关键词： Task analysis Robots Planning Taxonomy Resource management Complexity theory Analytical models Multi-agent mission planning multi-robot task allocation parallel task execution integer linear programming constraint programming

来源：评论

学校读者我要写书评

暂无评论

A bounded constraint-based approach to aid in fault localization from a counterexample

引用

INNOVATIONS IN SYSTEMS AND SOFTWARE ENGINEERING 2024年 1-19页

作者： Bekkouche, Mohammed Ecole Super Informat LabRI SBA Lab Sidi Bel Abbes Algeria

A model checker can produce a trace of counter-example for an erroneous program, which is often difficult to exploit for locating faults. In this paper, we propose a fault localization algorithm from counter-examples, named LocFaults, combining the approaches of Bounded Model-Checking (BMC) with a constraint satisfaction problem (CSP). The input is a faulty program for which a counter-example and a postcondition are provided. To identify helpful information for fault location, LocFaults analyzes the paths of the CFG (Control Flow Graph) of the erroneous program to calculate the subsets of suspicious instructions to correct the program. Indeed, we generate a system of constraints for paths of the control flow graph for which at most k conditional statements can be wrong. Then we calculate the MCSs (Minimal Correction Sets) of limited size on each of these paths. The removal of one of these sets of constraints yields a maximal satisfiable subset, in other words, a maximal subset of constraints satisfying the postcondition. LocFaults has been experimentally evaluated on a set of academic and realistic programs. The main advantage of this flow-driven approach is that the computed sets of suspicious instructions are small, each of them being associated with an identified path. Moreover, the constraint programming-based framework of LocFaults allows mixing Boolean and numerical constraints in an efficient and straightforward way.

关键词： Locating faults constraint programming LocFaults BugAssist Minimal correction subset Deviation

来源：评论

学校读者我要写书评

暂无评论

A decomposition-based two-stage online scheduling approach and its integrated system in the hybrid flow shop of steel industry

引用

EXPERT SYSTEMS WITH APPLICATIONS 2023年第PartC期213卷

作者： Jiang, Sheng-Long Xu, Chuanpei Zhang, Long Ma, Yong Chongqing Univ Coll Mat Sci & Engn Chongqing 400044 Peoples R China Guilin Univ Elect Technol Sch Elect Engn & Automat Guilin 541004 Peoples R China Guangxi Key Lab Automat Detect Technol & Instru Guilin 541004 Peoples R China Automat Res & Design Inst Met Ind State Key Lab Hybrid Proc Ind Automat Syst & Eq Beijing 100071 Peoples R China

Steelmaking-continuous casting (SCC) is one of the most critical building blocks in the modern steel industry. Many random events occur in the real-world SCC production system. In this paper, we propose a two-stage online scheduling policy that protects the baseline schedule by the slacks provided by intra-flow times and casting speeds. The main task of the two-stage online scheduling model is: (1) to make "here-and-now" decisions for minimizing economic costs and penalties caused by constraint violations;(2) make "wait-and-see" decisions for online scheduling. Afterward, we propose a decomposition-based optimization algorithm that divides the online scheduling problem into a master problem (MP) to seek partial solutions at the last processing stage and a slave problem (SP) to check optimal solutions for upstream processing stages. Then, we employ the IBM ILOG CPLEX to solve MP and use the constraint programming (CP) optimizer to solve SP. Sensitivity analyses and algorithm comparisons are conducted on a set of well-synthetic and realistic instances to validate the proposed model and algorithm. The results show that the proposed online scheduling model and algorithm can solve realistic in-dustrial case studies. Finally, we also develop a scheduling system integrating the proposed model and algorithm.

关键词： Online scheduling System architecture Hybrid flow shop constraint programming Decomposition

来源：评论

学校读者我要写书评

暂无评论

Compact Models to Solve the Precedence-Constrained Minimum-Cost Arborescence Problem with Waiting Times

引用

ALGORITHMS 2024年第1期17卷 12页

作者： Dell'Amico, Mauro Jamal, Jafar Montemanni, Roberto Univ Modena & Reggio Emilia Dept Sci & Methods Engn Via Amendola 2 I-42122 Reggio Emilia RE Italy Univ Modena & Reggio Emilia Interdept Ctr En&Tech Capannone 19 TecnopoloPiazza Europa 1 I-42122 Reggio Emilia RE Italy

The minimum-cost arborescence problem is a well-studied problem. Polynomial-time algorithms for solving it exist. Recently, a new variation of the problem called the Precedence-Constrained Minimum-Cost Arborescence Problem with Waiting Times was presented and proven to be NP-hard. In this work, we propose new polynomial-size models for the problem that are considerably smaller in size compared to those previously proposed. We experimentally evaluate and compare each new model in terms of computation time and quality of the solutions. Several improvements to the best-known upper and lower bounds of optimal solution costs emerge from the study.

关键词： arborescences precedence constraints mixed integer linear programming constraint programming

来源：评论

学校读者我要写书评

暂无评论

A hybrid evolutionary approach for lexicographic green flexible jobshop with interval uncertainty

引用

NATURAL COMPUTING 2025年 1-14页

作者： Afsar, Sezin Puente, Jorge Palacios, Juan Jose Gonzalez-Rodriguez, Ines Vela, Camino R. Univ Oviedo Dept Comp Sci Campus Gijon Gijon 33204 Spain Univ Cantabria Dept Math Stat & Computat Santander 39005 Spain

This article addresses the flexible job shop problem with uncertain processing times modelled by intervals. Due to climate change and the need for energy efficiency, there is an increasing interest in sustainability in addition to traditional production-related objectives such as makespan. In this work, we tackle a lexicographical goal programming scenario minimising makespan firstly and total energy consumption lately. We propose a hybrid evolutionary algorithm based on a genetic algorithm, incorporating heuristic seeding and a post-processing step using constraint programming. The experimental study shows that the proposed approach is able to meet tighter makespan goals than previously published methods, while offering a 32% improvement in energy consumption when goals are met.

关键词： Flexible job shop scheduling Intervals Heuristic seeding constraint programming Lexicographic goal programming

来源：评论

学校读者我要写书评

暂无评论

Exact methods for the Oven Scheduling Problem

引用

constraintS 2023年第2期28卷 320-361页

作者： Lackner, Marie-Louise Mrkvicka, Christoph Musliu, Nysret Walkiewicz, Daniel Winter, Felix TU Wien DBAI Christian Doppler Lab Artificial Intelligence & Op Favoritenstr 9 A-1040 Vienna Austria MCP GmbH Canovagasse 7 A-1010 Vienna Austria

The Oven Scheduling Problem (OSP) is a new parallel batch scheduling problem that arises in the area of electronic component manufacturing. Jobs need to be scheduled to one of several ovens and may be processed simultaneously in one batch if they have compatible requirements. The scheduling of jobs must respect several constraints concerning eligibility and availability of ovens, release dates of jobs, setup times between batches as well as oven capacities. Running the ovens is highly energy-intensive and thus the main objective, besides finishing jobs on time, is to minimize the cumulative batch processing time across all ovens. This objective distinguishes the OSP from other batch processing problems which typically minimize objectives related to makespan, tardiness or lateness. We propose to solve this NP-hard scheduling problem using exact techniques and present two different modelling approaches, one based on batch positions and another on representative jobs for batches. These models are formulated as constraint programming (CP) and integer linear programming (ILP) models and implemented both in the solver-independent modeling language MiniZinc and using interval variables in CP Optimizer. An extensive experimental evaluation of our solution methods is performed on a diverse set of problem instances. We evaluate the performance of several state-of-the-art solvers on the different models and on three variants of the objective function that reflect different real-life scenarios. We show that our models can find feasible solutions for instances of realistic size, many of those being provably optimal or nearly optimal solutions.

关键词： Oven Scheduling Problem Parallel batch processing constraint programming Integer linear programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：