{"id":{"repo_id":"odu","oai_identifier":"oai:digitalcommons.odu.edu:computerscience_etds-1163"},"canonical_url":"https://search.ndltd.org/etd/odu/oai:digitalcommons.odu.edu:computerscience_etds-1163","repository":{"repo_id":"odu","name":"Old Dominion University","base_url":"https://digitalcommons.odu.edu/do/oai/"},"display":{"title":"Two Approaches to Critical Path Scheduling for a Heterogeneous Environment","abstract":"Advances in computing and networking technologies are making large scale distributed heterogeneous computing a reality. Multi-Disciplinary Optimization (MDO) is a class of applications that is being addressed under this paradigm. It consists of multiple heterogeneous modules interacting with each other to solve an overall design problem. An efficient implementation of such an application requires scheduling heterogeneous modules (with different computing and disk 1/0 requirements) on a heterogeneous set of resources (with different CPU, memory, disk IO specifications). Given a set of tasks and a set of resources, an optimal schedule of the tasks on the resources is very hard to compute (NP-Complete). In this study, we focus on scheduling of coarse grained tasks on heterogeneous resources. We propose two algorithms based on the classic static Critical Path Method (CPM). CPM has been suggested for homogeneous environments. We adapt this method for a heterogeneous environment. One of the proposed algorithms, named EA-CPM, maps a highest priority ready task to a processor that ensures its earliest assignment. The other algorithm, called EF-CPM, assigns a highest priority ready task to a processor that yields the earliest finishing time. We describe a series of qualitative, systematic numerical studies for evaluating algorithms. Overall, the performance of both algorithms is very promising. In particular, EF-CPM is close to the locally optimal solution obtained by the branch exhaustive search method.","abstract_html":"Advances in computing and networking technologies are making large scale distributed heterogeneous computing a reality. Multi-Disciplinary Optimization (MDO) is a class of applications that is being addressed under this paradigm. It consists of multiple heterogeneous modules interacting with each other to solve an overall design problem. An efficient implementation of such an application requires scheduling heterogeneous modules (with different computing and disk 1/0 requirements) on a heterogeneous set of resources (with different CPU, memory, disk IO specifications). Given a set of tasks and a set of resources, an optimal schedule of the tasks on the resources is very hard to compute (NP-Complete). In this study, we focus on scheduling of coarse grained tasks on heterogeneous resources. We propose two algorithms based on the classic static Critical Path Method (CPM). CPM has been suggested for homogeneous environments. We adapt this method for a heterogeneous environment. One of the proposed algorithms, named EA-CPM, maps a highest priority ready task to a processor that ensures its earliest assignment. The other algorithm, called EF-CPM, assigns a highest priority ready task to a processor that yields the earliest finishing time. We describe a series of qualitative, systematic numerical studies for evaluating algorithms. Overall, the performance of both algorithms is very promising. In particular, EF-CPM is close to the locally optimal solution obtained by the branch exhaustive search method.","abstract_has_math":false,"creators":["Liu, Guangxia"],"institution":null,"degree_name":"Master of Science (MS)","degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Mohammad Zubair","Piyush Mehrotra","Kurt Maly","David Keyes"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":null,"date_issued":"","date_published":null,"updated_at":"2026-11-19T08:29:47Z","subjects":["Heterogeneous computing","Computer programs","Mathematical optimization","Digital Communications and Networking","Systems Architecture","Theory and Algorithms"],"languages":[],"rights":["<p>In Copyright. URI: <a href=\"http://rightsstatements.org/vocab/InC/1.0/\">http://rightsstatements.org/vocab/InC/1.0/</a> This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).</p>"],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[]},"links":{"outbound_url":"https://digitalcommons.odu.edu/computerscience_etds/156","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://digitalcommons.odu.edu/computerscience_etds/156","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://digitalcommons.odu.edu/do/oai/?verb=GetRecord&metadataPrefix=oai_etdms&identifier=oai%3Adigitalcommons.odu.edu%3Acomputerscience_etds-1163","prefix":"oai_etdms"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Mohammad Zubair","Piyush Mehrotra","Kurt Maly","David Keyes"]},{"key":"dc:creator","label":"Author","values":["Liu, Guangxia"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2023-10-24T07:00:00Z"]},{"key":"dc:date.created","label":"Dc Date Created","values":["1999-05-01T07:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science (MS)"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Heterogeneous computing","Computer programs","Mathematical optimization","Digital Communications and Networking","Systems Architecture","Theory and Algorithms"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["<p>In Copyright. URI: <a href=\"http://rightsstatements.org/vocab/InC/1.0/\">http://rightsstatements.org/vocab/InC/1.0/</a> This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).</p>"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.odu.edu/computerscience_etds/156"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Advances in computing and networking technologies are making large scale distributed heterogeneous computing a reality. Multi-Disciplinary Optimization (MDO) is a class of applications that is being addressed under this paradigm. It consists of multiple heterogeneous modules interacting with each other to solve an overall design problem. An efficient implementation of such an application requires scheduling heterogeneous modules (with different computing and disk 1/0 requirements) on a heterogeneous set of resources (with different CPU, memory, disk IO specifications). Given a set of tasks and a set of resources, an optimal schedule of the tasks on the resources is very hard to compute (NP-Complete). In this study, we focus on scheduling of coarse grained tasks on heterogeneous resources. We propose two algorithms based on the classic static Critical Path Method (CPM). CPM has been suggested for homogeneous environments. We adapt this method for a heterogeneous environment. One of the proposed algorithms, named EA-CPM, maps a highest priority ready task to a processor that ensures its earliest assignment. The other algorithm, called EF-CPM, assigns a highest priority ready task to a processor that yields the earliest finishing time. We describe a series of qualitative, systematic numerical studies for evaluating algorithms. Overall, the performance of both algorithms is very promising. In particular, EF-CPM is close to the locally optimal solution obtained by the branch exhaustive search method."]},{"key":"dc:title","label":"Title","values":["Two Approaches to Critical Path Scheduling for a Heterogeneous Environment"]}]}],"canonical_facts":{"dc:contributor":["Mohammad Zubair","Piyush Mehrotra","Kurt Maly","David Keyes"],"dc:creator":["Liu, Guangxia"],"dc:date.available":["2023-10-24T07:00:00Z"],"dc:date.created":["1999-05-01T07:00:00Z"],"dc:description.abstract":["Advances in computing and networking technologies are making large scale distributed heterogeneous computing a reality. Multi-Disciplinary Optimization (MDO) is a class of applications that is being addressed under this paradigm. It consists of multiple heterogeneous modules interacting with each other to solve an overall design problem. An efficient implementation of such an application requires scheduling heterogeneous modules (with different computing and disk 1/0 requirements) on a heterogeneous set of resources (with different CPU, memory, disk IO specifications). Given a set of tasks and a set of resources, an optimal schedule of the tasks on the resources is very hard to compute (NP-Complete). In this study, we focus on scheduling of coarse grained tasks on heterogeneous resources. We propose two algorithms based on the classic static Critical Path Method (CPM). CPM has been suggested for homogeneous environments. We adapt this method for a heterogeneous environment. One of the proposed algorithms, named EA-CPM, maps a highest priority ready task to a processor that ensures its earliest assignment. The other algorithm, called EF-CPM, assigns a highest priority ready task to a processor that yields the earliest finishing time. We describe a series of qualitative, systematic numerical studies for evaluating algorithms. Overall, the performance of both algorithms is very promising. In particular, EF-CPM is close to the locally optimal solution obtained by the branch exhaustive search method."],"dc:identifier":["https://digitalcommons.odu.edu/computerscience_etds/156"],"dc:rights":["<p>In Copyright. URI: <a href=\"http://rightsstatements.org/vocab/InC/1.0/\">http://rightsstatements.org/vocab/InC/1.0/</a> This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).</p>"],"dc:subject":["Heterogeneous computing","Computer programs","Mathematical optimization","Digital Communications and Networking","Systems Architecture","Theory and Algorithms"],"dc:title":["Two Approaches to Critical Path Scheduling for a Heterogeneous Environment"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["Master of Science (MS)"]},"updated_at":"2026-11-19T08:29:47Z"}