{"id":{"repo_id":"birmingham","oai_identifier":"oai:etheses.bham.ac.uk:4221"},"canonical_url":"https://search.ndltd.org/etd/birmingham/oai:etheses.bham.ac.uk:4221","repository":{"repo_id":"birmingham","name":"University of Birmingham","base_url":"https://etheses.bham.ac.uk/cgi/oai2"},"display":{"title":"Convex conic relaxations of the scheduling problem","abstract":"Scheduling has been used to describe a resources optimization problem since the early 1950's and plays an important role in domains such as manufacturing, transportation, distribution, construction, engineering, and management. A scheduling problem is defined by determining a production environment, job characteristics, scheduling constraints and an objective function which yields to different cases of the problem. As a result a variety of complexity arises among scheduling problems ranging from polynomially solvable to NP-hard problems. In this thesis two scheduling problem formulations are studied. The scheduling problem in a single machine environment, with equal-length jobs and release dates, with the objective function of minimizing total weighted tardiness (1\\(\\vert\\)p\\(_j\\) = p,r\\(_j\\)\\(\\vert\\)\\(\\sum\\)w\\(_j\\)T\\(_j\\)), whose complexity was still unknown, is shown to be solvable to optimality in polynomial time. The same is concluded for the related case with similar characteristics but minimizing weighted tardiness together with the maximum completion time, also known as the makespan. The second problem studied occurs in a single machine environment, with release dates and interruption of the processing allowed, with the objective of minimizing weighted completion time (1\\(\\vert\\)r\\(_j\\),pmtn\\(\\vert\\)\\(\\sum\\) w\\(_j\\)C\\(_j\\)). For this case three convex conic relaxations, based on semidefinite and linear programming, to use in conjunction with a customised branch and bound algorithm, are developed. The algorithm can be used to solve efficiently any size of the problem provided the maximum number of jobs at any time is 7.","abstract_html":"Scheduling has been used to describe a resources optimization problem since the early 1950&#x27;s and plays an important role in domains such as manufacturing, transportation, distribution, construction, engineering, and management. A scheduling problem is defined by determining a production environment, job characteristics, scheduling constraints and an objective function which yields to different cases of the problem. As a result a variety of complexity arises among scheduling problems ranging from polynomially solvable to NP-hard problems. In this thesis two scheduling problem formulations are studied. The scheduling problem in a single machine environment, with equal-length jobs and release dates, with the objective function of minimizing total weighted tardiness (1\\(\\vert\\)p<span class=\"etd-inline-math\"><sub>j</sub></span> = p,r<span class=\"etd-inline-math\"><sub>j</sub></span>\\(\\vert\\)\\(\\sum\\)w<span class=\"etd-inline-math\"><sub>j</sub></span>T<span class=\"etd-inline-math\"><sub>j</sub></span>), whose complexity was still unknown, is shown to be solvable to optimality in polynomial time. The same is concluded for the related case with similar characteristics but minimizing weighted tardiness together with the maximum completion time, also known as the makespan. The second problem studied occurs in a single machine environment, with release dates and interruption of the processing allowed, with the objective of minimizing weighted completion time (1\\(\\vert\\)r<span class=\"etd-inline-math\"><sub>j</sub></span>,pmtn\\(\\vert\\)\\(\\sum\\) w<span class=\"etd-inline-math\"><sub>j</sub></span>C<span class=\"etd-inline-math\"><sub>j</sub></span>). For this case three convex conic relaxations, based on semidefinite and linear programming, to use in conjunction with a customised branch and bound algorithm, are developed. The algorithm can be used to solve efficiently any size of the problem provided the maximum number of jobs at any time is 7.","abstract_has_math":true,"creators":["Montenegro Villota, Angela Liliana"],"institution":"University of Birmingham","degree_name":"d_ph","degree_level":"d_ph","degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2013,"date_issued":"2013-07","date_published":"2013-07","updated_at":"2026-11-19T09:27:36Z","subjects":["QA Mathematics"],"languages":["eng"],"rights":[],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[]},"links":{"outbound_url":null,"outbound_label":null,"outbound_source":null,"record_url":null,"record_label":null,"record_kind":null,"record_source":null,"download_url":"http://etheses.bham.ac.uk//id/eprint/4221/1/Montenegro-Villota13PhD.pdf","download_label":"Download PDF","download_source":"dc:identifier.uri","access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://etheses.bham.ac.uk/cgi/oai2?verb=GetRecord&metadataPrefix=uketd_dc&identifier=oai%3Aetheses.bham.ac.uk%3A4221","prefix":"uketd_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.sponsor","label":"Sponsor","values":["na"]},{"key":"dc:creator","label":"Author","values":["Montenegro Villota, Angela Liliana"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2013-07"]},{"key":"dc:date.issued","label":"Date","values":["2013-07"]},{"key":"dc:publisher.department","label":"Dc Publisher Department","values":["College of Engineering & Physical Sciences","School of Mathematics"]},{"key":"dc:publisher.institution","label":"Dc Publisher Institution","values":["University of Birmingham"]},{"key":"dc:relation.isreferencedby","label":"Dc Relation Isreferencedby","values":["http://etheses.bham.ac.uk//id/eprint/4221/"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"dc:type.qualificationlevel","label":"Dc Type Qualificationlevel","values":["d_ph"]},{"key":"dc:type.qualificationname","label":"Dc Type Qualificationname","values":["d_ph"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["QA Mathematics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.dcterms_iso639_2","label":"Language (ISO 639-2)","values":["eng"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://etheses.bham.ac.uk//id/eprint/4221/1/Montenegro-Villota13PhD.pdf","http://etheses.bham.ac.uk//id/eprint/4221/2/Decl_IS_Montenegro-Villota13PhD.pdf"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Scheduling has been used to describe a resources optimization problem since the early 1950's and plays an important role in domains such as manufacturing, transportation, distribution, construction, engineering, and management. A scheduling problem is defined by determining a production environment, job characteristics, scheduling constraints and an objective function which yields to different cases of the problem. As a result a variety of complexity arises among scheduling problems ranging from polynomially solvable to NP-hard problems. In this thesis two scheduling problem formulations are studied. The scheduling problem in a single machine environment, with equal-length jobs and release dates, with the objective function of minimizing total weighted tardiness (1\\(\\vert\\)p\\(_j\\) = p,r\\(_j\\)\\(\\vert\\)\\(\\sum\\)w\\(_j\\)T\\(_j\\)), whose complexity was still unknown, is shown to be solvable to optimality in polynomial time. The same is concluded for the related case with similar characteristics but minimizing weighted tardiness together with the maximum completion time, also known as the makespan. The second problem studied occurs in a single machine environment, with release dates and interruption of the processing allowed, with the objective of minimizing weighted completion time (1\\(\\vert\\)r\\(_j\\),pmtn\\(\\vert\\)\\(\\sum\\) w\\(_j\\)C\\(_j\\)). For this case three convex conic relaxations, based on semidefinite and linear programming, to use in conjunction with a customised branch and bound algorithm, are developed. The algorithm can be used to solve efficiently any size of the problem provided the maximum number of jobs at any time is 7."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dcterms:accessrights","label":"Dcterms Accessrights","values":["public","staffonly"]},{"key":"dc:title","label":"Title","values":["Convex conic relaxations of the scheduling problem"]}]}],"canonical_facts":{"dc:contributor.sponsor":["na"],"dc:creator":["Montenegro Villota, Angela Liliana"],"dc:date":["2013-07"],"dc:date.issued":["2013-07"],"dc:description.abstract":["Scheduling has been used to describe a resources optimization problem since the early 1950's and plays an important role in domains such as manufacturing, transportation, distribution, construction, engineering, and management. A scheduling problem is defined by determining a production environment, job characteristics, scheduling constraints and an objective function which yields to different cases of the problem. As a result a variety of complexity arises among scheduling problems ranging from polynomially solvable to NP-hard problems. In this thesis two scheduling problem formulations are studied. The scheduling problem in a single machine environment, with equal-length jobs and release dates, with the objective function of minimizing total weighted tardiness (1\\(\\vert\\)p\\(_j\\) = p,r\\(_j\\)\\(\\vert\\)\\(\\sum\\)w\\(_j\\)T\\(_j\\)), whose complexity was still unknown, is shown to be solvable to optimality in polynomial time. The same is concluded for the related case with similar characteristics but minimizing weighted tardiness together with the maximum completion time, also known as the makespan. The second problem studied occurs in a single machine environment, with release dates and interruption of the processing allowed, with the objective of minimizing weighted completion time (1\\(\\vert\\)r\\(_j\\),pmtn\\(\\vert\\)\\(\\sum\\) w\\(_j\\)C\\(_j\\)). For this case three convex conic relaxations, based on semidefinite and linear programming, to use in conjunction with a customised branch and bound algorithm, are developed. The algorithm can be used to solve efficiently any size of the problem provided the maximum number of jobs at any time is 7."],"dc:format":["application/pdf"],"dc:identifier.uri":["http://etheses.bham.ac.uk//id/eprint/4221/1/Montenegro-Villota13PhD.pdf","http://etheses.bham.ac.uk//id/eprint/4221/2/Decl_IS_Montenegro-Villota13PhD.pdf"],"dc:language.dcterms_iso639_2":["eng"],"dc:publisher.department":["College of Engineering & Physical Sciences","School of Mathematics"],"dc:publisher.institution":["University of Birmingham"],"dc:relation.isreferencedby":["http://etheses.bham.ac.uk//id/eprint/4221/"],"dc:subject":["QA Mathematics"],"dcterms:accessrights":["public","staffonly"],"dc:title":["Convex conic relaxations of the scheduling problem"],"dc:type":["Thesis"],"dc:type.qualificationlevel":["d_ph"],"dc:type.qualificationname":["d_ph"]},"updated_at":"2026-11-19T09:27:36Z"}