Similar Search Results

Pivot and Complement--A Heuristic for 0-1 Programming

Balas, Egon; Martin, Clarence H. - In: Management Science 26 (1980) 1, pp. 86-96

Pivot and Complement is a heuristic for finding approximate solutions to 0-1 programming problems. It uses the fact …

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

The Lagrangian Relaxation Method for Solving Integer Programming Problems

Fisher, Marshall L. - In: Management Science 27 (1981) 1, pp. 1-18

One of the most computationally useful ideas of the 1970s is the observation that many hard integer programming problems can be viewed as easy problems complicated by a relatively small set of side constraints. Dualizing the side constraints produces a Lagrangian problem that is easy to solve...

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

Note---An Approximate Algorithm for Multidimensional Zero-One Knapsack Problems---A Parametric Approach

Lee, Jae Sik; Guignard, Monique - In: Management Science 34 (1988) 3, pp. 402-410

A new approximate algorithm for multidimensional zero-one knapsack problems with all positive coefficients is presented. The procedure is controlled by three parameters which affect the tradeoff between solution quality and computation time and whose values are set by the users. For 48 test...

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

Worst-Case Analysis of Heuristic Algorithms

Fisher, Marshall L. - In: Management Science 26 (1980) 1, pp. 1-17

heuristic performance. A worst-case study establishes the maximum deviation from optimality that can occur when a specified … heuristic is applied within a given problem class. This is an important piece of information that can be combined with empirical … testing and other analyses to provide a more complete evaluation of a heuristic. In this paper the basic ground rules of worst …

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

Evaluation of a Heuristic for Scheduling Independent Jobs on Parallel Identical Processors

Dogramaci, Ali; Surkis, Julius - In: Management Science 25 (1979) 12, pp. 1208-1216

problems. Therefore, practitioners are forced to use heuristic methods to schedule their jobs on multiple processors. This … our total tardiness can be lowered substantially? How far off might the heuristic solution be, from the optimal solution …?" The study reported in this paper focuses on a heuristic which can handle reasonably large problems, and yet can be simply …

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

Asymptotic Methods in the Probabilistic Analysis of Sequencing and Packing Heuristics

E. G. Coffman, Jr.; Lueker, G. S.; Kan, A. H. G. Rinnooy - In: Management Science 34 (1988) 3, pp. 266-290

Recently there has been considerable interest in the average-case performance of heuristics. This paper pursues that interest, where it concerns sequencing and packing problems. In particular, we survey the methods that have been used to obtain formal probabilistic analyses of heuristics for...

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

The Lagrangian Relaxation Method for Solving Integer Programming Problems

Fisher, Marshall L. - In: Management Science 50 (2004) 12_supplement, pp. 1861-1871

(This article originally appeared in Management Science, January 1981, Volume 27, Number 1, pp. 1--18, published by The Institute of Management Sciences.) One of the most computationally useful ideas of the 1970s is the observation that many hard integer programming problems can be viewed as...

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

A Lagrangean Relaxation Algorithm for the Two Duty Period Scheduling Problem

Shepardson, Fred; Marsten, Roy E. - In: Management Science 26 (1980) 3, pp. 274-281

The two duty period scheduling problem is an integer programming problem with 0-1 constraint coefficients. It is recognized that the problem can be reformulated as a one duty period problem with side constraints. Since the one duty period problem can be solved as a minimal cost network flow...

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

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

Note---On the Single Machine Scheduling Problem with Quadratic Penalty Function of Completion Times: An Improved Branching Procedure

Gupta, Sushil K.; Sen, Tapan - In: Management Science 30 (1984) 5, pp. 644-647

This paper gives optimality conditions to obtain a priori precedence relationships among some of the jobs in a single machine scheduling problem so as to curtail the enumeration while using branch-and-bound technique. The objective is to minimize a quadratic (or generalized quadratic) penalty...

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