Scheduling Problems With Rejection To Minimize Two New-type Objective Functions

Machine scheduling has been one of the most important problems in combinatorial optimization. It is widely applied in management science, computer science and engineering and technology areas. It is also a very active branch of operations research. There is a lot of literature that studied kinds of scheduling problems. In the classical scheduling problems,all jobs must be processed on the machines. However, in order to obtain greater profit,sometimes we have to reject some jobs. In 2000, Bartal et al. [2] first studied scheduling problems with rejection. After that, people began to pay more and more attention and research on the scheduling with rejection. In this paper, we mainly consider the following two scheduling problems with rejection.(1) Parallel machines scheduling problem with rejection to minimize the sum of the square of the loads.This scheduling problem can be described as follows: There are m machines M1,…,Mm and n jobs J1,J2,…,Jn.Each job Jj has a processing time pj and a rejection cost ej. Job Jj is either accepted and processed on some machine, or rejected in which case the rejection cost ej has to be paid. Our objective is to minimize the sum of the square of loads and the rejection costs of rejected jobs. By using the general notation for scheduling problem introduced by Graham et al. [9], this problem can be denoted by Pm | reject |(?).Firstly, we show that this problem scheduling is binary NP-hard when m > 1 is a fixed constant and is strongly NP-hard when m is an arbitrary parameter. Secondly, we give a pseudo-polynomial-time dynamic programming algorithm when m is a fixed constant.Especially, when all jobs have the same processing time, it can be solved in polynomial time by the above dynamic programming algorithm. Finally, we give an effective approximation algorithm when m is arbitrary and a fully polynomial-time approximation scheme when m is a fixed constant.(2) Single machine scheduling problem with rejection to minimum the maximum weighted completion time.This scheduling problem can be described as follows: there are a single machine and n jobs J1, J2,…?Jn. Each job Jj has a processing time pj a rejection penalty ej and a weight wj Job Jj is either accepted and processed on the machine, or rejected in which case the rejection penalty ej has to be paid. Our objective is minimize the sum of the maximum weighted completion time and the total rejection penalty. By using the general notation for scheduling problem introduced by Graham et al.[9], this problem can be denoted by 1 | reject |(?).Firstly, we show that this scheduling problem is binary NP-haxd. Secondly, we present a pseudo-polynomial-time dynamic programming algorithm. Specially, when all jobs have the same processing time, this problem can be solved in polynomial time by the above dynamic programming algorithm. Finally, an approximation algorithm is given for this problem.