Convex conic relaxations of the scheduling problem

Montenegro Villota, Angela Liliana (2013). Convex conic relaxations of the scheduling problem. University of Birmingham. Ph.D.

PDF - Accepted Version

Download (834kB)


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.

Type of Work: Thesis (Doctorates > Ph.D.)
Award Type: Doctorates > Ph.D.
College/Faculty: Colleges (2008 onwards) > College of Engineering & Physical Sciences
School or Department: School of Mathematics
Funders: None/not applicable
Subjects: Q Science > QA Mathematics


Request a Correction Request a Correction
View Item View Item


Downloads per month over past year