A Study On Two Scheduling Problems With Restricted Resourses

Scheduling models and algorithms are widely used in manufacturing system for efficient production.However,the shortage of resource is bringing more and more ineffectiveness or inefficiency that a manufacturer can afford.This paper studies two problems respect to resource constrained production scheduling.In the first problem,we incorporate additional resources into classical parallel machine scheduling.It is assumed that the processing of each job requires not only a machine but also some additional resource.And two jobs requiring the same resource cannot be scheduled in parallel.The objective is to minimize the overall makespan of the schedule.In the second problem,we consider the scenario where flexible periodic maintenance occurs in a single machine so that all jobs have to be processed in periodic time windows.The objective is to minimize the number of tardy jobs.We distinguish four chapters among the thesis.In Chapter 1,we mainly introduce some fundamental knowledge on scheduling problem and the theory of computational complexity.Particularly,we give a short review on the resource-constrained scheduling problem.Chapter 2 discusses the first problem.According to the different choice of decision variables,we provide four different mathematical programming models for the considered problem.Then,a LPT-based approximation algorithm,namely ILPT,is designed to solve the problem.The worst case ratio of ILPT is shown to be 2-2m+1.Finally,we note LLPT is another LPT-based algorithm and is shown to have the same theoretical bound as ILPT in the literature.The performance of the existing algorithms is evaluated by numerical experiments.In Chapter 3,we study single machine scheduling with flexible periodic maintenance.We prove that the problem cannot be approximated within a constant worst case ratio and give a pseudo-polynomial time dynamic programming algorithm to solve the general problem.Solvable cases are also discussed.Chapter 4 makes a summary of the whole paper and put forward some problems for further study.