Scheduling With Rejection And Arrive Time

In classical scheduling problems,it is assumed that all jobs must be accepted and processed on some machines.However,in many actual production situation,mostly in highly loaded make-to-order production systems,accepting all jobs may cause a delay in the completion of orders which in turn may lead to high inventory and tardiness costs.Thus,the manufacturer may wish to reject the processing of some jobs by either outsourcing them or rejecting them together.Since scheduling problems with rejection are very interesting both from a practical and a theoretical point of view,they have received a great deal of attention from researcher over last decade.In this paper,we consider a single machine scheduling with rejection.There are n jobs which need to be processed on a single machine.Before the scheduling decision,we need to decide which jobs are accepted.The objective is to minimize the sum of makespan of the accepted and the total rejection penalty of the rejected jobs.Then,we provide a 1.618-approximation algorithm.We use numerical experiments check the efficiency of the B&B algorithm and the approximate algorithm.Also,we studied the case of parallel machines,and provide a 2-approximation algorithm.The numerical experiments explains the algorithm is efficient.