Single-machine Scheduling With Rejection And An Operator Non-availability Interval

Scheduling theory has a deep practical background and a wide range of applications as a branch of operations research and an applied science.Scheduling is to allocate several tasks to the existing resources and process them according to time such that the required indicators are optimal.In optimization theory and applications,scheduling often refers to machine scheduling.At present,a large amount of literature has studied various types of machine scheduling problems.The scheduling problem is divided into classical scheduling problem and modern scheduling problem.In the classical scheduling problems,we often assume that all jobs must be processed on the machine.However,in actual processing and production,in order to allocate resources more efficiently,and also to maximize the benefits of the manufacturer,sometimes we often need to reject or outsource these jobs to the third-party manufacturers.At the same time,in the production process,the ma-chine often needs regular maintenance due to some practical problems,such as adding fuel,etc.,or the machine operator needs to take a break.This will result in machine non-availability intervals and operator non-availability intervals,that is,during the ma-chine non-availability interval,the machine cannot process the jobs;during the operator non-availability intervals,the machine cannot be started or completed.In this paper,we combined the above two factors to consider the following three single-machine scheduling problems with rejection and operator non-availability intervals.(1)The single machine scheduling problem with rejection and an operator non-availability interval to minimize the sum of the maximum completed and the total rejection cost.The single machine scheduling problem with rejection and an operator non-availability interval to minimize the sum of the maximum completed and the total rejection cost can be described as follows.There are a single machine and n jobs J1,J2,…,Jn.Each job Jj is available at time 0 and has a processing time pj,a rejection penalty ej.Each job Jj is either rejected and the rejection penalty ej has to be paid,or accepted and then processed non-preemptively on this machine.There is an operator non-availability interval(a,b)on this machine,where we assume that 0<a<b.Without loss of generality,we assume that all the parameters pj,ej,a,b are non-negative integers.Define R as the set of all rejected jobs.Our objective function is to minimize the sum of the maximum completion time of the received jobs and the total rejection cost of the rejected jobs.According to the three-parameter representation notation for scheduling problem proposed by Graham et al.[11],we write this problem as 1|ONA(a,b),rej|Cmax+e(R).First,we show that this problem is binary NP-hard.Then,we provide a pseudo-polynomial dynamic programming algorithm and a fully polynomial time approximation scheme.(2)The single machine scheduling problem with rejection and an operator non-availability interval to minimize the sum of the total weighted completion time and the total of the rejection cost.The single machine scheduling problem with rejection and an operator non-availability interval to minimize the sum of the total weighted completion time and the total of the rejection cost can be described as follows.There are a single machine and n jobs J1,J2,…,Jn.Each job Jj is available at time 0 and has a processing time pj,a weight-ed ?j and a rejection penalty ej.Each job Jj is either rejected and the rejection cost ej has to be paid,or accepted and then processed non-preemptively on the machine.There is an operator non-availability interval(a,b)on the machine,where we assume that 0<a<b.Without loss of generality,we assume that all the parameters pj,wi,ej,a,b are non-negative integers.Define R as the set of all rejected jobs.Our objective function is to minimize the sum of the total weighted completion time of the received jobs and the total rejection cost of the rejected jobs.According to the three-parameter representation notation for scheduling problem proposed by Graham et al.[11],we write this problem as 1|ONA(a,b),rej|(?)?jCj+e(R).First,we show that this problem is binary NP-hard.Then,we provide a pseudo-polynomial dynamic programming algorithm and a fully polynomial time approximation scheme.(3)The single machine scheduling problem with rejection and a non-availability inter-val to minimize the sum of the maximum lateness and the total of the rejection cost.The single machine scheduling problem with rejection and a non-availability interval to minimize the sum of the maximum lateness and the total of the rejection cost can be described as follows.There are a single machine and n jobs J1,J2,…,Jn.Each job Jj is available at time 0 and has a processing time pj,a delivery time qj and a rejection penalty ej.Each job Jj is either rejected and the rejection penalty ej has to be paid,or accepted and then processed non-preemptively on the machine.There is a machine non-availability interval or an operator non-availability interval(a,b)on the machine,where we assume that 0<a<b.Without loss of generality,we assume that all the parameters pj,qj,ej,a,b are non-negative integers.Define R as the set of all rejected jobs.Our objective function is to minimize the sum of the maximum transportation completion time of the received jobs and the total rejection cost of the rejected jobs.According to the three-parameter representation notation for scheduling problem proposed by Graham et al.[11],we write this problem as 1|MNA(a,b),rej|Lmax+e(R)and 1|ONA(a,b),rej|Lmax+e(R),where L max=max{Cj+qi}.First,we show that this two problems is binary NP-hard.Then,for these two prob-lems,we give a pseudo-polynomial time optimal algorithm.Furthermore,we also propose a fully polynomial time approximation scheme.