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

A branch-and-bound method for solving multi-skill project scheduling problem

RAIRO-OPERATIONS RESEARCH 2007年第2期41卷 155-170页

作者： Bellenguez-Morineau, Odile Neron, Emmanuel Univ Tours Lab Informat F-37200 Tours France

This paper deals with a special case of Project Scheduling problem: there is a project to schedule, which is made up of activities linked by precedence relations. Each activity requires specific skills to be done. Moreover, resources are staff members who master fixed skill(s). Thus, each resource requirement of an activity corresponds to the number of persons doing the corresponding skill that must be assigned to the activity during its whole processing time. We search for an exact solution that minimizes the makespan, using a branch-and-bound method. This paper deals with a special case of Project Scheduling problem: there is a project to schedule, which is made up of activities linked by precedence relations. Each activity requires specific skills to be done. Moreover, resources are staff members who master fixed skill(s). Thus, each resource requirement of an activity corresponds to the number of persons doing the corresponding skill that must be assigned to the activity during its whole processing time. We search for an exact solution that minimizes the makespan, using a branch-and-bound method.

关键词： project scheduling skills branch-and-bound method

来源：评论

学校读者我要写书评

暂无评论

Complexity of solving the Subset Sum problem with the branch-and-bound method with domination and cardinality filtering

引用

AUTOMATION AND REMOTE CONTROL 2017年第3期78卷 463-474页

作者： Kolpakov, R. M. Posypkin, M. A. Sin, Si Tu Tant Moscow MV Lomonosov State Univ Moscow Russia Russian Acad Sci Dorodnicyn Comp Ctr Moscow Russia Moscow Inst Elect Equipment Moscow Russia

We obtain an exact upper bound on the complexity of solving the Subset Sum problem with a variation of the branch-and-bound method of a special form. Complexity is defined as the number of subproblems considered in the process of solving the original problem. Here we reduce the enumeration by using the domination relation. We construct an instance of the Subset Sum problem on which our bound is realized. The resulting bound is asymptotically twice smaller than the exact upper bound on the complexity of solving this problem with a standard version of the branch-and-bound method.

关键词： knapsack problem branch-and-bound method computational complexity domination relation

来源：评论

学校读者我要写书评

暂无评论

Development of automatic nesting system for shipbuilding using the branch-and-bound method

引用

JOURNAL OF MARINE SCIENCE AND TECHNOLOGY 2019年第2期24卷 398-409页

作者： Hamada, Kunihiro Ikeda, Yasuhiro Tokumoto, Hiroshi Hase, Shinji Hiroshima Univ Higashihiroshima Hiroshima Japan Tsuneishi Shipbldg Co Ltd Fukuyama Hiroshima Japan

This study develops a novel automatic nesting system for shipbuilding using the branch-and-bound method. The previous studies mainly discussed strip-packing problem, which is related to the arrangement of parts on the base material. In addition to the strip-packing problem, the present study also considers the bin-packing problem, which is the distribution of parts to different base materials. Therefore, the nesting problem in shipbuilding is defined as a combinatorial optimization problem that encompasses both the bin-packing and strip-packing problems. Based on the above-mentioned problem definition, the solution space of the nesting problem is greatly enhanced, and a lot of time is required to determine the optimal solution. Therefore, the branch-and-bound method is used in this study to solve the above-mentioned combinatorial optimization problem considering the trade-off relation between improving the optimality (i.e., yield rate) and reducing the computation time. This paper discusses the proposed method in detail. In addition, an actual nesting problem is solved using the proposed method to test its validity.

关键词： Shipbuilding Nesting branch-and-bound method Optimization

来源：评论

学校读者我要写书评

暂无评论

Unified solution of a non-convex SCUC problem using combination of modified branch-and-bound method with Quadratic Programming

引用

ENERGY CONVERSION AND MANAGEMENT 2011年第12期52卷 3425-3432页

作者： Shafie-khah, M. Moghaddam, M. Parsa Sheikh-El-Eslami, M. K. Tarbiat Modares Univ Dept Elect & Comp Engn Tehran Iran

In this paper, a new practical method is presented for solving the non-convex security constraint unit commitment (SCUC) problem in power systems. The accuracy of the proposed method is desirable while the shorter computation time makes it useful for SCUC solution of large-scale power systems, real-time market operation and long-term SCUC problems. The proposed framework allows inclusion of the valve point effects, warmth-dependent start-up costs, ramp rates, minimum up/down time constraints, multiple fuels costs, emission costs, prohibited operating zones and AC power flow limits in normal and contingency conditions. To solve the non-convex problem, combination of a modified branch-and-bound method with the Quadratic Programming is used as an optimization tool and a developed AC power flow algorithm is applied for considering the security and contingency concerns using the nonlinear/linear AC model. These modifications improve the convergence speed and solution precision of SCUC problem. In the proposed method, in contrast with traditional SCUC algorithms, unit commitment solution, checking and satisfying the security constraints are managed simultaneously. The obtained results are compared with other reported methods for investigating the effectiveness of the proposed method. Also, the proposed method is applied to an Iranian power system including 493 thermal units. (C) 2011 Elsevier Ltd. All rights reserved.

关键词： branch-and-bound method Quadratic programming Security constraint unit commitment Non-convexity Contingency analysis Nonlinear/linear AC power flow

来源：评论

学校读者我要写书评

暂无评论

A branch-and-bound method for absolute value programs

引用

OPTIMIZATION 2014年第2期63卷 305-319页

作者： Yamanaka, Shota Fukushima, Masao Kyoto Univ Dept Appl Math & Phys Grad Sch Informat Kyoto 6068501 Japan

In recent years, the absolute value equation (AVE) has attracted growing attention. The absolute value program (AVP) is an extension of AVE, which contains absolute values of variables in its objective function and constraints. In this article, we propose an algorithm for the AVP, which is based on the branch-and-bound method. In the branching procedure, we generate two subproblems by restricting the sign of a variable to be nonnegative or nonpositive. In the bounding procedure, we utilize the duality results for AVP. Furthermore, we carry out numerical experiments for nonconvex multi-facility location problems to show the validity of the proposed algorithm.

关键词： absolute value program absolute value equation branch-and-bound method nonconvex facility location problem

来源：评论

学校读者我要写书评

暂无评论

Flow shop scheduling for separation model of set-up and net process based on branch-and-bound method

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2009年第2期57卷 550-562页

作者： Kurihara, Kenzo Li, Yann-Liang Nishiuchi, Nobuyuki Masuda, Kazuaki Kanagawa Univ Dept Informat Syst Creat Kanagawa Ku Yokohama Kanagawa 2218686 Japan Tung Nan Inst Technol Fac Business Adm Taipei 222 Taiwan Tokyo Metropolitan Univ Fac Syst Design Tokyo 1910065 Japan

Lots of research reports on flow shop scheduling problems have been reported. Generally speaking, these models are applicable to a simple model with no separation of set-up processes and net ones. In many production lines, we cannot ignore the set-up times in comparison with the net processing times. We can expect to shorten the total processing time by executing the set-up processes and net ones in parallel. We need a parallel operation model to improve schedule results. We will propose a new scheduling method for multi-stage flow shops. The aim of the method is to shorten the total processing time by operating the set-up processes and the net ones of each job in parallel. We applied the branch-and-bound method and developed a new calculation algorithm for the lower bound estimation of the total processing time. Finally, we will evaluate our proposed method by some numerical experiments using actual production line data. (C) 2008 Elsevier Ltd. All rights reserved.

关键词： Flow shop scheduling branch-and-bound method Total processing time

来源：评论

学校读者我要写书评

暂无评论

Optimality and Complexity Analysis of a branch-and-bound method in Solving Some Instances of the Subset Sum Problem

引用

OPEN COMPUTER SCIENCE 2020年第1期11卷 116-126页

作者： Kolpakov, Roman Posypkin, Mikhail Lomonosov Moscow State Univ Moscow Russia RAS Fed Res Ctr Comp Sci & Control Vavilov St 40 Moscow Russia Moscow Inst Phys & Technol Moscow Russia

In this paper we study the question of parallelization of a variant of branch-and-bound method for solving of the subset sum problem which is a special case of the Boolean knapsack problem. The following natural approach to the solution of this question is considered. At the first stage one of the processors (control processor) performs some number of algorithm steps of solving a given problem with generating some number of subproblems of the problem. In the second stage the generated subproblems are sent to other processors for solving (one subproblem per processor). Processors solve completely the received subproblems and return their solutions to the control processor which chooses the optimal solution of the initial problem from these solutions. For this approach we define formally a model of parallel computing (frontal parallelization scheme) and the notion of complexity of the frontal scheme. We study the asymptotic behavior of the complexity of the frontal scheme for two special cases of the subset sum problem.

关键词： computational complexity parallel computations subset sum problem branch-and-bound method

来源：评论

学校读者我要写书评

暂无评论

A branch-and-bound method for discretely-constrained mathematical programs with equilibrium constraints

引用

ANNALS OF OPERATIONS RESEARCH 2013年第1期210卷 5-31页

作者： Shim, Yohan Fodstad, Marte Gabriel, Steven A. Tomasgard, Asgeir Univ Maryland College Pk MD 20742 USA Norwegian Univ Sci & Technol N-7491 Trondheim Norway

We present a branch-and-bound algorithm for discretely-constrained mathematical programs with equilibrium constraints (DC-MPEC). This is a class of bilevel programs with an integer program in the upper-level and a complementarity problem in the lower-level. The algorithm builds on the work by Gabriel et al. (Journal of the Operational Research Society 61(9):1404-1419, 2010) and uses Benders decomposition to form a master problem and a subproblem. The new dynamic partition scheme that we present ensures that the algorithm converges to the global optimum. Partitioning is done to overcome the non-convexity of the Benders subproblem. In addition Lagrangean relaxation provides bounds that enable fathoming in the branching tree and warm-starting the Benders algorithm. Numerical tests show significantly reduced solution times compared to the original algorithm. When the lower level problem is stochastic our algorithm can easily be further decomposed using scenario decomposition. This is demonstrated on a realistic case.

关键词： Mathematical program with equilibrium constraints Bilevel programming Discrete planning and decision making Optimization branch-and-bound method Global optimization

来源：评论

学校读者我要写书评

暂无评论

A Non-Uniform Convergence Tolerance Scheme for Enhancing the branch-and-bound method

引用

TRANSACTIONS OF THE KOREAN SOCIETY OF MECHANICAL ENGINEERS A 2012年第4期36卷 361-371页

作者： Jung, Sangjin Chen, Xi Choi, Gyunghyun Choi, Dong-Hoon Hanyang Univ Grad Sch Mech Engn Seoul South Korea Eaton Corp Dublin Ireland Hanyang Univ Dept Ind Engn Seoul South Korea Hanyang Univ Ctr Innovat Design Optimizat Technol iDOT Seoul South Korea

In order to improve the efficiency of the branch-and-bound method for mixed-discrete nonlinear programming, a non-uniform convergence tolerance scheme is proposed for the continuous subproblem optimizations. The suggested scheme assigns the convergence tolerances for each continuous subproblem optimization according to the maximum constraint violation obtained from the first iteration of each subproblem optimization in order to reduce the total number of function evaluations needed to reach the discrete optimal solution. The proposed tolerance scheme is integrated with five branching order options. The comparative performance test results using the ten combinations of the five branching orders and two convergence tolerance schemes show that the suggested non-uniform convergence tolerance scheme is obviously superior to the uniform one. The results also show that the branching order option using the minimum clearance difference method performed best among the five branching order options. Therefore, we recommend using the "minimum clearance difference method" for branching and the "non-uniform convergence tolerance scheme" for solving discrete optimization problems.

关键词： Discrete Optimization Mixed-Discrete Nonlinear Programming branch-and-bound method Convergence Tolerance branching Order

来源：评论

学校读者我要写书评

暂无评论

Application of parallel heuristic algorithms for speeding up parallel implementations of the branch-and-bound method

引用

Computational Mathematics and Mathematical Physics 2007年第9期47卷 1464-1476页

作者： Posypkin, M.A. Sigal, I.Kh. Institute of Systems Analysis Russian Academy of Sciences Moscow 117312 pr. Shestidesyatiletiya Oktyabrya 9 Russian Federation Computing Center Russian Academy of Sciences Moscow 119991 ul. Vavilova 40 Russian Federation

A scheme for the parallel implementation of the combined branch-and-bound method and heuristic algorithms is proposed. Results of computations for the one-dimensional Boolean knapsack problem are presented that demonstrate the efficiency of the proposed approach. The main factors that affect the speedup of the solution when local optimization is used are discussed. © 2007 Pleiades Publishing, Ltd.

关键词： Algorithms for parallel computations branch-and-bound method Discrete optimization Knapsack problem Local optimization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：