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

Optimized Scheduling of Periodic Hard Real-Time Multicore Systems

IEEE ACCESS 2023年 11卷 30027-30039页

作者： Aceituno, Jose Maria Guasque, Ana Balbastre, Patricia Blanes, Francisco Pomante, Luigi Univ Politecn Valencia Inst Automat Informat Ind Valencia 46022 Spain Univ Aquila Ctr Excellence DEWS I-67100 Laquila Italy

Multicore systems were developed to provide a substantial performance increase over mono-core systems. But shared hardware resources are a problem as they add unpredictable delays that affect the schedulability of multicore hard real-time systems. In recent years much effort has been put into modelling interference and proposing scheduling techniques to mitigate its negative effect. Using one of these models, we propose a scheduling technique, based on integer linear programming (ILP) that, in combination with a task to core allocator, not only achieves a feasible schedule but also reduces the interference produced by shared hardware resources in the context of hard real-time multicore systems. The evaluation shows how interference is reduced (approximate to 83.47%) and schedulability is increased (approximate to 12.25%) compared to traditional heuristics.

关键词： Scheduling Multicore processing Interference integer linear programming Job shop scheduling Real-time systems Computational modeling optimization partitioned systems real-time systems static scheduling

来源：评论

学校读者我要写书评

暂无评论

A biobjective availability optimization problem with nonlinear constraints

引用

ANNALS OF TELECOMMUNICATIONS 2023年第1-2期78卷 1-12页

作者： Santos, Dorabella Martins, Lucia Gomes, Teresa Univ Coimbra Dept Elect & Comp Engn INESC Coimbra Polo 2 P-3030290 Coimbra Portugal Univ Coimbra Dept Elect & Comp Engn Polo 2 P-3030290 Coimbra Portugal

In this paper, we revisit a biobjective optimization problem arising in software-defined networking with availability guarantees. The problem jointly optimizes the number of controllers and their locations, as well as optimizes a set of links that can be upgraded to achieve intercontroller availability targets. This problem is known to be NP-complete, includes generalized nonlinear flow constraints and includes nonlinear and nonconvex path pair availability constraints. In this paper, we propose an iterative approach for solving the optimization problem. The approach consists in a linear approximation that is obtained through convex relaxation. The linear approximated problem is solved iteratively, and can be tailored to be as close to the original problem as possible at the expense of a greater computational effort. The results obtained using this approach are compared with previously obtained ones. We show how the iterative approach is able to significantly improve most of the tested instances (or find the same solution as previously obtained) within feasible computational effort.

关键词： Biobjective optimization Convex relaxation integer linear programming Controller placement problem Availability guarantees

来源：评论

学校读者我要写书评

暂无评论

Algorithms for rescheduling jobs with a LIFO buffer to minimize the weighted number of late jobs

引用

JOURNAL OF SCHEDULING 2023年第3期26卷 267-287页

作者： Pferschy, Ulrich Resch, Julia Righini, Giovanni Karl Franzens Univ Graz Dept Operat & Informat Syst Univ Str 15 A-8010 Graz Austria Univ Milan Dept Comp Sci Via Celoria 18 I-20133 Milan Italy

Rescheduling can help to improve the quality of a schedule with respect to an initially given sequence. In this paper, we consider the possibility of rescheduling jobs arriving for processing at a single machine under the following limitations: (a) jobs can only be moved toward the end of the schedule and not toward the front, and (b) when a job is taken out of the sequence, it is put on a buffer of limited capacity before being reinserted in its new position closer to the end of the sequence. The buffer is organized as a stack with a last-in/first-out policy. As an objective function, we consider the minimization of the weighted number of late jobs. For this NP-hard problem, we first provide two different integer linear programming (ILP) formulations. Furthermore, we develop a branch-and-bound algorithm with a branching rule based on the movement of jobs. Then a new pseudo-polynomial dynamic programming algorithm is presented which utilizes dominance criteria and an efficient handling of states. Our computational experiments with up to 100 jobs show that this algorithm performs remarkably well and can be seen as the current method of choice.

关键词： Scheduling Rescheduling integer linear programming Dynamic programming Branch-and-bound

来源：评论

学校读者我要写书评

暂无评论

Planning and Monitoring Equitable Clinical Trial Enrollment Using Goal programming

引用

IEEE JOURNAL OF BIOMEDICAL AND HEALTH INFORMATICS 2023年第2期27卷 1084-1095页

作者： Qi, Miao Das, Amar K. Bennett, Kristin P. Rensselaer Polytech Inst Dept Comp Sci Troy NY 12180 USA IBM Res Cambridge MA 02142 USA Rensselaer Polytech Inst Inst Data Explorat & Applicat Troy NY 12180 USA Rensselaer Polytech Inst Math Sci Dept Troy NY 12180 USA Rensselaer Polytech Inst Comp Sci Dept Troy NY 12180 USA

Randomized clinical trial (RCT) studies are the gold standard for scientific evidence on treatment benefits to patients. RCT outcomes may not be generalizable to clinical practice if the trial population is not representative of the patients for which the treatment is intended. Specifically, enrollment plans may not adequately include groups of patients with protected attributes, such as gender, race, or ethnicity. Inequities in RCTs are a major concern for funding agencies such as the National Institutes of Health (NIH) and for policy makers. We address this challenge by proposing a goal-programming approach, explicitly integrating measurable enrollment goals, to design equitable enrollment plans for RCTs. We evaluate our model in both single and multisite settings using the enrollment criteria and study population from the Systolic Blood Pressure Intervention Trial (SPRINT) study. Our model can successfully generate equitable enrollment plans that satisfy multiple goals such as sample representativeness and minimum total financial cost. Our model can detect deviations from a target plan during the enrollment process and update the plan to reduce deviations in the remaining process. Finally, through appropriate site selection in the planning stage, the model can demonstrate the possibility of enrolling a nationally representative study population if geographic constraints exist in multisite recruitment (e.g., clinical centers in a particular region). Our model can be used to prospectively produce and retrospectively evaluate how equitable enrollment plans are based on subjects' protected attributes, and it allows researchers to provide justifications on validity of scientific analysis and evaluation of subgroup disparities.

关键词： Biomedical informatics computer aided analysis data analysis health equity integer linear programming optimization public healthcare randomized clinical trials enrollment

来源：评论

学校读者我要写书评

暂无评论

Mathematical models for the cutting stock with limited open stacks problem

引用

RAIRO-OPERATIONS RESEARCH 2023年第4期57卷 2067-2085页

作者： Guimaraes, Gabriel Gazzinelli Poldi, Kelly Cristina Univ Estadual Campinas UNICAMP Inst Matemat Estat & Comp Cient IMECC R Sergio Buarque de Holanda 651 BR-13083859 Campinas SP Brazil

This research is focused on solving the Cutting Stock with Limited Open Stacks Problem (CS-LOSP). The CS-LOSP is an optimization problem which consists of the classical Cutting Stock Problem (CSP) paired with the additional constraint that the maximum number of open stacks from the sequencing of the cutting patterns obtained from the CSP solution is equal or lower than a preset limit. Despite being a problem with great practical importance, the literature lacks models for this problem, and only one-dimensional problems are addressed. In this paper, we propose two integer linear programming formulations for the CS-LOSP that are valid for solving instances of the CSP of any dimension. In order to eliminate symmetrical solutions to the problem, the proposed formulations sequence sets of cutting patterns instead of sequencing the cutting patterns individually, thus, the search space for solutions is reduced. A set of randomly generated instances for the two-dimensional problem is used to perform computational experiments in order to validate the proposed mathematical formulations.

关键词： Cutting stock problem open stack pattern sequencing mathematical formulation integer linear programming setup cost

来源：评论

学校读者我要写书评

暂无评论

Towards Globally Optimal Design of Multipliers for FPGAs

引用

IEEE TRANSACTIONS ON COMPUTERS 2023年第5期72卷 1261-1273页

作者： Bottcher, Andreas Kumm, Martin Fulda Univ Appl Sci Appl Comp Sci Dept D-36037 Fulda Germany

The design of a multiplier typically consists of three steps: (1) partial product generation, (2) compressor tree design and (3) the selection of the final adder. Conventionally, these three steps are performed consecutively. However, when targeting FPGAs, there are many possibilities in all three design steps that heavily influence each other. This proposal presents for the first time a holistic optimization, combining all three optimization steps yielding a minimum amount of look-up-tables (LUTs) while it can also guarantee the minimal number of (pipeline) stages. An ILP-formulation for the determination of a combined, globally optimal solution for the multiplier tiling, compressor tree generation and final adder selection is proposed. With globally optimal we mean that the best solution is found for a given set of sub-multipliers for partial product generation, compressors and final *** allows to improve the quality and evaluate the limitations of existing heuristic 3-step approaches. It is shown experimentally for the example of Xilinx FPGAs, that globally optimal solutions can be obtained for multiplier sizes of practical relevance, leading to significant LUT reductions. Additional packing density experiments show that a significantly larger number of multiplier instances can be mapped to the same device.

关键词： Adders Field programmable gate arrays Costs Table lookup Optimization Shape Proposals Compressor tree computer arithmetic FPGA integer linear programming multiplier multiplier tiling

来源：评论

学校读者我要写书评

暂无评论

Virtualized Network Graph Design and Embedding Model to Minimize Provisioning Cost

引用

IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT 2023年第3期20卷 3562-3584页

作者： Sato, Takehiro Kurimoto, Takashi Urushidani, Shigeo Oki, Eiji Kyoto Univ Grad Sch Informat Kyoto 6068501 Japan Natl Inst Informat Informat Syst Architecture Sci Res Div Tokyo 1018430 Japan

The provisioning cost of a virtualized network (VN) depends on several factors, including the numbers of virtual routers (VRs) and virtual links (VLs), mapping of them on a substrate infrastructure, and routing of data traffic. An existing model, known as the virtual network embedding (VNE) model, determines the embedding of given VN graphs into the substrate infrastructure. When the resource allocation model of the VNE problem is adopted to a single-entity scenario, where a single entity fulfills the roles of both a service provider and an infrastructure provider, an issue of increased costs of VNs and access paths arise. This paper proposes a model for virtualized network graph design and embedding (VNDE) for the single-entity scenario. The VNDE model determines the number of VRs and a VN graph for each request in conjunction with embedding. The VNDE model also determines access paths that connect customer premises and VRs. We formulate the VNDE model as an integer linear programming (ILP) problem. We develop heuristic algorithms for the cases where the ILP problem cannot be solved in practical time. We evaluate the performance of the VNDE model on several networks, including an actual Japanese academic backbone network. Numerical results show that the proposed model designs suitable VN graphs and embeds them according to the volume of traffic demands and access path cost. Compared with the benchmark model, which is based on a classic VNE approach, the proposed model reduces the provisioning cost at most 28.7% in our examined scenarios.

关键词： Network virtualization optimization model integer linear programming provisioning cost

来源：评论

学校读者我要写书评

暂无评论

Collaborative strategic and tactical planning for one-way station-based carsharing systems with trip selection and vehicle relocation

引用

TRANSPORTATION LETTERS-THE INTERNATIONAL JOURNAL OF TRANSPORTATION RESEARCH 2023年第1期15卷 18-29页

作者： Wu, Jiayuan Hu, Lu Jiang, Yangsheng Southwest Jiaotong Univ Sch Transportat & Logist Chengdu 610031 Peoples R China Dept Southwest Jiaotong Univ Chengdu Peoples R China

Carsharing emerges as a flexible and sustainable transportation mode to deal with severe urban challenges. This paper addresses a joint design problem of carsharing systems by an integer linear programming (ILP) model. Strategic planning of stations' number, location and parking capacities and tactical planning of the fleet size and initial vehicle distribution are collaboratively optimized by considering all-day vehicle relocation and dynamic trip selection at the operational level. For the first time, vehicle relocation and demand selection are integrated with the joint optimization of strategic and tactical planning. We present a greedy heuristic algorithm embedding ILP to solve the problem. The case study of Chengdu demonstrates that the algorithm is computationally efficient when dealing with large-scale problems. The results identify how vehicle relocation and trip selection work in different scenes of travel time and demands and we conclude operators should target at medium-long trips by discount or promotion.

关键词： Carsharing location model trip selection vehicle relocation greedy algorithm integer linear programming

来源：评论

学校读者我要写书评

暂无评论

Node based compact formulations for the Hamiltonian p-median problem

引用

NETWORKS 2023年第4期82卷 336-370页

作者： Barbato, Michele Canas, Francisco Gouveia, Luis Pesneau, Pierre Univ Milan Dipartimento Informat Giovanni Antoni Milan Italy Univ Lisbon Fac Ciencias Ctr Matemat Aplicacoes Fundamentais & Invest Opera Lisbon Portugal Univ Bordeaux CNRS INRIA Bordeaux INPIMB Talence France Univ Lisbon Fac Ciencias Ctr Matemat Aplicacoes Fundamentais & Invest Opera C6-Piso 4 P-1749016 Lisbon Portugal

In this paper, we introduce, study and analyze several classes of compact formulations for the symmetric Hamiltonian p$$ p $$-median problem (Hp$$ p $$MP). Given a positive integer p$$ p $$ and a weighted complete undirected graph G=(V,E)$$ G=\left(V,E\right) $$ with weights on the edges, the Hp$$ p $$MP on G$$ G $$ is to find a minimum weight set of p$$ p $$ elementary cycles partitioning the vertices of G$$ G $$. The advantage of developing compact formulations is that they can be readily used in combination with off-the-shelf optimization software, unlike other types of formulations possibly involving the use of exponentially sized sets of variables or constraints. The main part of the paper focuses on compact formulations for eliminating solutions with less than p$$ p $$ cycles. Such formulations are less well known and studied than formulations which prevent solutions with more than p$$ p $$ cycles. The proposed formulations are based on a common motivation, that is, the formulations contain variables that assign labels to nodes, and prevent less than p$$ p $$ cycles by stating that different depots must have different labels and that nodes in the same cycle must have the same label. We introduce and study aggregated formulations (which consider integer variables that represent the label of the node) and disaggregated formulations (which consider binary variables that assign each node to a given label). The aggregated models are new. The disaggregated formulations are not, although in all of them new enhancements have been included to make them more competitive with the aggregated models. The two main conclusions of this study are: (i) in the context of compact formulations, it is worth looking at the models with integer node variables, which have a smaller size. Despite their weaker LP relaxation bounds, the fewer variables and constraints lead to faster integer resolution, especially when solving instances with more than 50 nodes;(ii) the best of our compact

关键词： combinatorial optimization Hamiltonian p-median problem integer linear programming location routing polyhedral theory valid inequalities

来源：评论

学校读者我要写书评

暂无评论

An Interactive Co-Evolutionary Framework for Multi-Objective Critical Node Detection on Large-Scale Complex Networks

引用

IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING 2023年第3期10卷 1722-1735页

作者： Zhang, Lei Zhang, Huaijin Yang, Haipeng Liu, Zhengyi Cheng, Fan Anhui Univ Sch Comp Sci & Technol Informat Mat & Intelligent Sensing Lab Anhui Prov Key Lab Intelligent Comp & Signal ProcMinist Educ Hefei 230039 Peoples R China

Multi-objective evolutionary algorithms (MOEAs) have been proved to be competitive for solving the critical node detection problem (CNDP) on complex networks in both non-cascading scenario and cascading scenario. With the continuous expansion of network scale, the search space of the existing MOEAs will increase exponentially. To this end, we propose an interactive co-evolutionary framework (ICoEF) to solve the multi-objective critical node detection on large-scale complex networks, where a set of local populations as well as a global population are interactively evolved to detect the critical nodes with high qualities. Specifically, we first use a community detection algorithm to divide the original network into multiple local communities, where each local community generates a local population for quickly finding local solutions independently. Then, the latent good solutions can be easily obtained by combining the returned local solutions. After that, one global population generated by the original network can refine these latent good solutions by using the proposed two-stage replacement search strategy. Through the above local and global evolutionary interaction, a set of high-quality solutions can be finally obtained. Experiments on synthetic and real-world networks demonstrate the superiority of the proposed framework over several state-of-the-art baselines in both non-cascading and cascading scenarios.

关键词： Optimization Complex networks Statistics Sociology Costs integer linear programming Evolutionary computation Cooperative co-evolutionary critical node detection large-scale complex network multi-objective optimization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：