Doctoral Dissertations

Abstract

"A parallel branch and bound algorithm is developed for use with MIMD computers to study the efficiency of parallel processors on general integer linear programming problems. The Haldi and IBM test problems and a System Design model are used in the implementation of the algorithm. Initially the algorithm solves the Haldi and IBM test problems on a single processor computer which simulates a multiple processor computer. The algorithm is then implemented on the Denelcor HEP multiprocessor using two of the IBM problems to compare the results of the simulation to the results using an MIMD computer. Finally the algorithm is implemented on the HEP using the System Design model to show a case in which the number of pivots decreases as the number of processes are increased from seven to the process limit of sixteen.

In general, it is shown that super linear efficiency can be achieved using multiple processors"--Abstract, page ii.

Advisor(s)

Gillett, Billy E.

Committee Member(s)

Rigler, A. K.
Dekock, Arlan R.
Prater, John Bruce, 1932-2002
Grimm, L. J.

Department(s)

Computer Science

Degree Name

Ph. D. in Computer Science

Publisher

University of Missouri--Rolla

Publication Date

Summer 1985

Pagination

vii, 104 pages

Note about bibliography

Includes bibliographical references (pages 59-64).

Rights

© 1985 Rochelle Lloyd Boehning, All rights reserved.

Document Type

Dissertation - Open Access

File Type

text

Language

English

Thesis Number

T 5212

Print OCLC #

13429691

Download

Share

 
COinS