Resource-constrained Machine Scheduling

Resource-constrained Machine Scheduling

Bonenkamp, Noortje (TU Delft Electrical Engineering, Mathematics and Computer Science; TU Delft Delft Institute of Applied Mathematics)

Janssen, Teun (mentor)
van Iersel, Leo (mentor)

Delft University of Technology

2017

Background
Scheduling is a form of decision-making that plays a very important
role in manufacturing industries. It is the method by which work
gets assigned to resources that compute it. In this thesis we want to assign
jobs (cycles of a lithography process) to different machines in such a way
that the machines are running for as little time as possible. The difficulty
lies in the fact that some jobs require the same resource, and thus cannot
be processed simultaneously.

Results
It appears that the following scheduling problems are NP-hard:
• P2kCmax and R2kCmax
• P3|res · 11, pj = 1|Cmax and R3|res · 11, pj = 1|Cmax
• P3|res · 11, pj = 1|
P Cj and R3|res · 11, pj = 1|
P Cj
We try to approximate an optimal solution for the scheduling problem
Rm|res · 11|
P Cj by calculating a ratio with a lower bound, where we ignore
resource constraints, and an upper bound, that is found by a Greedy
algorithm (w.r.t. resource constraints).

Conclusions
It appears that Greedy is not a very good approximation
algorithm for this problem, since the ratio in which the optimal Total
Completion Time should lie is about 8,33% of the average calculated Total
Completion Time

http://resolver.tudelft.nl/uuid:fa52773a-4362-4299-b7b2-eca491b6e4f2

Student theses

bachelor thesis

© 2017 Noortje Bonenkamp