NOTE: This item is not available outside the Texas A&M University network. Texas A&M affiliated users who are off campus can access the item through NetID and password authentication or by using TAMU VPN. Non-affiliated individuals should request a copy through their local library's interlibrary loan service.
A nonlinear multiprocessor scheduling problem
dc.contributor.advisor | Pooch, Udo W. | |
dc.creator | Price, Camille Cook | |
dc.date.accessioned | 2020-01-08T17:22:32Z | |
dc.date.available | 2020-01-08T17:22:32Z | |
dc.date.created | 1979 | |
dc.identifier.uri | https://hdl.handle.net/1969.1/DISSERTATIONS-151743 | |
dc.description | Includes bibliographical references (leaves 102-107) | en |
dc.description.abstract | The problem addressed in this research is that of assigning modules of a computer program among processors in a distributed computer network having functionally similar nodes. The assignment is to be made in such a way as to take advantage of particular efficiencies of some processors for certain modules while minimizing the costs of communication between modules that are assigned to different processors. The problem is formulated as a zero-one nonlinear programming problem. A graph model is developed which provides a state-space representation of the problem, and a shortest path labeling algorithm is given which produces an assignment. A heuristic procedure is described which is a non-backtracking branch-and-bound technique, using a local neighborhood search at each stage. Suboptimal assignments are produced, but at considerable reduction in computation time and memory requirements, since only selected portions of the search graph are explored. Finally, an iterative transformation is defined on the solution space. A fixed point theorem is proved, guaranteeing that this procedure converges to a local optimum. Because this problem is known to belong to the class of NP-complete problems, the suboptimal assignments that are generally produced by these algorithms are considered acceptable. The shortest path algorithm yields optimal solutions when the search graph exhibits certain identifiable structural properties. The algorithms are implemented in computer programs and computational results are reported. | en |
dc.format.extent | ix, 108 leaves : illustrations | en |
dc.format.medium | electronic | en |
dc.format.mimetype | application/pdf | |
dc.language.iso | eng | |
dc.rights | This thesis was part of a retrospective digitization project authorized by the Texas A&M University Libraries. Copyright remains vested with the author(s). It is the user's responsibility to secure permission from the copyright holder(s) for re-use of the work beyond the provision of Fair Use. | en |
dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | |
dc.subject | Computing Science | en |
dc.subject | Nonlinear programming | en |
dc.subject | Production scheduling | en |
dc.subject.classification | 1979 Dissertation P945 | |
dc.subject.lcsh | Nonlinear programming | en |
dc.subject.lcsh | Production scheduling | en |
dc.title | A nonlinear multiprocessor scheduling problem | en |
dc.type | Thesis | en |
thesis.degree.discipline | Computing Science | en |
thesis.degree.grantor | Texas A&M University | en |
thesis.degree.name | Doctor of Philosophy | en |
thesis.degree.level | Doctoral | en |
thesis.degree.level | Doctorial | en |
dc.contributor.committeeMember | Barnes, Jack | |
dc.contributor.committeeMember | Lucido, A. P. | |
dc.contributor.committeeMember | Phillips, Don | |
dc.contributor.committeeMember | Rhyne, V. T. | |
dc.type.genre | dissertations | en |
dc.type.material | text | en |
dc.format.digitalOrigin | reformatted digital | en |
dc.publisher.digital | Texas A&M University. Libraries |
Files in this item
This item appears in the following Collection(s)
-
Digitized Theses and Dissertations (1922–2004)
Texas A&M University Theses and Dissertations (1922–2004)
Request Open Access
This item and its contents are restricted. If this is your thesis or dissertation, you can make it open-access. This will allow all visitors to view the contents of the thesis.