On Some Special Cases Of Parallel Machine Scheduling With Rejection

Scheduling occupies a very important position in both operations research and combinatorial optimization.The classical scheduling problem is a famous NP-hard problem.An instance of it consists of m parallel machines and n jobs.Each job is associated with a processing time.A schedule or an assignment of the problem is a partition of these n jobs into m subsets such that all jobs in a subset will be assigned to one of the m machines.The load of a machine is the completion time that finishes all jobs assigned to it.The maximum load over all machines is called the makespan of such an assignment.The objective of the classical scheduling problem is to find an assignment such that the makespan is minimized.A generalized form of the classical scheduling problem is allowed to reject some of the jobs,only with the condition that rejection of any job brings its penalty.An instance of such a problem consists of m parallel machines,n jobs with each job is associated with its processing time if it is assigned to one of the machines and its penalty if it is rejected.The objective of the problem is actually two phases.The first phase is to partition these n jobs into two subsets: the accepted subset and the rejected subset.The second phase is to assign all jobs in accepted subset to m machines such that the makespan of the assignment plus the total penalties in the rejected subset is minimized.In this dissertation,we are focusing on algorithmic and complexity aspects of some special cases of this NP-hard problem.We discuss the special case in which the processing time of each job is a power of 2 and the ratio of processing time to the penalty of each job satisfies a certain relation;we show that the problem under such condition is polynomial time solvable and hence design a polynomial time algorithm for solving it.Our result is also natural to extend to the case in which the processing times of any two jobs are divisible in one way or in the opposite way.We also discuss a restricted case in which the cardinality of the accepted subset is required to be bounded by a constant.In this case,we design an approximation algorithm for the problem.