{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/54214"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/54214","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Scheduling of biological samples for DNA sequencing","abstract":"In a DNA sequencing workflow, a biological sample has to pass through multiple process steps. Two consecutive steps are hydroshearing and library construction. Samples arrive randomly into the inventory and are to complete both processes before their due dates. The research project is to decide the optimal sequence of samples to go through these two processes subject to operational constraints. Two approaches, namely, heuristic and integer programming have been pursued in this thesis. A heuristic algorithm is proposed to solve the scheduling problem. A variant of the problem involving deterministic arrivals of samples is also considered for comparison purposes. Comparison tests between the two approaches are carried out to investigate the performance of the proposed heuristic for the original problem and its variant. Sensitivity analysis of the schedule to parameters of the problem is also conducted when using both approaches.","abstract_html":"In a DNA sequencing workflow, a biological sample has to pass through multiple process steps. Two consecutive steps are hydroshearing and library construction. Samples arrive randomly into the inventory and are to complete both processes before their due dates. The research project is to decide the optimal sequence of samples to go through these two processes subject to operational constraints. Two approaches, namely, heuristic and integer programming have been pursued in this thesis. A heuristic algorithm is proposed to solve the scheduling problem. A variant of the problem involving deterministic arrivals of samples is also considered for comparison purposes. Comparison tests between the two approaches are carried out to investigate the performance of the proposed heuristic for the original problem and its variant. Sensitivity analysis of the schedule to parameters of the problem is also conducted when using both approaches.","abstract_has_math":false,"creators":["Hu, Yuwei, S.M. Massachusetts Institute of Technology","Lim, Chin Soon"],"institution":"Massachusetts Institute of Technology","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Computation for Design and Optimization Program.","school":null,"contributors":[],"advisors":["Stephen Graves."],"committee_chairs":[],"committee_members":[],"year":2009,"date_issued":"2009","date_published":"2009","updated_at":"2026-07-22T22:22:09Z","subjects":["Computation for Design and Optimization Program."],"languages":["eng"],"rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"rights_urls":["http://dspace.mit.edu/handle/1721.1/7582"],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/1721.1/54214","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Stephen Graves."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Computation for Design and Optimization Program."]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Computation for Design and Optimization Program."]},{"key":"dc:creator","label":"Author","values":["Hu, Yuwei, S.M. Massachusetts Institute of Technology","Lim, Chin Soon"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2010-04-26T19:19:20Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2010-04-26T19:19:20Z"]},{"key":"dc:date.issued","label":"Date","values":["2009"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computation for Design and Optimization Program."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://dspace.mit.edu/handle/1721.1/7582"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/1721.1/54214"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis (S.M.)--Massachusetts Institute of Technology, Computation for Design and Optimization Program, 2009.","This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.","Cataloged from student submitted PDF version of thesis.","Includes bibliographical references (p. 95-97)."]},{"key":"dc:description.abstract","label":"Abstract","values":["In a DNA sequencing workflow, a biological sample has to pass through multiple process steps. Two consecutive steps are hydroshearing and library construction. Samples arrive randomly into the inventory and are to complete both processes before their due dates. The research project is to decide the optimal sequence of samples to go through these two processes subject to operational constraints. Two approaches, namely, heuristic and integer programming have been pursued in this thesis. A heuristic algorithm is proposed to solve the scheduling problem. A variant of the problem involving deterministic arrivals of samples is also considered for comparison purposes. Comparison tests between the two approaches are carried out to investigate the performance of the proposed heuristic for the original problem and its variant. Sensitivity analysis of the schedule to parameters of the problem is also conducted when using both approaches."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["S.M."]},{"key":"dc:title","label":"Title","values":["Scheduling of biological samples for DNA sequencing"]}]}],"canonical_facts":{"dc:contributor.advisor":["Stephen Graves."],"dc:contributor.department":["Massachusetts Institute of Technology. Computation for Design and Optimization Program."],"dc:contributor.other":["Massachusetts Institute of Technology. Computation for Design and Optimization Program."],"dc:creator":["Hu, Yuwei, S.M. Massachusetts Institute of Technology","Lim, Chin Soon"],"dc:date.accessioned":["2010-04-26T19:19:20Z"],"dc:date.available":["2010-04-26T19:19:20Z"],"dc:date.issued":["2009"],"dc:description":["Thesis (S.M.)--Massachusetts Institute of Technology, Computation for Design and Optimization Program, 2009.","This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.","Cataloged from student submitted PDF version of thesis.","Includes bibliographical references (p. 95-97)."],"dc:description.abstract":["In a DNA sequencing workflow, a biological sample has to pass through multiple process steps. Two consecutive steps are hydroshearing and library construction. Samples arrive randomly into the inventory and are to complete both processes before their due dates. The research project is to decide the optimal sequence of samples to go through these two processes subject to operational constraints. Two approaches, namely, heuristic and integer programming have been pursued in this thesis. A heuristic algorithm is proposed to solve the scheduling problem. A variant of the problem involving deterministic arrivals of samples is also considered for comparison purposes. Comparison tests between the two approaches are carried out to investigate the performance of the proposed heuristic for the original problem and its variant. Sensitivity analysis of the schedule to parameters of the problem is also conducted when using both approaches."],"dc:description.degree":["S.M."],"dc:identifier.uri":["http://hdl.handle.net/1721.1/54214"],"dc:language.iso":["eng"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"dc:rights.uri":["http://dspace.mit.edu/handle/1721.1/7582"],"dc:subject":["Computation for Design and Optimization Program."],"dc:title":["Scheduling of biological samples for DNA sequencing"],"dc:type":["Thesis"]},"updated_at":"2026-07-22T22:22:09Z"}