Machine Scheduling Problem With The Denial Of Costs

Machine scheduling has been one of the most important and active research topics in combinatorial optimization over the last half century.In the classical scheduling literatures, all jobs must be processed and no rejection is allowed.However,in real applications,this may not be true.Due to the limited resources,the scheduler have the option to reject some jobs.In this paper,we consider the following two scheduling problems with release dates and rejection penality.(1) The single machine scheduling problem with release dates and rejection penaltyThe single machine scheduling problem with release dates and rejection penalty can be described as follows.There are a single machine and n jobs J₁,...,J_n.Each job J_j has a processing time,p_j,a release date r_j,and a rejection penalty w_j.J_j is either rejected, in which case the rejection penalty w_j has to be paid,or accepted and processed on the machine.The objective is to minimize the sum of the makespan of the accepted jobs and the total penalty of the rejected jobs.We denote the set of rejected jobs by R.By using the general notation for scheduling problem introduced by Graham et al.[12],this problem is denoted by 1|r_j,reject|C_max+∑_Jj∈Rw_j.First,we show that this problem is binary NP-hard.Then,we provide two pseudo-polynomial-time algorithms.Consequently,two special cases can be solved in polynomial time.Finally,a 2-approximation algorithm and a fully polynomial-time approximation scheme are given for this problem.(2) The unbounded parallel batch machine scheduling problem with release dates and rejection penaltyThe unbounded parallel batch machine scheduling problem with release dates and rejection penalty can be described as follows.There are an unbounded parallel batch machine and n jobs J₁,...,J_n.Each job J_j has a processing time p_j,a release date r_j, and a rejection penalty w_j.Each job J_j is either rejected with a rejection penalty w_j having to be paid,or accepted and processed on the parallel batch machine.The parallel batch machine can process a number of jobs simultaneously as a batch.The jobs in the same batch have the same starting time and completion time.The processing time of a batch is defined as the longest processing time of the jobs contained in it.Let R be the set of the rejected jobs.The objective is to minimize the sum of the makespan of the accepted jobs and the total rejection penalty of the rejected jobs.Using the general notation for scheduling problem introduced by Graham et al.[12],the problem is denoted by 1|p-batch,r_j,reject|C_max+∑_Jj∈Rw_j.First,we show that this problem is binary NP-hard.Then,we provide a pseudo-polynomial-time algorithm for the problem.Consequently,this problem is solved in polynomial time when all jobs have the same rejection penalty.Finally,a 2-approximation algorithm and a fully polynomial-time approximation scheme are given for this problem.