van de Velde, S. L.
October 1990
Annals of Operations Research;1990, Vol. 26 Issue 1-4, p257
Academic Journal
A branch-and-bound algorithm is presented for the two-machine flow shop problem with the objective of minimizing the sum of the job completion times. Lower bounds and precedence constraints result from a Lagrangian relaxation of this problem. The Lagrangian subproblem turns out to be a linear ordering problem that is polynomially solvable for appropriate choices of the Lagrangian multipliers. The best choice within this class yields a lower bound that dominates previous bounds. In fact, the existing bounds correspond to particular choices of the multipliers. Several dominance criteria are given to restrict the search tree. Computational experiments show that the proposed algorithm outperforms the previously best method.


Related Articles

  • A Polyhedral Approach to the Asymmetric Traveling Salesman Problem. Fischetti, Matteo; Toth, Paolo // Management Science;Nov97, Vol. 43 Issue 11, p1520 

    Several branch-and-bound algorithms for the exact solution of the asymmetric traveling salesman problem (ATSP), based on the assignment problem (AP) relaxation, have been proposed in the literature. These algorithms perform very well for some instances (e.g., those with uniformly random integer...

  • Obtaining the efficient set of nonlinear biobjective optimization problems via interval branch-and-bound methods. Fernández, José; Tóth, Boglárka // Computational Optimization & Applications;Apr2009, Vol. 42 Issue 3, p393 

    Obtaining a complete description of the efficient set of multiobjective optimization problems can be of invaluable help to the decision-maker when the objectives conflict and a solution has to be chosen. In this paper we present an interval branch-and-bound algorithm which aims at obtaining a...

  • BRANCH-AND-BOUND AS A HIGHER-ORDER FUNCTION. Mckeown, G. P.; Rayward-Smith, V. J.; Turpin, H. J. // Annals of Operations Research;1991, Vol. 33 Issue 1-4, p379 

    The branch-and-bound paradigm is presented as a higher-order function and illustrated by instantiations, providing two well-known branch-and-bound algorithms for the Steiner tree problem in graphs and one for the travelling salesman problem. We discuss the advantages of such a specification and...

  • Setup and Open-Stacks Minimization in One-Dimensional Stock Cutting. Belov, Gleb; Scheithauer, Guntram // INFORMS Journal on Computing;Winter2007, Vol. 19 Issue 1, p27 

    The primary objective in cutting and packing problems is trim loss or material input minimization (in stock cutting) or value maximization (in knapsack-type problems). However, in real-life production we usually have many other objectives (costs) and constraints. Probably the most complex...

  • Optimal periodic scheduling of multipurpose batch plants. Shah, N.; Pantelides, C. C.; Sargent, R. W. H. // Annals of Operations Research;1993, Vol. 42 Issue 1-4, p193 

    A rigorous mathematical programming framework for the scheduling of multipurpose batch plants operated in a cyclic mode is presented. The proposed formulation can deal with batch operations described by complex processing networks, involving shared intermediates, material recycles, and multiple...

  • A Branch and Bound Algorithm to Minimize Total Weighted Tardiness on a Single Processor. Babu, Pascal; Peridy, Laurent; Pinson, Eric // Annals of Operations Research;Jul2004, Vol. 129 Issue 1-4, p33 

    In this paper, we consider the problem of minimizing the total weighted tardiness of a set of jobs processed on a single processor. First, a lower bound based on a Lagrangian decomposition is presented. The particularity of this decomposition, based on a 0–1 time indexed formulation, is...

  • Towards a closer integration of finite domain propagation and simplex-based algorithms. Hajian, Mozafar T.; El-Sakkout, Hani; Wallace, Mark; Lever, Jonathan M.; Richards, Barry // Annals of Operations Research;1998, Vol. 81 Issue 1-4, p421 

    This paper describes our experience in implementing an industrial application using the finite domain solver of the ECLiPSe constraint logic programming (CLP) system, in conjunction with the mathematical programming (MP) system, FortMP. In this technique, the ECLiPSe system generates a feasible...

  • Simultaneous Job Scheduling and Resource Allocation on Parallel Machines. Zhi-Long Chen // Annals of Operations Research;Jul2004, Vol. 129 Issue 1-4, p135 

    Most deterministic production scheduling models assume that the processing time of a job on a machine is fixed externally and known in advance of scheduling. However, in most realistic situations, apart from the machines, it requires additional resources to process jobs, and the processing time...

  • Development of an Innovative Algorithm for the Traveling Salesman Problem (TSP). Froushani, Mahshid Abtahi; Yusuff, Rosnah Mohd. // European Journal of Scientific Research;Apr2009, Vol. 29 Issue 3, p349 

    A large number of real-world planning problems called combinatorial optimization problems share the following properties: They are optimization problems, are easy to state, and have a finite but usually very large number of feasible solutions. Branch and Bound (B&B) is by far the most widely...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics