Single Machine Scheduling With Rejection And Generalized Parameters

This kind of problem that allows jobs to be rejected is called scheduling with rejection.The generalized due date refers to that the due date of the job is determined according to the sequential processing position of the jobs,which is independent of the job.Inspired by the generalized due date,in this paper,We consider the following three scheduling problems with rejection and generalized parameters.(1)Single machine scheduling with rejection to minimize the makespan.When the release time of jobs are generalized,we call it GRD.When the processing time of jobs are generalized,we call it GPT.When the rejection cost of jobs are generalized,we call it GRC.Let A and R represent the set of received jobs and rejected jobs,respectively.According to the three-parameter representation notation for scheduling problem,we write the three problems as 1|GRD,reject |Cmax+∑Jj∈Rej and 1|rj,GPT,reject| Cmax+∑Jj∈Rej and 1|rj,GRC,reject| Cmax+∑Jj∈Rej,respectively.We show that the first scheduling problem is binary NP-hard,and then,we provide a pseudo-polynomial time algorithm and a full polynomial-time approximation scheme(FPTAS)for this problem.For the latter two problems,we provide polynomial-time optimal algorithms,respectively.(2)Single machine scheduling with rejection to minimize the maximum delivery completion time.When the delivery time of jobs are generalized,we call it GDT.When the processing time of jobs are generalized,we call it GPT.When the rejection cost of jobs are generalized,we call it GRC.Let A and R represent the set of received jobs and rejected jobs,respectively.According to the threeparameter representation notation for scheduling problem,we write the three problems as 1|GDT,reject| Dmax+∑Jj∈R ej and 1|GPT,reject |Dmax+∑Jj∈Rej and 1|GRC,reject|Dmax+∑Jj∈R ej,respectively.We show that the first scheduling problem is binary NP-hard,and then,we provide a pseudo-polynomial time algorithm and a full polynomial-time approximation scheme(FPTAS)for this problem.For the latter two problems,we provide polynomial-time optimal algorithms,respectively.(3)Single machine scheduling with rejection to minimize the total weighted completion time.When the processing time of jobs are generalized,we call it GPT;when the weight of jobs are generalized,we call it GW;when the refuse cost of jobs are generalized,we call it GRC.Let A and R represent the set of received jobs and rejected jobs,respectively.According to the three-parameter representation notation for scheduling problem,we write the three problems as 1|GPT,reject|∑Jj ∈A wjCj+∑Jj∈R ej and 1|GW,reject|∑Jj∈A,wjCj+∑Jj∈Rei and 1|GRC,reject|∑Jj∈A wjCj+∑Jj∈Rej,respectively.We prove that the first two problems are polynomial time solvable;for the third problem,we give a pseudo-polynomial time algorithm.