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

COMPLEXITY OF FINDING ALPHABET INDEXING

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 1995年第1期E78D卷 13-18页

作者： SHIMOZONO, S MIYANO, S Kyushu Inst of Technology Iizukashi Japan

For two finite disjoint sets P and Q of strings over an alphabet SIGMA, an alphabet indexing psi for P,Q by an indexing alphabet GAMMA with \GAMMA\ GAMMA satisfying psi(P) and psi(Q) = empty set, where psi: SIGMA* --... 详细信息

For two finite disjoint sets P and Q of strings over an alphabet SIGMA, an alphabet indexing psi for P,Q by an indexing alphabet GAMMA with \GAMMA\ < \SIGMA\ is a mapping psi: SIGMA --> GAMMA satisfying psi(P) and psi(Q) = empty set, where psi: SIGMA* --> GAMMA* is the homomorphism derived from psi. We defined this notion through experiments of knowledge acquisition from amino acid sequences of proteins by learning algorithms. This paper analyzes the complexity of finding an alphabet indexing. We first show that the problem is NP-complete. Then we give a local search algorithm for this problem and show a result on PLS-completeness.

关键词： algorithm AND COMPUTATIONAL COMPLEXITY ALPHABET INDEXING local search algorithm NP-COMPLETE PLS-COMPLETE

来源：评论

学校读者我要写书评

暂无评论

Flexible job shop scheduling with preventive maintenance consideration

引用

JOURNAL OF INTELLIGENT MANUFACTURING 2024年第4期35卷 1517-1539页

作者： Wocker, Michael Mario Ostermeier, Frederik Ferid Wanninger, Tobias Zwinkau, Ronny Deuse, Jochen TU Dortmund Univ Inst Prod Syst Leonhard Euler Str 5 D-44227 Dortmund Germany Univ Technol Sydney Ctr Adv Mfg Sydney Australia Tech Univ Munich Lab Prod Dev & Lightweight Design Boltzmannstr 15 D-85748 Munich Germany BMW Grp Knorrstr 147 D-80937 Munich Germany BMW Grp Bremer Str 6 D-80807 Munich Germany

In highly automated manufacturing systems running 24/7, preventive maintenance activities need to be executed during production times. Flexible job shops with several identical machines generally bear the potential to compensate temporary machine unavailability times caused by preventive maintenance without a considerable increase of the makespan due to machine paralleling. However, this requires sophisticated scheduling of manufacturing jobs and the assignment of maintenance activities over the scheduling horizon. This work, therefore, introduces a mixed-integer program that models both job scheduling and maintenance activity assignment. A local search algorithm is developed to solve both problems in an integrated way. Numerical studies are carried out based on data from a real flexible job shop in the automotive industry with 78 machines and four products. The results show that joint job scheduling and maintenance activity assignment is required to obtain a makespan similar to the makespan without maintenance consideration. Non-sophisticated scheduling of maintenance windows can increase the makespan by more than 20 percentage points compared to sophisticated scheduling. Besides, we show that only a limited amount of maintenance activities can be compensated and that higher unavailability times will inevitably lead to detrimental effects on the makespan unless maintenance worker capacity is increased.

关键词： Manufacturing Flexible job shop Scheduling Preventive maintenance local search algorithm

来源：评论

学校读者我要写书评

暂无评论

Incorporating Ab Initio energy into threading approaches for protein structure prediction

引用

BMC BIOINFORMATICS 2011年第s1期12卷 S54-S54页

作者： Shao, Mingfu Wang, Sheng Wang, Chao Yuan, Xiongying Li, Shuai Cheng Zheng, Weimou Bu, Dongbo Chinese Acad Sci Inst Theoret Phys Beijing 100080 Peoples R China Chinese Acad Sci Inst Comp Technol Beijing 100080 Peoples R China Int Comp Sci Inst Berkeley CA 94704 USA

Background: Native structures of proteins are formed essentially due to the combining effects of local and distant (in the sense of sequence) interactions among residues. These interaction information are, explicitly or implicitly, encoded into the scoring function in protein structure prediction approaches-threading approaches usually measure an alignment in the sense that how well a sequence adopts an existing structure;while the energy functions in Ab Initio methods are designed to measure how likely a conformation is near-native. Encouraging progress has been observed in structure refinement where knowledge-based or physics-based potentials are designed to capture distant interactions. Thus, it is interesting to investigate whether distant interaction information captured by the Ab Initio energy function can be used to improve threading, especially for the weakly/distant homologous templates. Results: In this paper, we investigate the possibility to improve alignment-generating through incorporating distant interaction information into the alignment scoring function in a nontrivial approach. Specifically, the distant interaction information is introduced through employing an Ab Initio energy function to evaluate the "partial" decoy built from an alignment. Subsequently, a local search algorithm is utilized to optimize the scoring function. Experimental results demonstrate that with distant interaction items, the quality of generated alignments are improved on 68 out of 127 query-template pairs in Prosup benchmark. In addition, compared with state-to-art threading methods, our method performs better on alignment accuracy comparison. Conclusions: Incorporating Ab Initio energy functions into threading can greatly improve alignment accuracy.

关键词： local search algorithm Protein Structure Prediction Alignment Accuracy Reference Alignment local Item

来源：评论

学校读者我要写书评

暂无评论

Smart City Response to Homelessness

引用

IEEE ACCESS 2020年 8卷 11380-11392页

作者： Khayyatkhoshnevis, Pedram Choudhury, Salimur Latimer, Eric Mago, Vijay Lakehead Univ Dept Comp Sci Thunder Bay ON P7B 5E1 Canada McGill Univ Dept Psychiat Montreal PQ H3A 0G4 Canada

The smart city is a concept of utilizing digital technologies to improve and enhance the lives of a city's inhabitants. This concept has been the subject of increasing interest over the past few years. However, most studies address improving aspects of a city's infrastructure, such as information security, privacy, communication networks, government, and transportation. Noticeably absent from the subject matter of these studies are social problems, such as poverty and homelessness. In this paper, we explore how technology can be harnessed to mitigate homelessness. We introduce eight novel heuristic algorithms that create a desirable homeless-to-housing assignment with regards to homeless individuals' characteristics and the nature of services. We discuss the efficiency of each of the algorithms through simulations. Our best performing algorithm obtains 92% accuracy in comparison to the optimal solution and 99.7% fairness. The algorithms are compared in terms of execution time, solution accuracy, fairness, and the relative difference with the optimal solution of this NP-hard problem.

关键词： Smart cities homelessness social systems greedy algorithm local search algorithm

来源：评论

学校读者我要写书评

暂无评论

Piecewise-convex maximization problems: algorithm and computational experiments

引用

JOURNAL OF GLOBAL OPTIMIZATION 2002年第1期24卷 61-77页

作者： Fortin, D Tsevendorj, I Ctr Math & Informat LIM F-13453 Marseille 13 France Inst Natl Rech Informat & Automat F-78153 Le Chesnay France

A function F : R-n --> R is called a piecewise convex function if it can be decomposed into F(x) = min {f (j)(x) | j is an element of M}, where f(j) : R-n --> R is convex for all j is an element of M = {1 2..,m}. In this article, we provide an algorithm for solving max F( x) subject to x D, which is based on global optimality conditions. We report first computational experiments on small examples and open up some issues to improve the checking of optimality conditions.

关键词： optimality conditions global search algorithm local search algorithm nonconvex and nonsmooth problem piecewise convex function

来源：评论

学校读者我要写书评

暂无评论

Sensor deployment optimization methods to achieve both coverage and connectivity in wireless sensor networks

引用

COMPUTERS & OPERATIONS REsearch 2015年第Jul.期59卷 11-21页

作者： Rebai, Maher Le Berre, Matthieu Snoussi, Hichem Hnaien, Faicel Khoukhi, Lyes Univ Technol Troyes Inst Charles Delaunay UMR CNRS 6279 F-10010 Troyes France

In this study, we aim to cover a sensing area by deploying a minimum number of wireless sensors while maintaining the connectivity between the deployed sensors. The problem may be reduced to a two-dimensional critical coverage problem which is an NP-Complete problem. We develop an integer linear programming model to solve the problem optimally. We also propose a local search (LS) algorithm and a genetic algorithm (GA) as approximate methods. We verify by computational experiments that the integer linear model, using Cplex, is able to provide an optimal solution of all our small and medium size problems. We also show that the proposed methods outperform some regular sensor deployment patterns. (C) 2014 Elsevier Ltd. All rights reserved.

关键词： Wireless sensor networks Coverage problem Connectivity Integer linear model Genetic algorithm local search algorithm

来源：评论

学校读者我要写书评

暂无评论

Frequency veering of railway vehicle systems and its mapping to vibration characteristics

引用

MULTIBODY SYSTEM DYNAMICS 2024年第4期62卷 463-492页

作者： Liu, Guangyu Gong, Dao Zhou, Jinsong Ren, Lihui Wang, Zegen Deng, Xin Sun, Weiguang You, Taiwen Tongji Univ Inst Rail Transit 4800 Cao An Rd Shanghai 201804 Peoples R China Lanzhou Jiaotong Univ Sch Mech Engn 88 Anning West Rd Lanzhou 730070 Peoples R China

Frequency veering is a phenomenon that occurs during modal parameter changes and is closely related to the response characteristics of the system. First, by taking a system with simple DOFs as the research object, the variations in the modal damping ratio and mode shape in the process of frequency veering are analysed, and a criterion for identifying this phenomenon is preliminarily proposed. Then, to explore the modal changes in complex vehicle systems with multiple DOFs, an adaptive modal continuous tracking algorithm based on a local search algorithm is proposed that takes the Euclidean closeness between complex mode shapes as an index. Frequency veering is analysed with the established vehicle system dynamics model (Model I) and reproduced through the SIMPACK model (Model II) for multibody dynamics simulation. The perturbation method is used to analyse the mechanism by which the vehicle system eigenvectors are prone to mutations during frequency veering, and the abnormal changes in the mode shapes during this process are further verified. In addition, two quantitative indices for identifying frequency veering phenomena are proposed based on the modal assurance criterion and mode shape similarity. Finally, the mapping relationship between the frequency veering and vehicle system response is explored. The results indicate that before and after frequency veering, the mode shapes interchange, and in the frequency veering zone, the damping-hopping phenomenon occurs, resulting in a significant decrease in system stability. Corresponding to the phenomena of modal damping ratios and mode shapes, the motion morphology of the vehicle system is clearly observable. Moreover, the response at the DOFs of the car body and bogie are obviously enhanced;these responses are also manifested in the increasing vibrations of the car body and bogie and the deterioration of the vehicle ride quality.

关键词： Railway vehicles Complex mode Euclidean closeness local search algorithm Modal continuous tracking Frequency veering Mutations of eigenvectors Multimode coupling response

来源：评论

学校读者我要写书评

暂无评论

A multi-start algorithm for a balanced real-world Open Vehicle Routing Problem

引用

EUROPEAN JOURNAL OF OPERATIONAL REsearch 2014年第1期238卷 104-113页

作者： Lopez-Sanchez, A. D. Hernandez-Diaz, A. G. Vigo, D. Caballero, R. Molina, J. Pablo de Olavide Univ Seville 41013 Spain Univ Bologna DEI Guglielmo Marconi I-40136 Bologna Italy Univ Malaga E-29071 Malaga Spain

The aim of this paper is to solve a real-world problem proposed by an international company operating in Spain and modeled as a variant of the Open Vehicle Routing Problem in which the makespan, i.e., the maximum time spent on the vehicle by one person, must be minimized. A competitive multi-start algorithm, able to obtain high quality solutions within reasonable computing time is proposed. The effectiveness of the algorithm is analyzed through computational testing on a set of 19 school-bus routing benchmark problems from the literature, and on 9 hard real-world problem instances. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Open Vehicle Routing Problem Multi-start algorithm local search algorithm

来源：评论

学校读者我要写书评

暂无评论

algorithm and peer-to-peer negotiation strategies for train dispatching problems in railway bottleneck sections

引用

IET INTELLIGENT TRANSPORT SYSTEMS 2019年第11期13卷 1717-1725页

作者： Liu, Jin Chen, Lei Roberts, Clive Nicholson, Gemma Ai, Bo Univ Birmingham Sch Engn Birmingham Ctr Railway Res & Educ Birmingham B15 2TT W Midlands England Beijing Jiaotong Univ State Key Lab Rail Traff Control & Safety Beijing 100044 Peoples R China

Train delays occur often in daily railway operations due to a variety of initiating incidents. On a heavily loaded mainline railway, a single train delay may lead to a series of secondary delays across the network. In this study, the authors describe a peer-to-peer system to solve train rescheduling problems in railway network bottlenecks. A designed Genetic algorithm is chosen as the local search algorithm on each side. Based on the local search algorithm, different negotiation protocols are raised to find globally feasible solutions. The proposed approach is tested in a railway bottleneck section in the UK, and the computational result is compared with a centralised method to show its performance in terms of computation time and optimality.

关键词： railways genetic algorithms rail traffic delays integer programming scheduling train rescheduling problems railway network bottlenecks designed Genetic algorithm local search algorithm different negotiation protocols railway bottleneck section peer-to-peer negotiation strategies train dispatching problems train delays daily railway operations initiating incidents heavily loaded mainline railway single train delay secondary delays peer-to-peer system

来源：评论

学校读者我要写书评

暂无评论

Knowledge-based modeling for disruption management in urban distribution

引用

EXPERT SYSTEMS WITH APPLICATIONS 2012年第1期39卷 906-916页

作者： Hu, Xiangpei Sun, Lijun Dalian Univ Technol Sch Management & Econ Inst Syst Engn Dalian 116023 Liaoning Provin Peoples R China

Disruption management in urban distribution is the process of achieving a new distribution plan in order to respond to a disruption in real time. Experienced schedulers can respond to disruptions quickly with common sense and past experiences, but they often achieve the new distribution plan by a fuzzy, sometimes inconsistent, and not well-understood way. The method is limited when the problem becomes large scale or more complicated. In this case, optimization techniques consisting of models and algorithms may complement it. However, as the distribution system's state changes constantly with the plan-executing process and disruptions are diversified, real-time modeling is very difficult. Hence in order to achieve the real-time modeling process, the research in the paper focuses on a knowledge-based modeling method, which combines the knowledge of experienced schedulers with the OR knowledge concerning models and algorithms. Policies, algorithms and models are represented by proper knowledge representation schemes in order to support automated or semi-automated modeling by computers. The modeling process is demonstrated by a case to show how the different kinds of knowledge representation schemes cooperate with each other to support the modeling process. In the knowledge-based modeling process, based on the knowledge of experienced schedulers, a qualitative policy for handling the disruption based on the current distribution system's state is achieved firstly;and then based on OR knowledge, the corresponding model and algorithm are constructed to quantitatively optimize the policy. The integration of the two kinds of knowledge not only effectively supports the real-time modeling process, but also combines the advantages of both to achieve more practical and scientific solutions to different kinds of disruptions occurring under different distribution system's states. (C) 2011 Elsevier Ltd. All rights reserved.

关键词： Knowledge-based modeling Knowledge representation Disruption management local search algorithm Vehicle Routing Problem (VRP)

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：