Convex conic relaxations of the scheduling problem

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

Preview

Montenegro-Villota13PhD.pdf
PDF - Accepted Version
Download (834kB)

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.

Type of Work:

Thesis (Doctorates > Ph.D.)

Award Type:

Doctorates > Ph.D.

Supervisor(s):