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

constraint programming and constructive heuristics for parallel machine scheduling with sequence-dependent setups and common servers

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2022年第PartA期172卷

作者： Heinz, Vilem Novak, Antonin Vlk, Marek Hanzalek, Zdenek Czech Tech Univ Fac Elect Engn Prague Czech Republic Czech Tech Univ Czech Inst Informat Robot & Cybernet Prague Czech Republic

This paper examines scheduling problem denoted as P|(seq), ser|C(max )in Graham's notation;in other words, scheduling of tasks on parallel identical machines (P) with sequence-dependent setups (seq) each performed by one of the available servers (ser). The goal is to minimize the makespan (C-max). We propose a constraint programming (CP) model for finding the optimal solution and constructive heuristics suitable for large problem instances. These heuristics are also used to provide a feasible starting solution to the proposed CP model, significantly improving its efficiency. This combined approach constructs solutions for benchmark instances of up to 20 machines and 500 tasks in 10 s, with makespans 3 % to 115 % greater than the calculated lower bounds with a 5% average. The extensive experimental comparison also shows that our proposed approaches outperform the existing ones.

关键词： Scheduling Parallel machines Sequence-dependent setups Servers constraint programming

来源：评论

学校读者我要写书评

暂无评论

constraint programming model for resource-constrained assembly line balancing problem

引用

SOFT COMPUTING 2020年第7期24卷 5367-5375页

作者： Alakas, Haci Mehmet Pinarbasi, Mehmet Yuzukirmizi, Mustafa Kirikkale Univ Dept Ind Engn Fac Engn Ankara Yolu 6 Km Kampus Yahsihan 71451 Kirikkale Turkey

The literature studies assume that resources used to be perform the tasks are certain and homogenous in any assembly line. However, tasks may need to be processed by general resource requirements in real life. These general resources could be classified by usage of resources such as simple or multiple, alternative and concurrent. The problem which is related to assignment of the task to any workstation and assignment of resources needed by the task simultaneously is defined as resource-constrained assembly line balancing problems (RCALBPs). In this study, a multiobjective model with minimization of cycle time and resource usage for a given number of stations is modeled to solve the RCALBP for the first time. Alternative and general resource types for tasks and using more than two resource type requirements are also considered. A constraint programming model is developed and solved to find the optimal solutions of these problems. The proposed models are tested with sample scenarios to show the effectiveness of the model.

关键词： Assembly line balancing constraint programming Resource constraints Type-2 problem

来源：评论

学校读者我要写书评

暂无评论

Optimal Beacon Placement for Indoor Positioning Using constraint programming 19

Optimal Beacon Placement for Indoor Positioning Using Constr...

引用

19th IEEE/ACS International Conference on Computer Systems and Applications (AICCSA)

作者： Loeffler, Sven Kroll, Franz Becker, Ilja Hofstedt, Petra Brandenburg Tech Univ Cottbus Programming Languages & Compiler Construct Cottbus Germany

ISBN: (纸本)9798350310085

Indoor location is a growing topic for hospitals, retirement homes and in case of emergency. For the resource efficient (indoor) positioning of mobile individuals an optimized distribution of the used sensors is necessary. The placement of beacons (sensors) in a building (indoor positioning) can be a difficult and laborious task, especially if done by hand. Multiple researchers already tried to tackle this problem using different algorithms and under the consideration of distinct use cases. However, none of the currently known methods incorporate constraint programming by using only Boolean variables. In this paper we tried to develop a new method for an efficient placement of Bluetooth Low Energy (BLE) beacons in an indoor scenario. More specifically, we try to optimize the beacons for a trilateration algorithm used for indoor positioning. This algorithm requires that three beacons should be in range for every possible position in the building. In a next step the initially calculated beacon positions are further optimized. This is done by trying to reduce the number of beacons used. Afterwards we evaluate the quality of the beacon placements by comparing it against a manually optimized beacon placement and evaluating it in an existing building by checking the quality of multiple sample positions.

关键词： Beacon Placement constraint programming Indoor Positioning Trilateration Combinatorial Optimization Local and Global Search IoTs CSP SAT

来源：评论

学校读者我要写书评

暂无评论

constraint programming and Constructive Heuristics for Parallel Machine Scheduling with Sequence-Dependent Setups and Common Servers

arXiv

引用

arXiv 2023年

作者： Heinz, Vilém Novák, Antonín Vlk, Marek Hanzálek, Zdeněk Faculty of Electrical Engineering Czech Technical University Prague Czech Republic Czech Institute of Informatics Robotics and Cybernetics Czech Technical University Prague Czech Republic

This paper examines scheduling problem denoted as P |seq, ser|Cmax in Graham’s notation;in other words, scheduling of tasks on parallel identical machines (P) with sequence-dependent setups (seq) each performed by one of the available servers (ser). The goal is to minimize the makespan (Cmax). We propose a constraint programming (CP) model for finding the optimal solution and constructive heuristics suitable for large problem instances. These heuristics are also used to provide a feasible starting solution to the proposed CP model, significantly improving its efficiency. This combined approach constructs solutions for benchmark instances of up to 20 machines and 500 tasks in 10 seconds, with makespans 3 % to 11.5 % greater than the calculated lower bounds with a 5% average. The extensive experimental comparison also shows that our proposed approaches outperform the existing ones. © 2023, CC BY-NC-ND.

关键词： constraint programming

来源：评论

学校读者我要写书评

暂无评论

A constraint programming approach to capacity planning in container vessels

引用

MARITIME ECONOMICS & LOGISTICS 2022年第2期24卷 415-438页

作者： Lee, Byung Kwon Low, Joyce M. W. Natl Univ Singapore Dept Ind Syst Engn & Management 1 Engn Dr 2 Singapore 117576 Singapore Singapore Management Univ Lee Kong Chian Sch Business 50 Stamford Rd Singapore 178899 Singapore

A container vessel carries containers of various characteristics, in terms of size, weight, and contents. The cargo load of a container vessel, being subjected to a set of operational conditions and restrictions regarding ship stability and safety, is a fundamental element in decision-making when a shipping line provides logistics services to clients. This study presents a constraint programming-based model for the capacity planning of a container vessel under various operational conditions. The proposed model generates base solutions and is complemented with a rich scenario-based analysis that utilizes real-life ship data of a container vessel operated by a liner shipping company with a significant market presence. Solutions obtained from the model provide insights on containership capacity planning with differing settings and search strategies. Recommendations to container carriers, regarding improved capacity planning, are the highlights of the study.

关键词： Capacity planning Cargo-mix profiles Stowage planning Container vessels constraint programming

来源：评论

学校读者我要写书评

暂无评论

Enhancing constraint programming via supervised learning for job shop scheduling

引用

KNOWLEDGE-BASED SYSTEMS 2024年 293卷

作者： Sun, Yuan Nguyen, Su Thiruvady, Dhananjay Li, Xiaodong Ernst, Andreas T. Aickelin, Uwe La Trobe Univ La Trobe Business Sch Bundoora Vic 3086 Australia RMIT Univ Sch Accounting Informat Syst & Supply Chain Melbourne Vic 3000 Australia Deakin Univ Sch Informat Technol Geelong Australia RMIT Univ Sch Comp Technol Melbourne Vic 3000 Australia Monash Univ Sch Math Clayton Vic 3800 Australia Univ Melbourne Sch Comp & Informat Syst Parkville Vic 3010 Australia

constraint programming (CP) is a powerful technique for solving constraint satisfaction and optimization problems. In CP solvers, the variable ordering strategy used to select which variable to explore first in the solving process has a significant impact on solver effectiveness. To address this issue, we propose a novel variable ordering strategy based on supervised learning, which we evaluate in the context of job shop scheduling problems. Our learning -based methods predict the optimal solution of a problem instance and use the predicted solution to order variables for CP solvers. Unlike traditional variable ordering methods, our methods can learn from the characteristics of each problem instance and customize the variable ordering strategy accordingly, leading to improved solver performance. Our experiments demonstrate that training machine learning models is highly efficient and can achieve high accuracy. Furthermore, our learned variable ordering methods perform competitively compared to four existing methods. Finally, we showcase the benefits of integrating machine learning -based variable ordering methods with conventional domain -based approaches through tie -breaking.

关键词： constraint programming Supervised learning Variable ordering Job shop scheduling problem

来源：评论

学校读者我要写书评

暂无评论

Computing Bipath Multicommodity Flows with constraint programming-Based Branch-and-Price-and-Cut

引用

INFORMS JOURNAL ON COMPUTING 2024年第6期36卷 1359-1756, C2页

作者： Zhang, Jiachen Magnouche, Youcef Bauguion, Pierre Martin, Sebastien Beck, Christopher Univ Toronto Dept Mech & Ind Engn Toronto ON M5S 3G8 Canada Huawei Technol Paris Res Ctr F-92100 Boulogne Billancourt France

We propose a constraint programming (CP)-based branch -and -price -and -cut framework to exactly solve bipath multicommodity flow (MCF): an MCF problem with two paths for each demand. The goal is to route demands in a capacitated network under the minimum cost. The two paths must have disjoint arcs, and the delays accumulated along the two paths must be within a small deviation of each other. CP is used at multiple points in this framework: for solving pricing problems, for cut generation, and for primal and branching node heuristics. These modules use a CP solver designed for network routing problems and can be adapted to other combinatorial optimization problems. We also develop a novel, complete, two -level branching scheme. On a set of diverse bipath MCF instances, experimental results show that our algorithm significantly outperforms monolithic CP and mixed integer linear programming models and demonstrate the efficiency and flexibility brought by the tailored integration of linear programming and CP methodologies.

关键词： constraint programming multicommodity flow network routing

来源：评论

学校读者我要写书评

暂无评论

A constraint programming Approach for Discrete Time-Cost Tradeoff Problems in a Time-Constrained Activity Network

引用

BUILDINGS 2024年第7期14卷 2073页

作者： Liu, Yang Liu, Dawei Rong, Yanzhao Song, Penghui Zou, Xin State Grid East Inner Mongolia Elect Power Supply Hohhot 010010 Peoples R China China Railway Construct Engn Grp Beijing 100160 Peoples R China North China Elect Power Univ Sch Econ & Management Baoding 071003 Peoples R China

The discrete time-cost tradeoff problem (DTCTP) is a well-researched topic in the field of operations research. The majority of existing DTCTP models are based on traditional activity networks, which permit the execution of an activity as soon as all its predecessors have been completed. This assumption is reasonable, but it is important to note that there are always exceptions. The main work of this study was threefold. Firstly, we expanded the analysis of the DTCTP to encompass time-constrained activity networks (DTCTPTC), which encompassed three different types of time constraints. The first constraint was the time-window constraint, which limited the time interval during which an activity could be executed. The second constraint was the time-schedule constraint, which specified the times at which an activity could begin execution. The third constraint was the time-switch constraint, which required project activities to start at specific times and remain inactive during designated time periods. Secondly, a constraint programming (CP) model was developed for the purpose of solving the DTCTPTC. The model employed interval variables to define the activity and its potential time constraints, while CP expressions were utilized to ensure the feasibility of the solution. The objective was to identify the optimal execution mode for each activity, the optimal start times for time-scheduled activities, and the optimal work/rest patterns for time-switch activities, with the aim of minimizing the total cost of the project. Finally, the efficacy of the proposed CP model was validated through two case studies based on two illustrative projects of varying sizes. The outcomes were then compared against existing algorithms. The results demonstrated that time constraints were important factors affecting schedule optimization, and the proposed CP model had the ability to solve large-scale DTCTPTC.

关键词： time-cost tradeoffs time-window time-schedule time-switch constraint programming

来源：评论

学校读者我要写书评

暂无评论

Crop planting layout optimization in sustainable agriculture: A constraint programming approach

引用

COMPUTERS AND ELECTRONICS IN AGRICULTURE 2024年 224卷

作者： Adamo, Tommaso Colizzi, Lucio Dimauro, Giovanni Guerriero, Emanuela Pareo, Deborah Univ Salento Dipartimento Ingn Innovaz Via Monteroni I-73100 Lecce Italy Univ Bari Aldo Moro Dipartimento Informat Via E Orabona 4 I-70125 Bari Italy

In sustainable agriculture, intercropping systems represent a valuable approach. These systems involve placing mutually beneficial plant types in close proximity to each other, with the goal of exploiting biodiversity to reduce pesticide and water usage, as well as improve soil nutrient utilization. Despite its potential, the optimization of intercropping systems has received limited attention in previous studies. One of the first steps in the design of an intercropping system is the solution of the crop planting layout problem, which involves meeting crop demand while maximizing positive interactions between adjacent plants. We perform a complexity analysis of this problem and solve it through constraint programming, an artificial intelligence technique, which relies on automated reasoning, constraint propagation and search heuristics. To this aim, we present two constraint programming models based on integer variables and interval variables, respectively. Through a computational study on real -life instances, we examine the impact of different modelling approaches on the difficulty of solving the crop planting layout problem with standard constraint programming solvers. This research work has also provided the groundwork for a sowing robotic arm (under development), aiming to automate intercropping systems and assist farm workers.

关键词： constraint programming Optimization crop planting layout AI planning Smart Agriculture Intercropping systems

来源：评论

学校读者我要写书评

暂无评论

Optimal Schedules for High-Level programming Environments on FPGAs with constraint programming 36

Optimal Schedules for High-Level Programming Environments on...

引用

36th IEEE International Parallel and Distributed Processing Symposium (IEEE IPDPS)

作者： Jungblut, Pascal Kranzlmuller, Dieter Ludwig Maxilimilians Univ Dept CS MNM Team Munich Germany

ISBN: (纸本)9781665497473

Scheduling tasks on reconfigurable hardware is a well-known problem. Yet, the adoption of advanced scheduling strategies for reconfigurable systems is still low. We argue that a pragmatic solution not relying on low-level features like partial reconfiguration is feasible. Our theoretical framework describes reconfigurable hardware in a simple and abstract way. The constraints of a schedule are used to derive a constraint programming formulation. We present two heuristic algorithms based on list scheduling and on clustering, respectively. The model is evaluated and compared to partial reconfiguration using parameters from a previously observed LU decomposition on an FPGA. The losses are compared to a conventional, optimal approach. It can be integrated into existing technologies to aide the adoption of high-level FPGA programming environments.

关键词： Scheduling FPGA constraint programming HLS

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：