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

A branch and bound algorithm for Scheduling of Flexible Manufacturing Systems

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING 2024年第3期21卷 4382-4396页

作者： Ahn, Jeongsun Kim, Hyun-Jung Korea Adv Inst Sci & Technol Dept Ind & Syst Engn Daejeon 34141 South Korea

Flexible manufacturing systems (FMSs), which can easily adapt to changes in job types, have been widely used in manufacturing areas. Scheduling of FMSs is a variant of a flexible job shop with transport robots and no buffer, and it is extremely hard as it involves determining the job processing sequence on machines and the sequence of robot tasks, with various jobs with different processing flows and the risk of deadlocks. Due to these characteristics, many existing studies have focused on developing heuristic algorithms. However, an optimal solution is still crucial to minimize FMSs makespan. Therefore, we propose a mixed integer programming (MIP) and a branch and bound (B & B) algorithm with a timed Petri net (TPN) to achieve optimal scheduling of FMSs. FMSs are first modeled with a TPN, and tight lower bounds are proposed based on bottleneck machines and sophisticated ready times. In addition, the search space is effectively reduced by the transition index marking (TIM)-based dominance rule and various deadlock prevention conditions based on the TPN. The experimental results show that our proposed B & B algorithm outperforms mathematical formulation and previous algorithms in various FMS instances

关键词： branch and bound algorithm flexible manufacturing system optimization Petri net scheduling

来源：评论

学校读者我要写书评

暂无评论

A branch and bound algorithm for solving a class of D-C programming

引用

APPLIED MATHEMATICS AND COMPUTATION 2005年第2期165卷 291-302页

作者： Xue, HG Xu, CX Xian Jiaotong Univ Fac Sci Dept Math Xian 710049 Peoples R China

The D-C (difference of convex functions) programming occurs very often in economic and financial field. In this paper, a class of D-C programming problems be studied, witch objection function is the sum of a convex quadratic function and a separable concave function, the constrains is the intersection of a polytop and a rectangular. A branch and bound algorithm is given for solving it. we compare the largest distance bisection with omega-subdivision in branch and bound algorithm. Numerical tests on different dimensions showed that the proposed branch and bound algorithm is efficient for solving medium-scale problems, and the efficiency of the largest distance bisection and omega-subdivision is nearly. (c) 2004 Elsevier Inc. All rights reserved.

关键词： D-C programming branch and bound algorithm omega-subdivision the largest distance bisection normal rectangular subdivision

来源：评论

学校读者我要写书评

暂无评论

An efficient branch and bound algorithm for assembly line balancing problems with parallel multi-manned workstations

引用

COMPUTERS & OPERATIONS RESEARCH 2012年第12期39卷 3344-3360页

作者： Kellegoz, Talip Toklu, Bilal Gazi Univ Dept Ind Engn Fac Technol Ankara Turkey Gazi Univ Dept Ind Engn Fac Engn Ankara Turkey

In the event that big-sized complex products (containing a large number of assembly tasks most of which have long task times) are produced in simple or two-sided assembly lines, hundreds of stations are essentially required. Long product flow time, a large area for establishment of the line, a high budget for the investment of equipment, and tools in stations and several work-in-process are also required for these kinds of products. In order to avoid these disadvantages, assembly lines with parallel multi-manned workstations can be utilized. In this paper, these lines and one of their balancing problems are addressed, and a branch and bound algorithm is proposed. The algorithm is composed of a branching scheme, some efficient dominance and feasibility criteria based on a problem-specific knowledge. A heuristic-based guidance for enumeration process is included as an efficient component of the algorithm as well. VWSolver algorithm proposed for a special version of the problem in the literature has been modified and compared with the proposed algorithm. Results show that proposed algorithm outperforms VWSolver in terms of both CPU times and quality of feasible solutions found. (c) 2012 Elsevier Ltd. All rights reserved.

关键词： Assembly line balancing Parallel multi-manned stations Lower bounding branch and bound algorithm

来源：评论

学校读者我要写书评

暂无评论

An extended branch and bound algorithm for bilevel multi-follower decision making in a referential-uncooperative situation

引用

INTERNATIONAL JOURNAL OF INFORMATION TECHNOLOGY & DECISION MAKING 2007年第2期6卷 371-388页

作者： Lu, Jie Shi, Chenggen Zhang, Guangquan Da Ruan Univ Technol Sydney Fac Informat Technol Sydney NSW 2007 Australia CEN SCK Belgian Nucl Res Ctr B-2400 Mol Belgium Univ Ghent Dept Appl Math & Comp Sci B-9000 Ghent Belgium

Within the framework of any bilevel decision problem, a leader's decision at the upper level is influenced by the reaction of their follower at the lower level. When multiple followers are involved in a bilevel decision problem, the leader's decision will not only be affected by the reactions of those followers, but also by the relationships among those followers. One of the popular situations within this framework is where these followers are uncooperatively making decisions while having cross reference of decision information, called a referential-uncooperative situation in this paper. The well-known branch and bound algorithm has been successfully applied to a one-leader-and-one-follower linear bilevel decision problem. This paper extends this algorithm to deal with the above mentioned linear bilevel multi-follower decision problem by means of a linear referential uncooperative bilevel multi-follower decision model. It then proposes an extended branch and bound algorithm to solve this problem with a set of illustrative examples in a referential-uncooperative situation.

关键词： linear bilevel programming branch and bound algorithm optimization multi-followers

来源：评论

学校读者我要写书评

暂无评论

2-STEP SEMI-OPTIMAL branch and bound algorithm FOR FEATURE-SELECTION IN MIXED VARIABLE DISCRIMINATION

引用

PATTERN RECOGNITION 1989年第4期22卷 455-459页

作者： KRUSINSKA, E Institute of Computer Science University of Wrocław 51-151 Wrocław Przesmyckiego 20 Poland

The paper presents a two step procedure for the selection of the most discriminative discrete as well as continuous features in the location model for mixed-variable discriminant analysis. The multivariate discriminatory measure T2 is used as a criterion for subset choice. The first step consists in finding stepwisely the most discriminative discrete features. The second step enables one to select the subset of continuous variables for the previously chosen discrete feature set. The two steps may be reversed. When the number of discrete variables is already fixed the selection of continuous features is made efficiently by the branch and bound algorithm.

关键词： Discriminant analysis Location model Mixed variables branch and bound algorithm

来源：评论

学校读者我要写书评

暂无评论

A branch and bound algorithm for the one-machine scheduling problem,with minimum and maximum time lags

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2007年第1期181卷 102-116页

作者： Sheen, Gwo-Ji Liao, Lu-Wen Natl Cent Univ Inst Ind Management Jhongli 32001 Taoyuan Taiwan

We consider the one-machine scheduling problem with minimum and maximum time lags while minimizing the makespan. This problem typically arises in a manufacturing environment where the next job has to be carried out within a specific time range after the completion of the immediately preceding job. We describe a branch and bound algorithm, based on the input and output of a clique and the relevant propositions, for finding the optimal waiting times. The computational experiments give promising results, showing whether a given instance is feasible or infeasible. With the proposed branch and bound algorithm we can either find an optimal schedule or establish the infeasibility within an acceptable run time. (c) 2006 Elsevier B.V. All rights reserved.

关键词： scheduling one machine makespan branch and bound algorithm minimum and maximum time lags

来源：评论

学校读者我要写书评

暂无评论

A branch and bound algorithm for Cyclic Scheduling of Timed Petri Nets

引用

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING 2015年第1期12卷 309-323页

作者： Jung, Chihyun Kim, Hyun-Jung Lee, Tae-Eog GlobalFoundries Malta NY 12020 USA Univ Calif Berkeley Dept Ind Engn & Operat Res Berkeley CA 94720 USA Korea Adv Inst Sci & Technol Dept Ind & Syst Engn Taejon 305701 South Korea

A timed Petri net (TPN) has been widely used for modeling, scheduling, and analyzing discrete event dynamic systems. This study examines cyclic scheduling problems of a TPN to minimize the cycle time especially for automated manufacturing systems. Appropriate token routing at each conflict place can make a TPN repeat an identical firing sequence. We propose a systematic procedure to transform a TPN with such cyclic token routing into an equivalent timed event graph (TEG) for which the cycle time and firing schedules can be evaluated by a linear programming (LP). Based on the transformation procedure, we develop an efficient branch and bound algorithmto solve the scheduling problem. A partial solution is defined as a partial token route that has only a subset of token routes for determining the complete schedule. The lower bound of a partial solution is determined by the cycle time of a TEG that has the partial token route. The cycle time of a TEG with an additional token route for a new partial solution is computed by a dual-simplex algorithm which avoids solving the LP completely again. A dynamic branching strategy that prevents unnecessary branching for the scheduling decision is also proposed. We demonstrate the computational efficiency through intensive experiments of cluster tools and robotic flow shops. Note to Practitioners-There are many systems which repeat an identical task sequence such as manufacturing systems, transportation systems, and robotic systems. Maximizing the throughput of such a system by optimizing the cyclic task sequence, which is called a cyclic scheduling problem, has been an important problem. In order to deal with cyclic scheduling problems, this paper uses a timed Petri net (TPN) which is a graphical modeling tool for discrete event dynamic systems. As the size of a TPN model increases, the computational complexity of the cyclic scheduling problem exponentially increases due to the combinatorial nature of sequencing problems. Therefor

关键词： branch and bound algorithm cluster tool cyclic scheduling timed event graph (TEG) timed Petri net (TPN)

来源：评论

学校读者我要写书评

暂无评论

A branch and bound algorithm for single-machine production scheduling integrated with preventive maintenance planning

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2013年第3期51卷 847-868页

作者： Wang, Shijin Liu, Ming Tongji Univ Dept Management Sci & Engn Sch Econ & Management Shanghai 200092 Peoples R China

This paper deals with an integrated optimisation model for production scheduling and preventive maintenance (PM) in a single machine with its time to failure subject to a Weibull probability distribution. The objective is to minimise the total expected weighted completion time of jobs. To solve this problem, we develop a branch and bound (B&B) algorithm (hereafter called the B&BA). Several lower bounds, dominance rules and upper bounds are developed to enhance the performance of the B&BA. Extensive computational experiments on randomly generated problems with different configurations are conducted and the results show that the proposed method can find optimal solutions for problems with up to 18 jobs in a reasonable amount of computation time.

关键词： branch and bound algorithm preventive maintenance single machine production scheduling

来源：评论

学校读者我要写书评

暂无评论

A branch and bound algorithm FOR SEPARABLE CONCAVE PROGRAMMING

引用

Journal of Computational Mathematics 2004年第6期22卷 895-904页

作者： Hong-gangXue Cheng-xianXu Feng-minXu DepartmentofMathematics FacultyofScienceXi'anJiaotongUniversityxi'an710049China DepartmentofMathematics FacultyofScienceXi'anJiaotongUniversityXi'an710049China

In this paper, we propose a new branch and bound algorithm for the solution of large scale separable concave programming problems. The largest distance bisection (LDB) technique is proposed to divide rectangle into sub-rectangles when one problem is branched into two subproblems. It is proved that the LDB method is a normal rectangle subdivision(NRS). Numerical tests on problems with dimensions from 100 to 10000 show that the proposed branch and bound algorithm is efficient for solving large scale separable concave programming problems, and convergence rate is faster than ω-subdivision method.

关键词： ω-subdivision branch and bound algorithm Largest distance bisection Normal rectangle subdivision Separable programming

来源：评论

学校读者我要写书评

暂无评论

Individual haplotype assembly of Apis mellifera (honeybee) using a practical branch and bound algorithm

引用

JOURNAL OF ASIA-PACIFIC ENTOMOLOGY 2012年第3期15卷 375-381页

作者： Lim, Hyeong-Seok Jeong, In-Seon Kang, Seung-Ho KT Daeduk 2 Res Ctr Natl Inst Math Sci Div Fus Convergence Math Sci Taejon 305811 South Korea Chonnam Natl Univ Dept Comp Sci Kwangju 500757 South Korea Natl Acad Agr Sci Rural Dev Adm Dept Agr Bioresources Suwon 441855 South Korea

A haplotype is a single nucleotide polymorphism (SNP) sequence and a representative genetic marker describing the diversity of biological organs. Haplotypes have a wide range of applications such as pharmacology and medical applications. In particular, as a highly social species, haplotypes of the Apis mellifera (honeybee) benefit human health and medicine in diverse areas, including venom toxicology, infectious disease, and allergic disease. For this reason, assembling a pair of haplotypes from individual SNP fragments drives research and generates various computational models for this problem. The minimum error correction (MEC) model is an important computational model for an individual haplotype assembly problem. However, the MEC model has been proved to be NP-hard;therefore, no efficient algorithm is available to address this problem. In this study, we propose an improved version of a branch and bound algorithm that can assemble a pair of haplotypes with an optimal solution from SNP fragments of a honeybee specimen in practical time bound. First, we designed a local search algorithm to calculate the good initial upper bound of feasible solutions for enhancing the efficiency of the branch and bound algorithm. Furthermore, to accelerate the speed of the algorithm, we made use of the recursive property of the bounding function together with a lookup table. After conducting extensive experiments over honeybee SNP data released by the Human Genome Sequencing Center, we showed that our method is highly accurate and efficient for assembling haplotypes. (C) Korean Society of Applied Entomology, Taiwan Entomological Society and Malaysian Plant Protection Society, 2012. Published by Elsevier B.V. All rights reserved,

关键词： Apis mellifera (honeybee) Single nucleotide polymorphism (SNP) Haplotype assembly Local search algorithm branch and bound algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：