Research On Scheduling With Processing Set Restrictions

Scheduling is the study on how to complete tasks within certain resources under constraints in an optimal way.In real life,scheduling problems are observed everywhere.Quite a lot of real-life problems are in fact scheduling problems.Because it helps the systems function more efficiently,the study on scheduling is of great significance.The main topic of thesis is the scheduling problems with two or three parallel machines where the jobs have processing set restrictions and can be rejected.In these problems,every job has its processing time and rejection penalty,and can be either processed on particular machines or rejected with the rejection penalty paid.The collection of machines that can process a certain job is called the processing set of that job.In Chapter 2,the scheduling of jobs on two machines with nested processing sets and rejection is studied.Two approximation algorithms are presented to minimize the sum of the makespan and the total rejection penalty.In the first algorithm,a job is processed or rejected according to its processing time,rejection penalty and the number of the machines.In the second algorithm,a job is process or rejected according to its processing time,rejection penalty and the number of the machines in its processing set.Both algorithms are proven and illustrated with examples.The worst-case ratio 2 of both algorithms are shown.In Chapter 3,the scheduling of jobs on three parallel machines with processing set restrictions are studied,and the processing set restrictions include three types: inclusive processing sets,tree-hierarchical processing sets,and nested processing sets.In every case,the objective function is to minimize the sum of the makespan and the total rejection penalty.Approximation algorithms with worst-case ratio 3 are provided for the three types,and all of them are proven and illustrated with examples.