We consider the problem of locating input and output (I/O) points of each department for a given layout. The objective of the problem is to minimise the total distance of material flows between the I/O points. Here, d...
详细信息
We consider the problem of locating input and output (I/O) points of each department for a given layout. The objective of the problem is to minimise the total distance of material flows between the I/O points. Here, distances between the I/O points are computed as the lengths of the shortest path (not the rectilinear distances) between the I/O points. We developed a procedure to eliminate dominated candidate positions of I/O points that do not need to be considered. With this procedure, a large number of dominated candidate positions can be eliminated. A linear programming (LP) model for minimising the total rectilinear distance of flows is used to obtain a lower bound. Using the elimination procedure and the LP model, a branch and bound algorithm is developed to find an optimal location of the I/O points. Results from computational experiments show that the suggested algorithm finds optimal solutions in a very short time even for large-sized problems.
The article studies the scheduling problem of a material handling hoist in a circuit board production line. The existing models for the problem assume that the times required to perform inter-tank moves are given cons...
详细信息
The article studies the scheduling problem of a material handling hoist in a circuit board production line. The existing models for the problem assume that the times required to perform inter-tank moves are given constants. However, as shown in a simple example, the optimal solutions obtained under this assumption may not be the actual optimal solutions. In this article the times for inter-tank moves are decision variables of a mixed integer program proposed for the problem. An efficient branch and bound algorithm is developed for solving the problem optimally. A numerical example is used to illustrate the algorithm. Computational experience with benchmark problems and randomly generated test problems is discussed.
We consider linear systems with unspecified parameters that lie between given upper and lower bounds. Except for a few special cases, the computation of many quantities of interest for such systems can be performed on...
详细信息
Cell formation (CF) is the first and the most important problem in designing cellular manufacturing systems. Due to its non-polynomial nature, various heuristic and metaheuristic algorithms have been proposed to solve...
详细信息
Cell formation (CF) is the first and the most important problem in designing cellular manufacturing systems. Due to its non-polynomial nature, various heuristic and metaheuristic algorithms have been proposed to solve CF problem. Despite the popularity of heuristic algorithms, few studies have attempted to develop exact algorithms, such as branch and bound (B&B) algorithms, for this problem. We develop three types of branch and bound algorithms to deal with the cell formation problem. The first algorithm uses a binary branching scheme based on the definitions provided for the decision variables. Unlike the first algorithm, which relies on the mathematical model, the second one is designed based on the structure of the cell formation problem. The last algorithm has a similar structure to the second one, except that it has the ability to eliminate duplicated nodes in branching trees. The proposed branch and bound algorithms and a hybrid genetic algorithm are compared through some numerical examples. The results demonstrate the effectiveness of the modified problem-oriented branch and bound algorithm in solving relatively large size cell formation problems. (C) 2011 Elsevier Inc. All rights reserved.
Issues of computer network survivability have gained much attention in recent years since computer networks plays an important role in modern world. Many organizations, institutions, companies use computer networks as...
详细信息
Issues of computer network survivability have gained much attention in recent years since computer networks plays an important role in modern world. Many organizations, institutions, companies use computer networks as a basic tool for transmitting many kinds of information. Service disruptions in modern networks are expected to be significant because loss of services and traffic in high-speed fiber systems could cause a lot of damages including economic loses, political conflicts, human health problems. In this paper we focus on problems of survivable connection oriented network design. A new objective function LF for primary routes assignment applying the local-destination rerouting strategy is defined. Next, an optimization problem of primary routes assignment using the LF function is formulated. Moreover, a branch and bound algorithm for that problem is proposed. The theory and experimental results demonstrate the ability to apply the LF function to dynamic and static design of survivable connection oriented networks.
For linear bilevel programming, the branch and bound algorithm is the most successful algorithm to deal with the complementary constraints arising from Kuhn Tucker conditions. However, one principle challenge is that ...
详细信息
For linear bilevel programming, the branch and bound algorithm is the most successful algorithm to deal with the complementary constraints arising from Kuhn Tucker conditions. However, one principle challenge is that it could not well handle a linear bilevel programming problem when the constraint functions at the upper-level are of arbitrary linear form. This paper proposes an extended branch and bound algorithm to solve this problem. The results have demonstrated that the extended branch and bound algorithm can solve a wider class of linear bilevel problems can than current capabilities permit. (c) 2006 Elsevier Inc. All rights reserved.
Feature selection plays an important role in pattern classification. In this paper, we present an improved branch and bound algorithm for optimal feature subset selection. This algorithm searches for an optimal soluti...
详细信息
Feature selection plays an important role in pattern classification. In this paper, we present an improved branch and bound algorithm for optimal feature subset selection. This algorithm searches for an optimal solution in a large solution tree in an efficient manner by cutting unnecessary paths which are guaranteed not to contain the optimal solution. Our experimental results demonstrate the effectiveness of the new algorithm. (C) 2003 Elsevier Science B.V. All rights reserved.
We propose a new adaptive branch and bound algorithm for selecting the optimal subset of features in pattern recognition applications. The algorithm improves the search speed by avoiding unnecessary criterion function...
详细信息
We propose a new adaptive branch and bound algorithm for selecting the optimal subset of features in pattern recognition applications. The algorithm improves the search speed by avoiding unnecessary criterion function calculations at nodes in the solution tree. Our algorithm includes the following new properties: (i) ordering the tree nodes by the significance of features during construction of the tree, Oil obtaining a large "good" initial bound by a floating search method, (iii) a new method to select an initial starting search level in the tree. and (iv) a new adaptive jump search strategy to select subsequent search levels to avoid redundant criterion function calculations. Our experimental results for four different databases demonstrate that our method is significantly faster than other versions of the branch and bound algorithm when the database has more than 30 features. (c) 2007 Elsevier B.V.. All rights reserved.
In this paper, a nonconvex multiobjective optimization problem with Lipschitz objective functions is considered. A branch and bound algorithm that incorporates the decision maker's preference information is propos...
详细信息
In this paper, a nonconvex multiobjective optimization problem with Lipschitz objective functions is considered. A branch and bound algorithm that incorporates the decision maker's preference information is proposed for this problem. In the proposed algorithm, a new discarding test is designed to check whether a box contains preferred solutions according to the preference information expressed by means of reference points. In this way, the proposed algorithm is able to gradually guide the search towards the region of interest on the Pareto fronts during the solution process. We prove that the proposed algorithm obtains e-efficient solutions distributed among the regions of interest with respect to the given reference points. Moreover, lower bound on the total finite number of required iterations for predefined precision is also provided. Finally, the algorithm is illustrated with a number of test problems.
This paper addresses a robotic cell rescheduling problem and focuses on trade-off between the total completion time of all jobs and the disturbance of a reschedule. We first define and measure the disturbance of a res...
详细信息
This paper addresses a robotic cell rescheduling problem and focuses on trade-off between the total completion time of all jobs and the disturbance of a reschedule. We first define and measure the disturbance of a reschedule as the deviation of completion time of the jobs already scheduled between the reschedule and the initial schedule. To guarantee the steady performance of the system, we consider a special case that the processing sequence of the jobs already scheduled cannot be changed. The addressed rescheduling problem is transformed into a series of deterministic local scheduling problems with the objective of minimizing the total completion time of all jobs provided that the disturbance is within a given limit. A two-phase branch and bound algorithm is developed to efficiently solve the local scheduling problems. To improve the efficiency of the search procedure, a dynamic enumeration mechanism is applied to eliminate redundant constraints. Furthermore, two search strategies are proposed to direct the search procedure toward finding an optimal solution and a near-optimal solution. Finally, computational results demonstrate the efficiency of our algorithm. (C) 2014 Elsevier Ltd. All rights reserved.
暂无评论