Resource-constrained Machine Scheduling

Bachelor thesis (2017)

Authors

N.E.J. Bonenkamp Electrical Engineering, Mathematics and Computer Science

Contributors

T.M.L. Janssen (mentor)
Faculty
Electrical Engineering, Mathematics and Computer Science, Electrical Engineering, Mathematics and Computer Science
Copyright: © 2017 Noortje Bonenkamp
More Info
expand_more

Published Date

07-09-2017

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Abstract

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