Back to search

University of Birmingham

Convex conic relaxations of the scheduling problem

Abstract

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\)pj = p,rj\(\vert\)\(\sum\)wjTj), 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\)rj,pmtn\(\vert\)\(\sum\) wjCj). 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.

Degree

thesis:*
Name dc:type.qualificationname
d_ph
Level dc:type.qualificationlevel
d_ph
Grantor dc:publisher.institution
University of Birmingham
Year dc:date.issued
2013

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Montenegro Villota, Angela Liliana

Subjects

dc:subject × 1

Rights

Language dc:language.dcterms_iso639_2
eng

Chain of custody

source
Harvested from
University of Birmingham
Base URL
etheses.bham.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Montenegro Villota, Angela Liliana. Convex conic relaxations of the scheduling problem. d_ph thesis, University of Birmingham, 2013.