A Zero-One Programming Approach to Scheduling with Limited Resources

by A. Alan B. Pritsker, Lawrence J. Watters

Purchase Print Copy

 FormatList Price Price
Add to Cart Paperback59 pages $23.00 $18.40 20% Web Discount

A zero-one linear programming (LP) formulation of scheduling problems that is more versatile and efficient than any other known LP formulation. It is the first formulation designed to accommodate multiple resource constraints. Bowman's formulation can be extended to do so, but in a sample comparison, it required 72 variables and 125 constraints for a three-project, eight-job, three-resource problem compared with 33 variables and 48 constraints for the new formulation. The new method also showed substantial improvement when compared with schedules based on two common dispatching rules: first-come-first-served and earliest completion date. Execution time on RAND's IBM 7044, using the Geoffrion computer code (see RM-4783), was three seconds. Other objective functions are formulated in the study and additional constraints are modeled. Examples of larger problems rewritten for standard LP computer codes showed that the number of variables and constraints involved are probably within no more than one order of magnitude of the maximum number that could be handled with available zero-one computer codes.

This report is part of the RAND Corporation research memorandum series. The Research Memorandum was a product of the RAND Corporation from 1948 to 1973 that represented working papers meant to report current results of RAND research to appropriate audiences.

The RAND Corporation is a nonprofit institution that helps improve policy and decisionmaking through research and analysis. RAND's publications do not necessarily reflect the opinions of its research clients and sponsors.