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

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

来源：评论

学校读者我要写书评

暂无评论

Recombinations, chains and caps: resolving problems with the DCJ-indel model

引用

ALGORITHMS FOR MOLECULAR BIOLOGY 2024年第1期19卷 8页

作者： Bohnenkaemper, Leonard Bielefeld Univ Fac Technol Univ Str 25 D-33615 Bielefeld NRW Germany Bielefeld Univ Ctr Biotechnol CeBiTec Univ Str 25 D-33615 Bielefeld NRW Germany

One of the most fundamental problems in genome rearrangement studies is the (genomic) distance problem. It is typically formulated as finding the minimum number of rearrangements under a model that are needed to transform one genome into the other. A powerful multi-chromosomal model is the Double Cut and Join (DCJ) *** the DCJ model is not able to deal with some situations that occur in practice, like duplicated or lost regions, it was extended over time to handle these cases. First, it was extended to the DCJ-indel model, solving the issue of lost markers. Later ILP-solutions for so called natural genomes, in which each genomic region may occur an arbitrary number of times, were developed, enabling in theory to solve the distance problem for any pair of genomes. However, some theoretical and practical issues remained unsolved. On the theoretical side of things, there exist two disparate views of the DCJ-indel model, motivated in the same way, but with different conceptualizations that could not be reconciled so far. On the practical side, while ILP solutions for natural genomes typically perform well on telomere to telomere resolved genomes, they have been shown in recent years to quickly loose performance on genomes with a large number of contigs or linear chromosomes. This has been linked to a particular technique, namely capping. Simply put, capping circularizes linear chromosomes by concatenating them during solving time, increasing the solution space of the ILP superexponentially. Recently, we introduced a new conceptualization of the DCJ-indel model within the context of another rearrangement problem. In this manuscript, we will apply this new conceptualization to the distance problem. In doing this, we uncover the relation between the disparate conceptualizations of the DCJ-indel model. We are also able to derive an ILP solution to the distance problem that does not rely on capping. This solution significantly improves upon the performance of previou

关键词： Comparative genomics Genome rearrangement Double-cut-and-join Indels integer linear programming Capping

来源：评论

学校读者我要写书评

暂无评论

Madusa: mobile application demo generation based on usage scenarios

引用

AUTOMATED SOFTWARE ENGINEERING 2023年第1期30卷 1-25页

作者： Lee, Jaehyung Cho, Hangyeol Lee, Woosuk Hanyang Univ Dept Comp Sci & Engn Ansan South Korea

Mobile applications have grown rapidly in size. This dramatic increases in size and complexity make mobile applications less accessible to a broader scope of users. The prevailing approach for better accessibility of mobile applications is to manually reimplement slimmed versions with a small but representative portion of a regular original app. Unfortunately, this approach imposes significant burden on developers. We propose a system called Madusa to enable developers to effectively customize and reduce their mobile applications for Android. Madusa takes as input an original app, an upper bound on the size of a reduced version, and usage scenarios as a high-level specification of its desired core functionality. The output is a reduced version of the app that is still correct with respect to the specification while not exceeding the size limit. Madusa constructs a graph representing dependencies among methods and resources and identifies a sub-part of the graph using integer linear programming to generate a reduced version that exhibits behaviors as similar as possible to the original app. Our experimental evaluation on a suite of 19 Android apps available on Google Play Store. Madusa effectively converges to the desired simplified apps by reducing the app size by 40% on average (maximally by 60%). We conclude our approach effectively removes redundant code and resources with respect to given usage scenarios.

关键词： Demo generation Mobile applications integer linear programming Android Static analysis for android

来源：评论

学校读者我要写书评

暂无评论

Mutation-Based Minimal Test Suite Generation for Boolean Expressions

引用

INTERNATIONAL JOURNAL OF SOFTWARE ENGINEERING AND KNOWLEDGE ENGINEERING 2023年第6期33卷 865-884页

作者： Ayav, Tolga Belli, Fevzi Izmir Inst Technol Dept Comp Engn TR-35430 Izmir Turkiye Univ Paderborn Dept Software Engn Paderborn Germany

Boolean expressions are highly involved in control flows of programs and software specifications. Coverage criteria for Boolean expressions aim at producing minimal test suites to detect software faults. There exist various testing criteria, efficiency of which is usually evaluated through mutation analysis. This paper proposes an integer programming-based minimal test suite generation technique relying on mutation analysis. The proposed technique also takes into account the cost of fault detection. The technique is optimal such that the resulting test suite guarantees to detect all the mutants under given fault assumptions, while maximizing the average percentage of fault detection of a test suite. Therefore, the approach presented can also be considered as a reference method to check the efficiency of any common technique. The method is evaluated using four well-known real benchmark sets of Boolean expressions and is also exemplary compared with MCDC criterion. The results show that the test suites generated by the proposed method provide better fault coverage values and faster fault detection.

关键词： Software testing fault-based testing Boolean functions mutation analysis integer linear programming

来源：评论

学校读者我要写书评

暂无评论

An Intelligent Optimization Method of Reinforcing Bar Cutting for Construction Site

引用

Computer Modeling in Engineering & Sciences 2023年第1期134卷 637-655页

作者： Zhaoxi Ma Qin Zhao Tianyou Cang Zongjian Li Yiyun Zhu Xinhong Hei Department of Civil Engineering and Architecture Xi’an University of TechnologyXi’an710048China State Key Laboratory of Rail Transit Engineering Informatization(FSDI) Xi’an710043China Department of Computer Science and Engineering Xi’an University of TechnologyXi’an710048China

To meet the requirements of specifications,intelligent optimization of steel bar blanking can improve resource utilization and promote the intelligent development of sustainable *** one of the most important building materials in construction engineering,reinforcing bars(rebar)account for more than 30%of the cost in civil engineering.A significant amount of cutting waste is generated during the construction *** cutting waste increases construction costs and generates a considerable amount of CO_(2)*** study aimed to develop an optimization algorithm for steel bar blanking that can be used in the intelligent optimization of steel bar engineering to realize sustainable *** the proposed algorithm,the integer linear programming algorithm was applied to solve the *** was combined with the statistical method,a greedy strategy was introduced,and a method for determining the dynamic critical threshold was developed to ensure the accuracy of large-scale data *** proposed algorithm was verified through a case study;the results confirmed that the rebar loss rate of the proposed method was reduced by 9.124%compared with that of traditional distributed processing of steel bars,reducing CO_(2)emissions and saving construction *** the scale of a project increases,the calculation quality of the optimization algorithmfor steel bar blanking proposed also increases,while maintaining high calculation *** the results of this study are applied in practice,they can be used as a sustainable foundation for building informatization and intelligent development.

关键词： Building construction rebar work cutting stock problem optimization algorithm integer linear programming

来源：评论

学校读者我要写书评

暂无评论

A Branch-and-Cut algorithm for the multiple Steiner TSP with order constraints

引用

ANNALS OF OPERATIONS RESEARCH 2024年 1-29页

作者： Taktak, Raouia Univ Sfax ISIMS Sfax Tunisia Ctr Rech Numer Sfax Smrts Sfax Tunisia

This paper deals with a variant of the traveling salesman problem (TSP), called the multiple Steiner TSP with order constraints. This consists, given an undirected graph with nonnegative weights on the edges, and a set of salesmen such that with each salesman is associated a set of ordered terminals, in finding a minimum-cost subgraph containing for each salesman a tour going in order through its terminals. We propose an integer linear programming (ILP) formulation for the problem. We identify new families of valid inequalities and devise separation algorithms. Using this, we propose a Branch-and-Cut algorithm. The efficiency of our algorithm is shown through an extensive computational study.

关键词： Steiner TSP Order constraints integer linear programming Valid inequality Branch-and-Cut

来源：评论

学校读者我要写书评

暂无评论

HASCH - A high-throughput amplicon-based SNP-platform for medicinal cannabis and industrial hemp genotyping applications

引用

BMC GENOMICS 2024年第1期25卷 1页

作者： Mansueto, Locedie Tandayu, Erwin Mieog, Jos Garcia-de Heer, Lennard Das, Rekhamani Burn, Adam Mauleon, Ramil Kretzschmar, Tobias Southern Cross Univ Fac Sci & Engn Southern Cross Plant Sci 1 Mil Rd East Lismore NSW 2480 Australia Int Rice Res Inst Pili Dr Laguna Philippines

Background Cannabis sativa is seeing a global resurgence as a food, fiber and medicinal crop for industrial hemp and medicinal Cannabis industries respectively. However, a widespread moratorium on the use and research of C. sativa throughout most of the 20th century has seen the development of improved cultivars for specific end uses lag behind that of conventional crops. While C. sativa research and development has seen significant investments in the recent past, resulting in a suite of publicly available genomic resources and tools, a versatile and cost-effective mid-density genotyping platform for applied purposes in breeding and pre-breeding is lacking. Here we report on a first mid-density fixed-target SNP platform for C. sativa. Results The High-throughput Amplicon-based SNP-platform for medicinal Cannabis and industrial Hemp (HASCH) was designed using a combination of filtering and integer linear programming on publicly available whole-genome sequencing and RNA sequencing data, supplemented with in-house generated genotyping-by-sequencing (GBS) data. HASCH contains 1,504 genome-wide targets of high call rate (97% mean) and even distribution across the genome, designed to be highly informative (> 0.3 minor allele frequency) across both medicinal cannabis and industrial hemp gene pools. Average numbers of mismatch SNP between any two accessions were 251 for medicinal cannabis (N = 116) and 272 for industrial hemp (N = 87). Comparing HASCH data with corresponding GBS data on a collection of diverse C. sativa accessions demonstrated high concordance and resulted in comparable phylogenies and genetic distance matrices. Using HASCH on a segregating F2 population derived from a cross between a tetrahydrocannabinol (THC)-dominant and a cannabidiol (CBD)-dominant accession resulted in a genetic map consisting of 310 markers, comprising 10 linkage groups and a total size of 582.7 cM. Quantitative Trait Locus (QTL) mapping identified a major QTL for CBD content on chrom

关键词： Cannabis sativa Genotyping SNP Plant breeding Quantitative trait loci integer linear programming Genetic fingerprints

来源：评论

学校读者我要写书评

暂无评论

A Global Optimal Gaussian Mixture Reduction Approach Based on integer linear programming

引用

CHINESE JOURNAL OF ELECTRONICS 2013年第4期22卷 763-768页

作者： Zhu Hongyan Zhai Qiaozhu Xi An Jiao Tong Univ Sch Elect & Informat Engn Xian 710049 Peoples R China Xi An Jiao Tong Univ Minist Educ Key Lab Intelligent Networks & Network Secur Xian 710049 Peoples R China

In many applications, the Gaussian mixture serves as an important probabilistic representation of the system state. A global optimal Gaussian mixture reduction (GMR) approach based on integer linear programming (ILP) is developed in this paper. Firstly, a Gaussian base set is constructed with partial merging of components of the original mixture. Secondly, by introducing auxiliary variables reasonably, the original problem of selecting the best candidates from the given Gaussian base set is formulated as an ILP problem. Finally, a global optimal solution to GMR is obtained by solving the ILP problem. The global optimum property enables it as a basis for performance comparison with different GMR algorithms.

关键词： Gaussian mixture reduction integer linear programming Component merging Integral squared difference Global optimal solution

来源：评论

学校读者我要写书评

暂无评论

Controller Placement Approach with Criteria Balance in SDN networks

引用

JOURNAL OF HIGH SPEED NETWORKS 2024年第4期30卷 497-516页

作者： Fellah, Soumaya Fellah, Khadidja Natl Polytech Sch Oran Maurice Audin Oran Algeria Oran Grad Sch Econ Oran Algeria

Software Defined Network (SDN) is an emerging technology that centralizes network control and automates network management by separating the data plane from the control plane. The control plane is a set of controllers that manage the network switches. The crucial problem of positioning these controllers is known as the Controller Placement Problem (CPP). The optimal controllers positioning is very constrained and affects the different network performance parameters, such as, controller-to-switch latency, inter-controller latency, number of hops between controller and switch and inter-controller. In this paper, we study the impact of optimizing some parameters on the others, we have developed different approaches, and each considers one or two parameters. Moreover, we propose a balanced optimization approach that considers the various network performance parameters. We formulate the problem as an integer linear programming model that considers all parameters using the Lexicographic Multi-objective optimization method. By ensuring a balance between all parameters, network performance is significantly improved. The obtained results reveal that our approach is more inclusive and provides very interesting results.

关键词： Controller placement SDN lexicographic optimization latency integer linear programming

来源：评论

学校读者我要写书评

暂无评论

A network model to optimally group road maintenance interventions for work zone development

引用

STRUCTURE AND INFRASTRUCTURE ENGINEERING 2023年第7期19卷 1007-1023页

作者： Xu, Zhepu Burkhalter, Marcel Adey, Bryan T. Yang, Qun Shanghai Inst Technol Dept Railway Transportat Shanghai Peoples R China Inst Construct & Infrastruct Management Swiss Fed Inst Technol Zurich Infrastruct Management Grp Zurich Switzerland Tongji Univ Key Lab Rd & Traff Engn Minist Educ Shanghai Peoples R China

One of the main tasks of road managers is to plan maintenance interventions, which is currently in practice often done using a simple ranking-based method. However, an increasing number of researchers are focusing their efforts on supporting the planning process using operations research models. Models that have been developed can optimally group maintenance interventions: (1) in a single work zone, taking into consideration both work zone and asset related costs, and (2) in multiple work zones, taking into consideration only asset-related costs. In this paper, a new operation research model is developed to optimally group maintenance interventions in multiple work zones, taking into consideration both work zone and asset-related costs. The new model is used to optimally group maintenance interventions for a road network located in Fujian province in China. The improvement obtained from using the new model is compared to the result determined using an operation research model that can only determine one optimal group of intervention at a time, and one determined using a commonly used ranking-based method. It is shown that the new model results in the highest net-benefit, and that both operation research models result in higher net benefits than the ranking-based method.

关键词： integer linear programming infrastructure management maintenance planning interventions network model optimization work zone

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：