Accession Number:

AD0672256

Title:

FINDING MINIMAL COST-TIME RATIO CIRCUITS,

Descriptive Note:

Corporate Author:

RAND CORP SANTA MONICA CALIF

Personal Author(s):

• Fox,Bennett

Report Date:

1968-06-01

Pagination or Media Count:

16.0

Abstract:

An efficient method is given for finding minimal cost-time ratio circuits in routing problems through the use of the out-of-kilter algorithm. The problem of finding a cycle in a network having a minimal cost-to-time ratio has been considered previously, and column generators have been used to introduce, into the basis of the master problem, the solution that corresponds to this cycle. The subproblem is of independent interest and corresponds to deterministic single chain Markov renewal programming. The main difference between earlier approaches and the present one is that where others have used a shortest path method corresponding to the simplex method except that steepest descent is not used, here the flow circulation problem for optimal cost-time tradeoff is solved parametrically by the out-of-kilter algorithm. Author

Descriptors:

• (*OPERATIONS RESEARCH
• SCHEDULING)
• (*NETWORKS
• SCHEDULING)
• (*SCHEDULING
• OPTIMIZATION)
• DYNAMIC PROGRAMMING
• LINEAR PROGRAMMING
• STATISTICAL PROCESSES
• ITERATIONS
• COSTS
• TIME
• ALGORITHMS
• PROBLEM SOLVING

Subject Categories:

• Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE