Single Machine Scheduling Problems Under Distinct Discount Ratios On The Number Of Outsourced Jobs

Scheduling is a very important branch of Operations Research and Management,Science.In the classical scheduling problems,the manufacture must process all jobs in-house on the machines.That is.it is not allowed to reject or outsource any jobs.However,with the increase in the number of jobs,processing all jobs may cause the delays of some jobs,and then reduce the satisfaction degree of some customers.Thus,in the recent 10 years,many scholars have studied some scheduling problems with rejection or ousourcing.In the scheduling problems with rejection or ousourcing.if a job is rejected or outsourced,then,it,need to pay a corresponding rejection cost or outsourcing cost.Clearly,by rejecting or outsourcing some jobs,the manufacture can use production capacity more efficiently and preserve high quality of service(QOS)to the VIP customers.In fact,if we treat the rejection cost as its oursourcing cost,then scheduling with rejection is equivalent to scheduling wit.h outsourcing.In most scheduling problems with rejection or outsourcing,the rejection or outsourc-ing cost of a.job is always fixed.The objective is to make a balance between a objective function corresponding to the processed jobs and the total cost corresponding to the re-jected or outsourced jobs.However,in scheduling with outsourcing,in the subcontractor's point of view,the outsourcer may provide an attractive discount scheme in order to encour-age the manufacturer to outsource more jobs.This discount scheme might be dependent on the number of the outsourced jobs,the original total outsourcing cost and the time slots in which the outsourced jobs are processed by the outsourcer.Nowadays,quantity discount is the commonest,discount scheme and the widely-used promotion method in the market.In this thesis,we consider some single-machine scheduling problems with the distinct discount ratios on the number of the outsourced jobs.In these scheduling problems,each job Jj has an original outsourcing cost et.Each Jj is either processed by the manufacturer's in-house machine,or outsourced and then pays an outsourcing cost of ej.Let O and O be the sets of the outsourced jobs and the in-house processed job,respectively.Let m = |O| be the number of the jobs in O.It is also assumed that there are k disjoint intervals[0,[N1,N2),…[Nk-1,Nk).A certain discount rate DRi is associated to each[Ni-1,Ni)(1? i ? k,where we have 1 = DR1>DR2>…>DRk>0.If m?[Ni-1,Ni),the actual outsoucing cost of each job Jj is exactly ej1= DRi·ej.Clearly,to obtain a smaller discount ratio,the manufacture has to outsource more jobs.Thus,the manufacture needs to determine which jobs should be outsourced,and then determine a schedule for the in-house processed jobs,so as to minimize a given objective function.In Chapter 2.we consider four scheduling problems with the identical release dates.We studied four distinct objective functions:the makespan Cmax;the maximum lateness Lmax,the total completion time ?Cj and the total weighted completion time?wjCj.For the problems to minimize the makespan Cmax or the total completion time?Cj,we propose a polynomial-time optimal algorithm,respectively;For the problems to minimize the maximum lateness Lmax or the total weighted completion time ?wjCj,we show that both of two problems are NP-hard and then propose a dynamic programming algorithm to obtain an optimal schedule in pseudo-polynomial time,respectively.In Chapter 3,we consider a scheduling problem with the non-identical release dates.The objective is to minimize the makespan Cmax.we show that this problem is NP-hard and then propose two dynamic programming algorithm to obtain an optimal schedule in pseudo-polynomial time.Finally,we also present a 2-approximation algorithm and a fully polynomial time approximation scheme(FPTAS)for this problem.