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

An accelerated approach for solving fuzzy relation equations with a linear objective function

IEEE TRANSACTIONS ON FUZZY SYSTEMS 2002年第4期10卷 552-558页

作者： Wu, YK Guu, SM Liu, JYC Van Nun Inst Technol Dept Ind Management Tao Yuan 320 Taiwan Yuan Ze Univ Dept Informat Management Tao Yuan 320 Taiwan

In literature, the optimization model with a linear objective function subject to fuzzy relation equations has been converted into a 0-1 integer programming problem by Fang and Li. They proposed a jump-tracking branch-and-bound method to solve this 0-1 integer programming problem. In this paper, we propose an upper bound for the optimal objective value. Based on this upper bound and rearranging the structure of the problem, we present a backward jump-tracking branch-and-bound scheme for solving this optimization problem. A numerical example is provided to illustrate our scheme. Furthermore, testing examples show that the performance of our scheme is superior to the procedure in the paper by Fang and Li. Several testing examples do indeed show that our initial upper bound is sharp.

关键词： branch-and-bound method fuzzy relation equations jump-tracking technique max-min composition

来源：评论

学校读者我要写书评

暂无评论

Solving a special class of large-scale fuzzy multiobjective integer linear programming problems

引用

FUZZY SETS AND SYSTEMS 1999年第3期107卷 289-297页

作者： Osman, MS Saad, OM Hasan, AG Helwan Univ Fac Sci Dept Math Cairo Egypt Higher Technol Inst Cairo Egypt Ain Shams Univ Coll Women Cairo Egypt

We present a method useful in solving a special class of large-scale multiobjective integer problems depending on the decomposition algorithm. These problems involve fuzzy parameters on the right-hand side of the independent constraints. The presented solution method is based upon a combination of the decomposition algorithm coupled with the weighting method together with the branch-and-bound method. An illustrative numerical example is given to clarify the theory and the method discussed in this paper. (C) 1999 Elsevier Science B.V. All rights reserved.

关键词： multiobjective linear programming decomposition algorithm integer programming fuzzy parameters fuzzy numbers weighting method branch-and-bound method

来源：评论

学校读者我要写书评

暂无评论

HBBA: hybrid algorithm for buffer allocation in tandem production lines

引用

JOURNAL OF INTELLIGENT MANUFACTURING 2007年第3期18卷 411-420页

作者： Dolgui, Alexandre Eremeev, Anton V. Sigaev, Viatcheslav S. Ecole Natl Super Mines Div Ind Engn & Comp Sci F-42023 St Etienne 2 France Sobolev Inst Math Omsk Branch Discrete Optimizat Lab Omsk Russia Omsk State Univ Dept Math Omsk 644077 Russia

In this paper, we consider the problem of buffer space allocation for a tandem production line with unreliable machines. This problem has various formulations all aiming to answer the question: how much buffer storage to allocate between the processing stations? Many authors use the knapsack-type formulation of this problem. We investigate the problem with a broader statement. The criterion depends on the average steady-state production rate of the line and the buffer equipment acquisition cost. We evaluate black-box complexity of this problem and propose a hybrid optimization algorithm (HBBA), combining the genetic and branch-and-bound approaches. HBBA is excellent in computational time. HBBA uses a Markov model aggregation technique for goal function evaluation. Nevertheless, HBBA is more general and can be used with other production rate evaluation techniques.

关键词： production line buffer allocation NP completeness black-box complexity genetic algorithm branch-and-bound method hybrid algorithm

来源：评论

学校读者我要写书评

暂无评论

Minimizing tardiness in a two-machine flow-shop

引用

COMPUTERS & OPERATIONS RESEARCH 2002年第7期29卷 869-885页

作者： Pan, JCH Chen, JS Chao, CM Natl Taiwan Univ Sci & Technol Dept Ind Management Sect 4 Taipei 106 Taiwan Far E Coll Dept Ind Engn & Management Hsin Shih 744 Taiwan

The two-machine flow-shop scheduling problem with the objective of minimizing total tardiness is considered in this paper. Dominance criteria are developed to establish the precedence constraints between jobs in an optimal schedule. A lower bound on the total tardiness of the problem is derived by constructing the sequence of jobs from front to back to simplify the bounding procedure. A branch-and-bound algorithm incorporating these properties is proposed to expedite the search for an optimal sequence. Computational experiments are conducted and the results demonstrate that the proposed algorithm surpasses an existing one in terms of both computation times and sizes of the problems solved.

关键词： scheduling two-machine flow-shop total tardiness branch-and-bound method

来源：评论

学校读者我要写书评

暂无评论

Fuzzy job shop scheduling

引用

INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS 1996年第1-2期44卷 45-51页

作者： Kuroda, M Wang, Z Department of Industrial and Systems Engineering Aoyama Gakuin University Tokyo Japan. Shibuya Optical Co. Ltd. Tokyo Japan

This paper discusses job shop scheduling from the viewpoint of dealing with fuzziness inherent in the problem. Some static problems with fuzzy information regarding due dates and/or operation times are solved using a branch-and-bound algorithm and the meaning of solving such scheduling problems is described. The method for handling dynamic problems with fuzzy information, i.e., fuzzy job shop simulation is also discussed, with the intention of applying the fuzzy theory to real-life job shop scheduling.

关键词： job shop scheduling fuzzy information static problem dynamic problem branch-and-bound method simulation

来源：评论

学校读者我要写书评

暂无评论

Commercial territory design planning with realignment and disjoint assignment requirements

引用

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE 2013年第3期41卷 525-535页

作者： Rios-Mercado, Roger Z. Fabian Lopez-Perez, J. Univ Autonoma Nuevo Leon Grad Program Syst Engn San Nicolas De Los Garza 66450 NL Mexico Univ Autonoma Nuevo Leon Grad Program Management Sci CEDEEM San Nicolas De Los Garza 66450 NL Mexico

A territory design problem motivated by a bottled beverage distribution company is addressed. The problem consists of finding a partition of the entire set of city blocks into a given number of territories subject to several planning criteria. Each unit has three measurable activities associated to it, namely, number of customers, product demand, and workload. The plan must satisfy planning criteria such as territory compactness, territory balancing with respect to each of the block activity measures, and territory connectivity, meaning that there must exist a path between any pair of units in a territory totally contained in it. In addition, there are some disjoint assignment requirements establishing that some specified units must be assigned to different territories, and a similarity with existing plan requirement. An optimal design is one that minimizes a measure of territory dispersion and similarity with existing design. A mixed-integer linear programming model is presented. This model is unique in the commercial territory design literature as it incorporates the disjoint assignment requirements and similarity with existing plan. Previous methods developed for related commercial districting problems are not applicable. A solution procedure based on an iterative cut generation strategy within a branch-and-bound framework is proposed. The procedure aims at solving large-scale instances by incorporating several algorithmic strategies that helped reduce the problem size. These strategies are evaluated and tested on some real-world instances of 5000 and 10,000 basic units. The empirical results show the effectiveness of the proposed method and strategies in finding near optimal solutions to these very large instances at a reasonably small computational effort. (C) 2012 Elsevier Ltd. All rights reserved.

关键词： Bottled beverage distribution Commercial districting Mixed-integer linear programming branch-and-bound method Heuristics

来源：评论

学校读者我要写书评

暂无评论

A PARALLEL ALGORITHM FOR THE 0-1 KNAPSACK-PROBLEM

引用

INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING 1992年第5期21卷 349-362页

作者： LOOTS, W SMITH, THC RAND AFRIKAANS UNIV DEPT COMP SCI JOHANNESBURG 2000 SOUTH AFRICA

Research efforts on parallel exact algorithms for the 0-1 knapsack problem have up to now concentrated on solving small problems (at most 1,000 objects) and in many cases results have only been obtained by simulation of the parallel algorithm. After a brief review of a well known sequential branch-and-bound algorithm we discuss a new parallel algorithm for the 0-1 knapsack problem which exploits the potential parallelism that exists during the backtracking steps of the branch-and-bound algorithm. We report results for our parallel algorithm on a transputer network for problems with up to 20,000 objects. The speedup obtained is nearly linear for 2, 4, and 8 processors except when there is a strong correlation between the profit and weight of the objects.

关键词： KNAPSACK PROBLEM PARALLEL PROCESSING branch-and-bound method TRANSPUTER

来源：评论

学校读者我要写书评

暂无评论

Exact solution for minimization of root mean square deviation with G-RMSD to determine molecular similarity

引用

BULLETIN OF THE CHEMICAL SOCIETY OF JAPAN 2024年第4期97卷 uoae037-uoae037页

作者： Nabika, Tomohiro Iwata, Satoru Satoh, Hiroko Univ Tokyo Dept Frontier Sci 5-1-5 Kashiwanoha Kashiwa Kashiwa Chiba 2778561 Japan Univ Tokyo Dept Math Informat 7-3-1 HongoBunkyo Ku Tokyo 1138656 Japan Hokkaido Univ Inst Chem React Design & Discovery Kita 21 Nishi 10Kita Ku Sapporo Hokkaido 0010021 Japan Univ Zurich Dept Chem Winterthurerstr 190 CH-8057 Zurich Switzerland Res Org Informat & Syst ROIS Joint Support Ctr Data Sci Res 10-3 Midori Cho Tachikawa Tokyo 1900014 Japan

Generalized root mean square deviation (G-RMSD) is an optimization method for three-dimensional molecular similarity determination. It calculates the minimum value of RMSD among all the possible one-to-one matchings between the atoms and positions of the molecules. The first paper on G-RMSD introduced two approaches called alternating optimization (AO) and tangent space relaxation (TSR) methods, which give local optimum solutions. We propose here a new method of G-RMSD using a branch-and-bound method (BnB) on isometric transformations, called IsometryOpt, which is mathematically proven to give an exact G-RMSD index, i.e. this method can reach the global optimum solution. The performance of IsometryOpt was compared to AO and TSR, as well as the MatchFastOpt method. IsometryOpt shows better performance than MatchFastOpt for molecules with the same number of atoms. AO and TSR fail to reach exact values in some cases. We also have developed two improved methods to search for all possible matches of a substructure in one or more molecules. One is called IsometrySearch, which uses BnB on isometric transformations. The other is a variant version of MatchFPT, called MatchFPT-delta. Computer experiments indicate that MatchFPT-delta performs better than MatchFPT and IsometrySearch. Generalized root mean square deviation (G-RMSD) is an optimization method for three-dimensional molecular similarity determination. It calculates the minimum RMSD values without fixing both, atom mapping and superimposition. We propose a new method of G-RMSD using a branch-and-bound method which is mathematically proven to give an exact solution of the G-RMSD index.

关键词： branch-and-bound method molecular similarity RMSD minimization root mean square deviation (RMSD)

来源：评论

学校读者我要写书评

暂无评论

A Hybrid Exact Algorithm for the Asymmetric Traveling Salesman Problem: Construction and a Statistical Study of Computational Efficiency

引用

AUTOMATION AND REMOTE CONTROL 2019年第11期80卷 2054-2067页

作者： Zhukova, G. N. Ul'yanov, M., V Fomichev, M., I Natl Res Univ Higher Sch Econ Moscow Russia Russian Acad Sci Trapeznikov Inst Control Sci Moscow Russia Moscow MV Lomonosov State Univ Moscow Russia

We present the results of a comparative statistical analysis of the time for solving the asymmetric traveling salesman problem (ATSP) with the branch-and-bound method (without precalculation of the tour) and with a hybrid method. The hybrid method consists of the Lin-Kernighan-Helsgaun approximate algorithm used to calculate the initial tour and the branch-and-bound method. We show that using an approximate solution found with the Lin-Kernighan-Helsgaun algorithm can significantly reduce the search time for the exact solution to the traveling salesman problem using the branch-and-bound method for problems from a certain class. We construct a prediction of the search time for the exact solution by the branchand- bound method and by the hybrid algorithm. A computational experiment has shown that the proportion of tasks solved faster by the hybrid algorithm than by the branch-and-bound method grows with increasing problem dimension.

关键词： traveling salesman problem branch-and-bound method approximation of a probability distribution quantile of a probability distribution probabilistic forecasting of time

来源：评论

学校读者我要写书评

暂无评论

DATAPATH SCHEDULING FOR BEHAVIORAL DESCRIPTION WITH CONDITIONAL branchES

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 1994年第12期E77A卷 1999-2009页

作者： YAMADA, A YAMAZAKI, T ISHIURA, N SHIRAKAWA, I KAMBE, T SHARP CO LTD CTR PRECIS TECHNOL DEV TENRI NARA 632 JAPAN

A new approach is described for the datapath scheduling of behavioral descriptions containing nested conditional branches of arbitrary structures. This paper first investigates such a complex scheduling mechanism, and formulates an optimal scheduling problem as a 0-1 integer programming problem such that given a prescribed number of control steps, the total cost of functional units can be minimized. In this formulation, each constraint is expressed in the form of a Boolean function, which is set equal to 1 or 0 according as the constraint is satisfied or not, respectively, and a satisfiability problem is defined by the product of the Boolean functions. A procedure is then described, which intends to seek an optimal solution by means of a branch-and-bound method on a binary decision diagram representing the satisfiability problem. Experimental results are also shown, which demonstrate that our approach is of more practical use than the existing methods.

关键词： HIGH-LEVEL SYNTHESIS DATAPATH SCHEDULING 0-1 INTEGER PROGRAMMING PROBLEM BINARY DECISION DIAGRAM branch-and-bound method

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：