Research On Some Scheduling Problems With Job Rejection And Outsourcing Allowed

This paper mainly studies a type of scheduling problems with job rejection and outsourcing allowed,which has a broad application background in manufacturing systems.In the production and manufacturing process,if the order demand exceeds its production capacity or due to the order quota,the enterprise will refuse or outsource part of the order to relieve the production pressure.This paper studies two scheduling problem models with different machine environments and constraints.One is the single machine scheduling problem with the joint decision of job processing,outsourcing and transportation.The other is the problem of m unrelated parallel machine scheduling with job release dates and rejection.The research focuses on the design of an exact algorithm,approximation algorithm and the fully polynomial-time approximation scheme（FPTAS）,algorithm worst-case bound and problem complexity confirmation proof.At the same time,numerical experiments are designed to illustrate the feasibility and effectiveness of the algorithm.The full text is as follows.The first chapter mainly introduces some knowledge and concepts about scheduling theory,the significance and the research status of scheduling problems with rejection and outsourcing.It introduces the scheduling problem model to be studied in detail.The second chapter of the paper studies a single machine scheduling problem with the joint decision of job processing,outsourcing and transportation.In this problem,n jobs from m different customers can be processed on in-house machines either at the manufacturer’s or outsourced to a subcontractor.Each completed job should be transported to its customer immediately.The in-house machine environment is a single machine,while the outsourced production capacity is infinite by default.At the same time,there are different processing times,transportation times and production costs when the manufacturer and subcontractor process the job.The goal is to minimize the weighted sum of the makespan and the total cost,expressed as 1+∞‖λC_max+（1-λ）W.The predecessors proved that the problem is NP-hard even if the number of customers is m=1.The dynamic programming algorithm and 2-approximation algorithm are given for the special case where the number of customers is m=1.We make the model more general;for the m customers scheduling problem model,we design the dynamic programming algorithm,2-approximation algorithm and the fully polynomial-time approximation scheme（FPTAS）.Finally,an example illustrates that the proposed algorithm is feasible and effective in solving this scheduling problem.In the third chapter of the paper,we consider the job with release dates and rejection of the m unrelated parallel machine scheduling problem.In this problem,it is not to default that the job is available at zero time,each job has a different arrival time,and the job can only be processed after arrival.At the same time,it is not to default that all the jobs should be processed;you can choose to reject some jobs and pay a certain rejection cost.The goal is to minimize the sum of the makespan of accepted jobs and the total rejection cost of rejected jobs,expressed as R_m|r_j,rej|C_max（A）+（?）e_j.This problem has not been studied before;we give the complexity confirmation of this problem and prove that this problem is NP-hard.Then,we present the dynamic programming algorithm,m+1-approximation algorithm and fully polynomial-time approximation scheme（FPTAS）for this problem.Finally,the feasibility and effectiveness of the algorithm are illustrated by a concrete example.The fourth chapter of the paper summarizes the work of this paper,expounds the conclusion and analyzes the future research direction.