Search Results - subject:"branch and bound"

A New Algorithm for the 0-1 Knapsack Problem

Martello, Silvano; Toth, Paolo - In: Management Science 34 (1988) 5, pp. 633-644

We present a new algorithm for the optimal solution of the 0-1 Knapsack problem, which is particularly effective for large-size problems. The algorithm is based on determination of an appropriate small subset of items and the solution of the corresponding "core problem": from this we derive a...

Persistent link: https://www.econbiz.de/10009197865

Algorithms for Scheduling a Single Machine to Minimize the Weighted Number of Late Jobs

Potts, C. N.; Wassenhove, L. N. Van - In: Management Science 34 (1988) 7, pp. 843-858

bound algorithm that uses the linear programming lower bound is proposed. Computational results with branch and bound … linear programming lower bound is used in a reduction algorithm that eliminates jobs from the problem. Also, a branch and …

Persistent link: https://www.econbiz.de/10009218029

Minimizing Mean Squared Deviation of Completion Times About a Common Due Date

Bagchi, Uttarayan; Sullivan, Robert S.; Chang, Yih-Long - In: Management Science 33 (1987) 7, pp. 894-906

This paper addresses a nonpreemptive single machine scheduling problem where all jobs have a common due date and have zero ready time. The scheduling objective is to minimize mean squared deviation (MSD) of job completion times about the due date. This nonregular measure of performance is...

Persistent link: https://www.econbiz.de/10009209188

An Integer Programming Approach and Implementation for an Electric Utility Capacity Planning Problem with Renewable Energy Sources

Sherali, Hanif D.; Staschus, Konstantin; Huacuz, Jorge M. - In: Management Science 33 (1987) 7, pp. 831-847

considers the option of investing in nondispatchable or renewable energy sources. A branch-and-bound algorithm is proposed for …

Persistent link: https://www.econbiz.de/10009214054

Heuristics for Multilevel Lot-Sizing with a Bottleneck

Billington, Peter J.; McClain, John O.; Thomas, L. Joseph - In: Management Science 32 (1986) 8, pp. 989-1006

branch and bound procedure. The objective is to find a production schedule that fits within available capacity at minimum …

Persistent link: https://www.econbiz.de/10009203846

A Branch and Bound Approach for Machine Load Balancing in Flexible Manufacturing Systems

Berrada, Mohammed; Stecke, Kathryn E. - In: Management Science 32 (1986) 10, pp. 1316-1335

A flexible manufacturing system (FMS) is an integrated system of computer numerically controlled machine tools connected with automated material handling. A set of production planning problems for FMSs has been defined (Stecke [Stecke, Kathryn E. 1983. Formulation and solution of nonlinear...

Persistent link: https://www.econbiz.de/10009204405

A Multiplier Adjustment Method for the Generalized Assignment Problem

Fisher, Marshall L.; Jaikumar, R.; Wassenhove, Luk N. Van - In: Management Science 32 (1986) 9, pp. 1095-1103

We describe a branch and bound algorithm for the generalized assignment problem in which bounds are obtained from a … reasonable in all cases and the branch and bound trees generated had nearly two orders of magnitude fewer nodes than for …

Persistent link: https://www.econbiz.de/10009214863

Improved Penalties for Fixed Cost Linear Programs Using Lagrangean Relaxation

Cabot, A. Victor; Erenguc, S. Selcuk - In: Management Science 32 (1986) 7, pp. 856-869

The most commonly used penalty in branch and bound approaches to integer programming is the Driebeek--Tomlin penalty … problems and comparing the number of nodes generated on the branch and bound tree and the total computer time needed to solve …

Persistent link: https://www.econbiz.de/10009218041

Branch and Bound Experiments in Convex Nonlinear Integer Programming

Gupta, Omprakash K.; Ravindran, A. - In: Management Science 31 (1985) 12, pp. 1533-1546

The branch and bound principle has long been established as an effective computational tool for solving mixed integer … linear programming problems. This paper investigates the computational feasibility of branch and bound methods in solving … convex nonlinear integer programming problems. The efficiency of a branch and bound method often depends on the rules used …

Persistent link: https://www.econbiz.de/10009191202

Note---Multi-Activity Facility Design and Location Problems

Akinc, Umit - In: Management Science 31 (1985) 3, pp. 275-283

capacities. Efficient branch-and-bound algorithms are developed, and extensive computational results are given. …

Persistent link: https://www.econbiz.de/10009214114