NETWORK FLOWS OVER EDGE-DISJOINT PATHS.
Abstract
An algorithm for the following parallel bottleneck assignment problem is developed: Each of two production lines consists of m different jobs arranged in a serial order. Each job requires one man and any man can be occupied in no more than one job with a processing rate. The rate of each line is determined by the minimum processing rate of the men along the line, the bottleneck. Find the assignment of men to jobs which maximizes the sum of the rates of the two lines. Two routes are said to be edge-disjoint if they share no edges. An algorithm is developed to find a pair of edge-disjoint routes the sum of whose capacities is maximized. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 30, 1968
- Accession Number
- AD0693139
Entities
People
- Hiroshi Takamori
Organizations
- Columbia University