{"id":{"repo_id":"vt","oai_identifier":"oai:vtechworks.lib.vt.edu:10919/36732"},"canonical_url":"https://search.ndltd.org/etd/vt/oai:vtechworks.lib.vt.edu:10919/36732","repository":{"repo_id":"vt","name":"Virginia Tech","base_url":"https://vtechworks.lib.vt.edu/oai/request"},"display":{"title":"Bi-criteria Scheduling Problems on Parallel Machines","abstract":"Mathematical programming has not been used extensively for the solution of scheduling problems. Moreover, the study of bicriteria problems on single and parallel machines is an open field for research. This thesis is aimed at developing algorithms to solve bicriteria problems more efficiently and in reasonable amount of time and with little compromise on the optimality of the solutions obtained. Two classes of problems are considered. The first class consists of scheduling unit duration tasks on parallel machines. Various combinations of primary and secondary criteria are considered and optimal seeking algorithms of polynomial time complexity are developed. The second class of problems assume general processing time tasks. An algorithm is developed for the primary criterion of total tardiness and the secondary criterion of total flow time. This algorithm is based on the solution of the underlying mathematical program and makes use of dominance relationship among the jobs and fixing of variables. Experimental results are presented regarding its performance.","abstract_html":"Mathematical programming has not been used extensively for the solution of scheduling problems. Moreover, the study of bicriteria problems on single and parallel machines is an open field for research. This thesis is aimed at developing algorithms to solve bicriteria problems more efficiently and in reasonable amount of time and with little compromise on the optimality of the solutions obtained. Two classes of problems are considered. The first class consists of scheduling unit duration tasks on parallel machines. Various combinations of primary and secondary criteria are considered and optimal seeking algorithms of polynomial time complexity are developed. The second class of problems assume general processing time tasks. An algorithm is developed for the primary criterion of total tardiness and the secondary criterion of total flow time. This algorithm is based on the solution of the underlying mathematical program and makes use of dominance relationship among the jobs and fixing of variables. Experimental results are presented regarding its performance.","abstract_has_math":false,"creators":["Prakash, Divya"],"institution":"Virginia Tech","degree_name":"Master of Science","degree_level":"masters","degree_discipline":"Industrial and Systems Engineering","degree_department":"Industrial and Systems Engineering","school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":["Kobza, John E.","Sherali, Hanif D.","Sarin, Subhash C."],"year":1995,"date_issued":"1995-07-20","date_published":"1995-07-20","updated_at":"2026-11-18T20:02:44Z","subjects":["none"],"languages":[],"rights":["In Copyright"],"rights_urls":["http://rightsstatements.org/vocab/InC/1.0/"],"identifier_entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["etd-4621112149731401"],"render_values":[{"text":"etd-4621112149731401","href":null,"code":true}]},{"key":"dc:identifier.sourceurl","label":"Source URL","values":["http://scholar.lib.vt.edu/theses/available/etd-4621112149731401/"],"render_values":[{"text":"http://scholar.lib.vt.edu/theses/available/etd-4621112149731401/","href":"http://scholar.lib.vt.edu/theses/available/etd-4621112149731401/","code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/10919/36732","outbound_label":"Handle","outbound_source":"dc:identifier.uri","record_url":"http://hdl.handle.net/10919/36732","record_label":"Repository record","record_kind":"handle","record_source":"dc:identifier.uri","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://vtechworks.lib.vt.edu/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Avtechworks.lib.vt.edu%3A10919%2F36732","prefix":"dim"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.committeemember","label":"Committee Member","values":["Kobza, John E.","Sherali, Hanif D.","Sarin, Subhash C."]},{"key":"dc:contributor.department","label":"Department","values":["Industrial and Systems Engineering"]},{"key":"dc:creator","label":"Author","values":["Prakash, Divya"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accepted","label":"Dc Date Accepted","values":["1995-07-20"]},{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2014-03-14T20:51:36Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2014-03-14T20:51:36Z","1995-07-20"]},{"key":"dc:date.issued","label":"Date","values":["1995-07-20"]},{"key":"dc:date.submitted","label":"Dc Date Submitted","values":["1998-07-21"]},{"key":"dc:publisher","label":"Institution","values":["Virginia Tech"]},{"key":"dc:relation.haspart","label":"Dc Relation Haspart","values":["etd.pdf","edt.pdf"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Industrial and Systems 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":["Virginia Polytechnic Institute and State University"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["none"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["In Copyright"]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://rightsstatements.org/vocab/InC/1.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["etd-4621112149731401"]},{"key":"dc:identifier.sourceurl","label":"Source URL","values":["http://scholar.lib.vt.edu/theses/available/etd-4621112149731401/"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/10919/36732"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Mathematical programming has not been used extensively for the solution of scheduling problems. Moreover, the study of bicriteria problems on single and parallel machines is an open field for research. This thesis is aimed at developing algorithms to solve bicriteria problems more efficiently and in reasonable amount of time and with little compromise on the optimality of the solutions obtained. Two classes of problems are considered. The first class consists of scheduling unit duration tasks on parallel machines. Various combinations of primary and secondary criteria are considered and optimal seeking algorithms of polynomial time complexity are developed. The second class of problems assume general processing time tasks. An algorithm is developed for the primary criterion of total tardiness and the secondary criterion of total flow time. This algorithm is based on the solution of the underlying mathematical program and makes use of dominance relationship among the jobs and fixing of variables. Experimental results are presented regarding its performance."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Master of Science"]},{"key":"dc:title","label":"Title","values":["Bi-criteria Scheduling Problems on Parallel Machines"]}]}],"canonical_facts":{"dc:contributor.committeemember":["Kobza, John E.","Sherali, Hanif D.","Sarin, Subhash C."],"dc:contributor.department":["Industrial and Systems Engineering"],"dc:creator":["Prakash, Divya"],"dc:date.accepted":["1995-07-20"],"dc:date.accessioned":["2014-03-14T20:51:36Z"],"dc:date.available":["2014-03-14T20:51:36Z","1995-07-20"],"dc:date.issued":["1995-07-20"],"dc:date.submitted":["1998-07-21"],"dc:description.abstract":["Mathematical programming has not been used extensively for the solution of scheduling problems. Moreover, the study of bicriteria problems on single and parallel machines is an open field for research. This thesis is aimed at developing algorithms to solve bicriteria problems more efficiently and in reasonable amount of time and with little compromise on the optimality of the solutions obtained. Two classes of problems are considered. The first class consists of scheduling unit duration tasks on parallel machines. Various combinations of primary and secondary criteria are considered and optimal seeking algorithms of polynomial time complexity are developed. The second class of problems assume general processing time tasks. An algorithm is developed for the primary criterion of total tardiness and the secondary criterion of total flow time. This algorithm is based on the solution of the underlying mathematical program and makes use of dominance relationship among the jobs and fixing of variables. Experimental results are presented regarding its performance."],"dc:description.degree":["Master of Science"],"dc:identifier.other":["etd-4621112149731401"],"dc:identifier.sourceurl":["http://scholar.lib.vt.edu/theses/available/etd-4621112149731401/"],"dc:identifier.uri":["http://hdl.handle.net/10919/36732"],"dc:publisher":["Virginia Tech"],"dc:relation.haspart":["etd.pdf","edt.pdf"],"dc:rights":["In Copyright"],"dc:rights.uri":["http://rightsstatements.org/vocab/InC/1.0/"],"dc:subject":["none"],"dc:title":["Bi-criteria Scheduling Problems on Parallel Machines"],"dc:type":["Thesis"],"thesis:degree_discipline":["Industrial and Systems Engineering"],"thesis:degree_level":["masters"],"thesis:degree_name":["Master of Science"],"thesis:institution_name":["Virginia Polytechnic Institute and State University"]},"updated_at":"2026-11-18T20:02:44Z"}