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

A NEW PARALLEL ALGORITHM FOR THE N-JOB, M-MACHINE FLOWSHOP SCHEDULING PROBLEM

SYSTEMS AND COMPUTERS IN JAPAN 1995年第2期26卷 10-21页

作者： OKAMOTO, S WATANABE, I IIZUKA, H SEIKEI UNIV DEPT INFORMAT SCIMUSASHINOTOKYO 180JAPAN SEIKEI UNIV DEPT IND ENGNMUSASHINOTOKYO 180JAPAN

This paper describes a new parallel algorithm for solving the m-machines, n-jobs flow-shop scheduling problem as well as its implementation on a distributed memory multiprocessor. The algorithm is basically a parallelization of the usual branch-and-bound method. It also takes advantage of the all-search method to keep the efficiency of parallel processing reasonably high when subproblems become smaller than a certain size. The performance evaluation is done by comparing the parallel execution of this algorithm on the nCUBE2 multiprocessor and the sequential execution of the branch-and-bound with depth-first search algorithm. The result shows that the mean speedup ratio for some conditions of the problem is more than the number of processors, and the mean speedup ratio for the conditions on which the sequential executions complete quickly is not smaller than 1.

关键词： PARALLEL ALGORITHM FLOWSHOP SCHEDULING branch-and-bound method NCUBE2

来源：评论

学校读者我要写书评

暂无评论

The branch-and-bound Algorithm for the Traveling Salesman Problem is Not a Direct Algorithm

引用

AUTOMATIC CONTROL AND COMPUTER SCIENCES 2021年第7期55卷 816-826页

作者： Maksimenko, A. N. Demidov Yaroslavl State Univ Yaroslavl 150003 Russia

This article considers the concept of a linear separation direct algorithm introduced by V.A. Bondarenko in 1983. The concept of a direct algorithm is defined using the solution graph of a combinatorial optimization problem. The vertices of this graph are all feasible solutions of the problem. Two solutions are called adjacent if there are input data for which these and only these solutions are optimal. A key feature of direct algorithms is that their complexity is bounded from below by the clique number of the solution graph. In 2015-2018, there were five articles published, the main results of which are estimates of the clique numbers of polyhedron graphs associated with various combinatorial optimization problems. The thesis that the class of direct algorithms is broad and includes many classical combinatorial algorithms, including the branch-and-bound algorithm for the traveling salesman problem proposed by J.D.C. Little, K.G. Murty, D.W. Sweeney, and C. Karel in 1963, was the main motivation for these articles. We show that this algorithm is not a direct algorithm. Earlier, in 2014, the author of this article showed that the Hungarian algorithm for the assignment problem is not a direct algorithm. Therefore, the class of direct algorithms is not as broad as previously assumed.

关键词： branch-and-bound method traveling salesman problem linear decision tree clique number direct algorithm

来源：评论

学校读者我要写书评

暂无评论

A GLOBAL APPROACH FOR GENERAL 0-1 FRACTIONAL-PROGRAMMING

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 1994年第3期73卷 590-596页

作者： LI, HL NATL CHIAO TUNG UNIV INST INFORMAT MANAGEMENT1001 TA HSIEH RDHSINCHU 30050TAIWAN

Current methods of general 0-1 fractional programming (G-FP) can only find the local optimum. This paper proposes a new method of solving G-FP problems by a mixed 0-1 linear program to obtain a global optimum. Given a mixed 0-1 polynomial term xy where x is a 0-1 variable and 0 < y less-than-or-equal-to 1, we develop a theorem to transfer the xy term into a set of mixed 0-1 linear inequalities. Based on this theorem, a G-FP problem can be solved by a branch-and-bound method to obtain the global solution.

关键词： 0-1 FRACTIONAL PROGRAMMING branch-and-bound method

来源：评论

学校读者我要写书评

暂无评论

PRACTICAL MULTIPROCESSOR SCHEDULING ALGORITHMS FOR EFFICIENT PARALLEL PROCESSING

引用

IEEE TRANSACTIONS ON COMPUTERS 1984年第11期33卷 1023-1029页

作者： KASAHARA, H NARITA, S Department of Electrical Engineering Waseda University

First Page of the Article

关键词： Approximation MIMD system This paper describes practical optimization/ approximation algorithms for scheduling a set of partially ordered computational tasks onto a multiprocessor system so that the schedule length will be minimized. Since this problem belongs to the class of "strong" NP-hard problems we must foreclose the possibility of constructing not only pseudopolynomial time optimization algorithms but also fully polynomial time approximation schemes unless P = NP. branch-and-bound method heuristic algorithm multiprocessor scheduling algorithm optimization parallel processing strong NP-hard task graph

来源：评论

学校读者我要写书评

暂无评论

An exact algorithm for factor model in portfolio selection with roundlot constraints

引用

OPTIMIZATION 2009年第3期58卷 305-318页

作者： Sun, X. L. Niu, S. F. Li, D. Fudan Univ Sch Management Dept Management Sci Shanghai 200433 Peoples R China NW Normal Univ Coll Math & Informat Sci Lanzhou 730070 Peoples R China Chinese Univ Hong Kong Dept Syst Engn & Engn Management Shatin Hong Kong Peoples R China

We consider in this article a factor model in portfolio selection with roundlot constraints. Mathematically, this model leads to a quadratic integer programming problem. We exploit the separable structure of the model in order to derive Lagrangian bounds. A branch-and-bound algorithm based on Lagrangian relaxation and continuous relaxation is then developed for solving this model. Computational results are reported for test problems with up to 150 securities.

关键词： portfolio optimization factor model roundlot constraints Lagrangian relaxation continuous relaxation branch-and-bound method

来源：评论

学校读者我要写书评

暂无评论

A SEQUENCING PROBLEM FOR A MIXED-MODEL ASSEMBLY-LINE IN A JIT PRODUCTION SYSTEM

引用

COMPUTERS & INDUSTRIAL ENGINEERING 1994年第1-4期27卷 71-74页

作者： ZHAO, XB OHNO, K NAGOYA INST TECHNOL NAGOYAAICHI 466JAPAN

In an assembly line of a just-in-time (JIT) production system, workers have the power and the responsibility to stop the line when they fail to complete their operations within their work zones. This paper deals with a sequencing problem for the mixed-model assembly conveyor line in the JIT production system. In some environment, the most important criterion is the line stoppage rather than the variation of production rates. The problem is to find an optimal sequence of units that minimizes the total line stoppage time. Lower and upper bounds of the total line stoppage time are derived and the branch-and-bound method is applied to the problem, A numerical example is given.

关键词： JIT MINIMIZING LINE STOPPAGE TIME MIXED-MODEL ASSEMBLY LINE branch-and-bound method

来源：评论

学校读者我要写书评

暂无评论

A quick optimal algorithm for sequencing on one machine to minimize total tardiness

引用

INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS 1999年第3期60-1卷 549-555页

作者： Hirakawa, Y Sci Univ Tokyo Fac Sci & Technol Dept Ind Adm Chiba 2788510 Japan

In considering the problem of sequentially ordering N jobs, it is known that large-scale problems cannot be solved readily in order to find optimality since there are N! possibilities to the schedules. In this paper, a quick optimal algorithm for sequencing jobs processed on one machine to minimize total tardiness is proposed. The optimal algorithm relies upon the branch-and-bound method applied directly to Lawler's decomposition theorem and gives an optimal solution. In the algorithm, special care is given to the calculation procedure and the setup of the upper bound values to shorten the calculation time. (C) 1999 Elsevier Science B.V. All rights reserved.

关键词： branch-and-bound method scheduling sequencing single machine total tardiness

来源：评论

学校读者我要写书评

暂无评论

TWO-DIMENSIONAL LINEAR PREDICTION MODEL-BASED DECORRELATION method

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 1989年第6期11卷 661-665页

作者： LIN, Z ATTIKIOUZEL, Y Dept. of Electr. & Electron. Eng. Western Australia Univ. Nedlands WA Australia

A unified feature extraction scheme, the two-dimensional (2-D) linear prediction model-based decorrelation method, is presented. By applying 2-D causal linear prediction model to decorrelate a textured image, the very heavy computation load required when using a whitening operator to decorrelate the image, or the significant information loss when using the gradient operator to approximately whiten the image is avoided. The texture model-based decorrelation provides three sets of features to perform texture classification: the coefficients of the 2-D linear prediction, the moments of error residuals and the autocorrelation values. An optimum feature-selection scheme using modified branch-and-bound method was introduced to reduce information redundancy. After feature selection, 100% classification accuracy was achieved for a 20-class texture problem. Experiments show that this feature extraction scheme is truly information lossless, effective, and fast.","doi":"10.1109/34.24801","publicationTitle":"IEEE Transactions on Pattern Analysis and Machine Intelligence","startPage":"661","endPage":"665","rightsLink":"http://***/AppDispatchServlet?publisherName=ieee&publication=0162-8828&title=Two-dimensional+linear+prediction+model-based+decorrelation+method&isbn=&publicationDate=June+1989&author=Z.+Lin&ContentID=10.1109/34.24801&orderBeanReset=true&startPage=661&endPage=665&volumeNum=11&issueNum=6","displayPublicationTitle":"IEEE Transactions on Pattern Analysis and Machine Intelligence","pdfPath":"/iel1/34/938/***","keywords":[{"type":"IEEE Keywords","kwd":["Predictive models","Decorrelation","Feature extraction","Image texture analysis","Image analysis","Two dimensional displays","Autocorrelation","Image segmentation","Parametric statistics","Correlation"]},{"type":"INSPEC: Controlled Indexing","kwd":["picture processing","correlation methods","filtering and prediction theory","pattern recognition"]},{"type":"INSPEC: Non-Controlled Indexing","kwd":["

关键词： Predictive models Decorrelation Feature extraction Image texture analysis Image analysis Two dimensional displays Autocorrelation Image segmentation Parametric statistics Correlation INSPEC: Controlled Indexing picture processing correlation methods filtering and prediction theory pattern recognition INSPEC: Non-Controlled Indexing branch-and-bound method 2D linear prediction model based decorrelation picture processing pattern recognition feature extraction textured image whitening operator texture classification error residuals autocorrelation values feature-selection

来源：评论

学校读者我要写书评

暂无评论

Algorithms for the minimum spanning tree problem with resource allocation

引用

OPERATIONS RESEARCH PERSPECTIVES 2016年 3卷 5-13页

作者： Kataoka, Seiji Yamada, Takeo Natl Def Acad Dept Comp Sci Yokosuka Kanagawa 2398686 Japan

We formulate the minimum spanning tree problem with resource allocation (MSTRA) in two ways, as discrete and continuous optimization problems (d-MSTRA/c-MSTRA), prove these to be NP-hard, and present algorithms to solve these problems to optimality. We reformulate d-MSTRA as the knapsack constrained minimum spanning tree problem, and solve this problem using a previously published branch-and-bound algorithm. By applying a 'peg test', the size of d-MSTRA is (significantly) reduced. To solve c-MSTRA, we introduce the concept of f-fractional solution, and prove that an optimal solution can be found within this class of solutions. Based on this fact, as well as conditions for 'pruning' subproblems, we develop an enumerative algorithm to solve c-MSTRA to optimality. We implement these algorithms in ANSI C programming language and, through extensive numerical tests, evaluate the performance of the developed codes on various types of instances. (C) 2016 The Authors. Published by Elsevier Ltd.

关键词： Minimum spanning tree problem Resource allocation Trade-off analysis branch-and-bound method

来源：评论

学校读者我要写书评

暂无评论

Multi-dimensional pruning from the Baumann point in an interval global optimization algorithm

引用

JOURNAL OF GLOBAL OPTIMIZATION 2007年第2期38卷 215-236页

作者： Toth, Boglarka Casado, Leocadio G. Univ Murcia Dept Estadist & Invest Operat Murcia 30100 Spain Univ Almeria Dept Arquitectura Comp & Elect Almeria 04120 Spain

A new pruning method for interval branch and bound algorithms is presented. In reliable global optimization methods there are several approaches to make the algorithms faster. In minimization problems, interval B&B methods use a good upper bound of the function at the global minimum and good lower bounds of the function at the subproblems to discard most of them, but they need efficient pruning methods to discard regions of the subproblems that do not contain global minimizer points. The new pruning method presented here is based on the application of derivative information from the Baumann point. Numerical results were obtained by incorporating this new technique into a basic Interval B&B Algorithm in order to evaluate the achieved improvements.

关键词： interval arithmetic branch-and-bound method global optimization pruning test

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：