A Zero-One Programming Approach to Scheduling with Limited Resources

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.