A branch and bound algorithm for disassembly scheduling with assembly product structure

This paper considers a production planning problem in disassembly systems, which is the problem of determining the quantity and timing of disassembling end-of-use/life products in order to satisfy the demand of their parts or components over a planning horizon. The case of single product type without parts commonality is considered for the objective of minimizing the sum of setup and inventory holding costs. To show the complexity of the problem, we prove that the problem is NP-hard. Then, after deriving the properties of optimal solutions, a branch and bound algorithm is suggested that incorporates the Lagrangean relaxation-based upper and lower bounds. Computational experiments are performed on a number of randomly generated problems and the test results indicate that the branch and bound algorithm can give optimal solutions up to moderate-sized problems in a reasonable computation time. A Lagrangean heuristic for a viable alternative for large-sized problems is also suggested and compared with the existing heuristics to show its effectiveness.     

A branch and bound algorithm for hybrid flow shop scheduling problem with setup time and assembly operations

A hybrid flow shop scheduling problem (HFSP) with assembly operations is studied in this paper. In the considered problem, a number of products of the same kind are produced. Each product is assembled using a set of several parts. At first, the parts are produced in a hybrid flow shop and then they are assembled in an assembly stage to produce products. The considered objective is to minimize the completion time of all products (makespan). This problem has been proved strongly NP-hard, so in order to solve it, a hierarchical branch and bound algorithm is presented. Also, some lower and upper bounds are developed to increase the efficiency of the proposed algorithm. The numerical experiments are used to evaluate the performance of the proposed algorithm.     

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

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.     

A two-stage parallel branch and bound algorithm for mixed integer programs

Mixed integer programming (MIP) models are extensively usedto aid strategic and tactical decision making in many businesssectors. Solving MIP models is a computationally intensive processand there is a need to develop solution approaches that enablelarger models to be solved within acceptable timeframes. Inthis paper, we describe the implementation of a two-stage parallelbranch and bound (PB & B) algorithm for MIP. In stage 1of the algorithm, a multiple heuristic search is implementedin which a number of alternative search trees are investigatedusing a forest search in the hope of finding a good solutionquickly. In stage 2, the search is reorganized so that the branchesof a chosen tree are investigated in parallel. A new heuristicis introduced, based on a best projection criterion, which evaluatesalternative B & B trees in order to choose one for investigationin stage 2 of the algorithm. The heuristic also serves as away of implementing a quality load balancing scheme for stage2 of the algorithm. The results of experimental investigationsare reported for a range of models taken from the MIPLIB libraryof benchmark problems.     

A branch and bound algorithm for the acyclic subgraph problem

A branch and bound algorithm for the acyclic subgraph problem (feedback are set problem) is described. The branching scheme lexicographically enumerates all permutations, skipping initial segments known by some easy tests not to have any optimal completion. A lower bound for the number of feedback arcs is given by the size of any collection of disjoint cycles. We propose a heuristic algorithm to find a large collection. The size of the problems our branch and bound algorithm can solve varies from 25 to 34 nodes, depending on the nature of the problem.     

A branch and bound algorithm for the maximum clique problem

We present a branch and bound algorithm for the maximum clique problem in arbitrary graphs. The main part of the algorithm consists in the determination of upper bounds by graph colorings. Using a modification of a known graph coloring method called DSATUR we simultaneously derive lower and upper bounds for the clique number.

---

Zusammenfassung Wir stellen einen Branch and Bound Algorithmus für das Maximum Clique Problem in einem beliebigen Graphen vor. Das Hauptaugenmerk richtet sich dabei auf die Bestimmung oberer Schranken mit Hilfe von Färbungen von Graphen. Es wird eine Modifikation einer bekannten Färbungsmethode, genannt DSATUR, verwendet, mit der sich gleichzeitig obere und untere Schranken für die Cliquezahl erstellen lassen.

     

A branch and bound algorithm for the maximum diversity problem

This article begins with a review of previously proposed integer formulations for the maximum diversity problem (MDP). This problem consists of selecting a subset of elements from a larger set in such a way that the sum of the distances between the chosen elements is maximized. We propose a branch and bound algorithm and develop several upper bounds on the objective function values of partial solutions to the MDP. Empirical results with a collection of previously reported instances indicate that the proposed algorithm is able to solve all the medium-sized instances (with 50 elements) as well as some large-sized instances (with 100 elements). We compare our method with the best previous linear integer formulation solved with the well-known software Cplex. The comparison favors the proposed procedure.     

A branch and bound algorithm for the generalized assignment problem

This paper describes what is termed the generalized assignment problem. It is a generalization of the ordinary assignment problem of linear programming in which multiple assignments of tasks to agents are limited by some resource available to the agents. A branch and bound algorithm is developed that solves the generalized assignment problem by solving a series of binary knapsack problems to determine the bounds. Computational results are cited for problems with up to 4 000 0–1 variables, and comparisons are made with other algorithms.This research was partly supported by ONR Contracts N00014-67-A-0126-0008 and N00014-67-A-0126-0009 with the Center for Cybernetic Studies, The University of Texas.     

A branch and bound algorithm for solving the multiple-choice knapsack problem

The multiple-choice knapsack problem is a binary knapsack problem with the addition of disjoint multiple-choice constraints. We describe a branch and bound algorithm based on embedding Glover and Klingman's method for the associated linear program within a depth-first search procedure. A heuristic is used to find a starting dual feasible solution to the associated linear program and a ‘pegging’ test is employed to reduce the size of the problem for the enumeration phase. Computational experience and comparisons with the code of Nauss and an algorithm of Armstrong et al. for the same problem are reported.     

A new branch and bound algorithm for cell formation problem

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.     

A branch and bound algorithm for scheduling trains in a railway network

The paper studies a train scheduling problem faced by railway infrastructure managers during real-time traffic control. When train operations are perturbed, a new conflict-free timetable of feasible arrival and departure times needs to be re-computed, such that the deviation from the original one is minimized. The problem can be viewed as a huge job shop scheduling problem with no-store constraints. We make use of a careful estimation of time separation among trains, and model the scheduling problem with an alternative graph formulation. We develop a branch and bound algorithm which includes implication rules enabling to speed up the computation. An experimental study, based on a bottleneck area of the Dutch rail network, shows that a truncated version of the algorithm provides proven optimal or near optimal solutions within short time limits.     

A simplicial branch and bound duality-bounds algorithm for the linear sum-of-ratios problem

In this article, we present and validate a simplicial branch and bound duality-bounds algorithm for globally solving the linear sum-of-ratios fractional program. The algorithm computes the lower bounds called for during the branch and bound search by solving ordinary linear programming problems. These problems are derived by using Lagrangian duality theory. The algorithm applies to a wide class of linear sum-of-ratios fractional programs. Two sample problems are solved, and the potential practical and computational advantages of the algorithm are indicated.     

R-SALSA: A branch,bound, and remember algorithm for the workload smoothing problem on simple assembly lines

We consider a simple assembly line balancing problem with given cycle time and number of stations. A quadratic objective function based on a so-called smoothness index SX levels the workloads of the stations. For this problem, called SALBP-SX, only a few solution procedures have been proposed in literature so far. In this paper, we extend and improve the branch-and-bound procedure SALSA (Simple Assembly Line Smoothing Algorithm) of Walter et al. (2021) to a bidirectional branch, bound, and remember algorithm called R-SALSA (R for remember). Like SALSA, it is based on a dynamic programming scheme which pre-determines potential workloads of the stations and provides a construction plan for possible station loads. This scheme is extended by the new concept of supporters and preventers which significantly enhances branching, bounding, and logical tests. Furthermore, a tailored heuristic that searches for improved initial solutions, a bidirectional branching scheme and additional dominance rules are integrated. In extensive computational experiments, we find out that our new procedure clearly outperforms all former exact solution procedures on benchmark data sets with up to 1000 tasks.     

An upper bound for the zero-one knapsack problem and a branch and bound algorithm

A new way of computing the upper bound for the zero-one knapsack problem is presented, substantially improving on Dantzig's approach. A branch and bound algorithm is proposed, based on the above mentioned upper bound and on original backtracking and forward schemes. Extensive computational experiences indicate this new algorithm to be superior to the fastest algorithms known at present.     

A branch and bound algorithm for the robust spanning tree problem with interval data

The robust spanning tree problem is a variation, motivated by telecommunications applications, of the classic minimum spanning tree problem. In the robust spanning tree problem edge costs lie in an interval instead of having a fixed value.Interval numbers model uncertainty about the exact cost values. A robust spanning tree is a spanning tree whose total cost minimizes the maximum deviation from the optimal spanning tree over all realizations of the edge costs. This robustness concept is formalized in mathematical terms and is used to drive optimization.In this paper a branch and bound algorithm for the robust spanning tree problem is proposed. The method embeds the extension of some results previously presented in the literature and some new elements, such as a new lower bound and some new reduction rules, all based on the exploitation of some peculiarities of the branching strategy adopted.Computational results obtained by the algorithm are presented. The technique we propose is up to 210 faster than methods recently appeared in the literature.     

A branch and bound algorithm for the robust shortest path problem with interval data

Many real problems can be modelled as robust shortest path problems on interval digraphs, where intervals represent uncertainty about real costs and a robust path is not too far from the shortest path for each possible configuration of the arc costs.A branch and bound algorithm for this problem is presented.     

A note on the two-stage assembly flow shop scheduling problem with uniform parallel machines

We study the problem of minimizing the makespan in a two-stage assembly flow shop scheduling problem with uniform parallel machines. This problem is a generalization of the assembly flow shop problem with concurrent operations in the first stage and a single assembly operation in the second stage. We propose a heuristic with an absolute performance bound which becomes asymptotically optimal as the number of jobs becomes very large. We show that our results slightly improve earlier results for the simpler assembly flow shop problem (without uniform machines) and for the two-stage hybrid flow shop problem with uniform machines.     

A tight bound for the boolean quadratic optimization problem and its use in a branch and bound algorithm 1

Known duality statements are used to find tight bounds for the branch and bound process in solving Boolean quadratic optimization problems. To solve the corresponding continuous partial problem, a NEWTON-like procedure is indicated. Superlinear convergence, however, is only obtained in partial cases.     

A BRANCH BOUND METHOD FOR SUBSET SUM PROBLEM

ＡＢＲＡＮＣＨＢＯＵＮＤＭＥＴＨＯＤＦＯＲＳＵＢＳＥＴＳＵＭＰＲＯＢＬＥＭＷＵＳＨＩＱＵＡＮ（吴士泉）（ＩｎｓｔｉｔｕｔｅｏｆＡｐｐｌｉｅｄＭａｔｈｅｍａｔｉｃｓ，ｔｈｅＣｈｉｎｅｓｅＡｃａｄｅｍｙｏｆＳｃｉｅｎｃｅｓ，Ｂｅｉｊｉｎｇ１０００８０，Ｃ...     

A simplicial branch and duality bound algorithm for the sum of convex–convex ratios problem

This article presents a simplicial branch and duality bound algorithm for globally solving the sum of convex–convex ratios problem with nonconvex feasible region. To our knowledge, little progress has been made for globally solving this problem so far. The algorithm uses a branch and bound scheme where the Lagrange duality theory is used to obtain the lower bounds. As a result, the lower-bounding subproblems during the algorithm search are all ordinary linear programs that can be solved very efficiently. It has been proved that the algorithm possesses global convergence. Finally, the numerical experiments are given to show the feasibility of the proposed algorithm.