Resource-constrained Machine Scheduling

Background Scheduling is a form of decision-making that plays a very importantrole in manufacturing industries. It is the method by which workgets assigned to resources that compute it. In this thesis we want to assignjobs (cycles of a lithography process) to different machines in such a waythat the machines are running for as little time as possible. The difficultylies in the fact that some jobs require the same resource, and thus cannotbe 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 CjWe try to approximate an optimal solution for the scheduling problemRm|res · 11|P Cj by calculating a ratio with a lower bound, where we ignoreresource constraints, and an upper bound, that is found by a Greedyalgorithm (w.r.t. resource constraints).Conclusions It appears that Greedy is not a very good approximationalgorithm for this problem, since the ratio in which the optimal TotalCompletion Time should lie is about 8,33% of the average calculated TotalCompletion Tim