{"id":{"repo_id":"rice","oai_identifier":"oai:repository.rice.edu:1911/104536"},"canonical_url":"https://search.dev.ndltd.org/etd/rice/oai:repository.rice.edu:1911/104536","repository":{"repo_id":"rice","name":"Rice University","base_url":"https://repository.rice.edu/server/oai/request"},"display":{"title":"Heuristic algorithms for distributed processor scheduling with limited memory","abstract":"This thesis studies a heuristic approach to scheduling •on a 2-processor distributed system when one processor has a limited memory. A program is assumed to consist of a set of sequentially executing modules and is represented by Stone's graph model. It is desired to assign these modules to the processors so as to minimize interprocessor communication while taking advantage of specific capabilities of the two processors. This optimization problem is NP-complete. It is shown that the corresponding 'absolute approximation' problem is as hard. For the classes of constant degree and constant connectivity graphs statistics are presented to support the conjecture of Rao, Stone and Hu that use of the 'inclusive-cuts graph' can appreciably simplify this scheduling problem. Asymptotic upper and lower bounds on the expected cost of the optimum assignment are derived for the class of constant degree graphs. These results motivate the development and assist the evaluation of two polynomial-time heuristic algorithms for 2-processor scheduling with limited memory. For constant degree graphs it is shown that the heuristics can be useful scheduling tools. It is also shown that use of the inclusive-cuts graph can lead to an improvement in performance, but at the expense of additional scheduling overhead. An ancillary result proved is a relationship between scheduling with limited memory and scheduling when one processor is multiprogrammed and has a variable load factor. Some implications of this relationship are discussed.","abstract_html":"This thesis studies a heuristic approach to scheduling •on a 2-processor distributed system when one processor has a limited memory. A program is assumed to consist of a set of sequentially executing modules and is represented by Stone's graph model. It is desired to assign these modules to the processors so as to minimize interprocessor communication while taking advantage of specific capabilities of the two processors. This optimization problem is NP-complete. It is shown that the corresponding 'absolute approximation' problem is as hard. For the classes of constant degree and constant connectivity graphs statistics are presented to support the conjecture of Rao, Stone and Hu that use of the 'inclusive-cuts graph' can appreciably simplify this scheduling problem. Asymptotic upper and lower bounds on the expected cost of the optimum assignment are derived for the class of constant degree graphs. These results motivate the development and assist the evaluation of two polynomial-time heuristic algorithms for 2-processor scheduling with limited memory. For constant degree graphs it is shown that the heuristics can be useful scheduling tools. It is also shown that use of the inclusive-cuts graph can lead to an improvement in performance, but at the expense of additional scheduling overhead. An ancillary result proved is a relationship between scheduling with limited memory and scheduling when one processor is multiprogrammed and has a variable load factor. Some implications of this relationship are discussed.","abstract_has_math":false,"creators":["Gonsalves, Timothy A."],"institution":"Rice University","degree_name":"Master of Science","degree_level":"Masters","degree_discipline":"Engineering","degree_department":null,"school":null,"contributors":[],"advisors":["Rao, G. S."],"committee_chairs":[],"committee_members":[],"year":1979,"date_issued":"1979","date_published":"1979","updated_at":"2026-07-24T04:10:17Z","subjects":[],"languages":["eng"],"rights":["Copyright is held by the author, unless otherwise indicated. Permission to reuse, publish, or reproduce the work beyond the bounds of fair use or other exemptions to copyright law must be obtained from the copyright holder."],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1911/104536","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Rao, G. S."]},{"key":"dc:creator","label":"Author","values":["Gonsalves, Timothy A."]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2018-12-18T21:25:03Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2018-12-18T21:25:03Z"]},{"key":"dc:date.issued","label":"Date","values":["1979"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Masters"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Rice University"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright is held by the author, unless otherwise indicated. Permission to reuse, publish, or reproduce the work beyond the bounds of fair use or other exemptions to copyright law must be obtained from the copyright holder."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1911/104536"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["This thesis studies a heuristic approach to scheduling •on a 2-processor distributed system when one processor has a limited memory. A program is assumed to consist of a set of sequentially executing modules and is represented by Stone's graph model. It is desired to assign these modules to the processors so as to minimize interprocessor communication while taking advantage of specific capabilities of the two processors. This optimization problem is NP-complete. It is shown that the corresponding 'absolute approximation' problem is as hard. For the classes of constant degree and constant connectivity graphs statistics are presented to support the conjecture of Rao, Stone and Hu that use of the 'inclusive-cuts graph' can appreciably simplify this scheduling problem. Asymptotic upper and lower bounds on the expected cost of the optimum assignment are derived for the class of constant degree graphs. These results motivate the development and assist the evaluation of two polynomial-time heuristic algorithms for 2-processor scheduling with limited memory. For constant degree graphs it is shown that the heuristics can be useful scheduling tools. It is also shown that use of the inclusive-cuts graph can lead to an improvement in performance, but at the expense of additional scheduling overhead. An ancillary result proved is a relationship between scheduling with limited memory and scheduling when one processor is multiprogrammed and has a variable load factor. Some implications of this relationship are discussed."]},{"key":"dc:title","label":"Title","values":["Heuristic algorithms for distributed processor scheduling with limited memory"]}]}],"canonical_facts":{"dc:contributor.advisor":["Rao, G. S."],"dc:creator":["Gonsalves, Timothy A."],"dc:date.accessioned":["2018-12-18T21:25:03Z"],"dc:date.available":["2018-12-18T21:25:03Z"],"dc:date.issued":["1979"],"dc:description.abstract":["This thesis studies a heuristic approach to scheduling •on a 2-processor distributed system when one processor has a limited memory. A program is assumed to consist of a set of sequentially executing modules and is represented by Stone's graph model. It is desired to assign these modules to the processors so as to minimize interprocessor communication while taking advantage of specific capabilities of the two processors. This optimization problem is NP-complete. It is shown that the corresponding 'absolute approximation' problem is as hard. For the classes of constant degree and constant connectivity graphs statistics are presented to support the conjecture of Rao, Stone and Hu that use of the 'inclusive-cuts graph' can appreciably simplify this scheduling problem. Asymptotic upper and lower bounds on the expected cost of the optimum assignment are derived for the class of constant degree graphs. These results motivate the development and assist the evaluation of two polynomial-time heuristic algorithms for 2-processor scheduling with limited memory. For constant degree graphs it is shown that the heuristics can be useful scheduling tools. It is also shown that use of the inclusive-cuts graph can lead to an improvement in performance, but at the expense of additional scheduling overhead. An ancillary result proved is a relationship between scheduling with limited memory and scheduling when one processor is multiprogrammed and has a variable load factor. Some implications of this relationship are discussed."],"dc:identifier.uri":["https://hdl.handle.net/1911/104536"],"dc:language.iso":["eng"],"dc:rights":["Copyright is held by the author, unless otherwise indicated. Permission to reuse, publish, or reproduce the work beyond the bounds of fair use or other exemptions to copyright law must be obtained from the copyright holder."],"dc:title":["Heuristic algorithms for distributed processor scheduling with limited memory"],"dc:type":["Thesis"],"thesis:degree_discipline":["Engineering"],"thesis:degree_level":["Masters"],"thesis:degree_name":["Master of Science"],"thesis:institution_name":["Rice University"]},"updated_at":"2026-07-24T04:10:17Z"}