Accession Number : AD0664551

Title :   A ZERO-ONE PROGRAMMING APPROACH TO SCHEDULING WITH LIMITED RESOURCES,

Corporate Author : RAND CORP SANTA MONICA CALIF

Personal Author(s) : Pritsker,A. A. B. ; Watters,L. J.

Report Date : JAN 1968

Pagination or Media Count : 57

Abstract : A zero-one linear programming 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 3-project, 8-job, 3-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 an IBM 7044, using the Geoffrion computer code was 3 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. (Author)

Descriptors :   (*SCHEDULING, OPERATIONS RESEARCH), (*LINEAR PROGRAMMING, OPERATIONS RESEARCH), NUMERICAL METHODS AND PROCEDURES, QUEUEING THEORY, MAINTENANCE, PROBLEM SOLVING, COMPUTER PROGRAMMING, ALGORITHMS

Subject Categories : Operations Research
      Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE