Complexity And Algorithms Of Some New Scheduling Problems

In this thesis,we investigate some new scheduling problems,including multi-agent parallel machine scheduling with rejection,parallel machine scheduling with deteriorating jobs and rejection,multi-agent scheduling with deteriorating jobs and rejection,two-machine flow shop scheduling with an operator non-availability period and the supply chain scheduling with rejection.We design algorithms for these problems and analyze the computational complexity of some problems.In Chapter 1,we first give some basic concepts and definitions of combinatorial optimization problems and scheduling problems.Then we introduce the reviews of the fields related to the content of this thesis.Finally,the main results in this thesis are presented.In Chapter 2,we consider the multi-agent parallel machine scheduling with rejection We are given two agents A,B and two parallel machines,each agent has a set of non-preemptive jobs to be processed on the machine,and the agents has no job in common.Each job is either rejected with a certain penalty has to be paid,or accepted and processed on the machine.The objective is to minimize the sum of the given objective function fA of the the accepted A-jobs and the total rejection penalty of the rejected A-jobs subject to an upper bound on the sum of the given objective function fB of the accepted B-jobs and the total rejection penalty of the rejected B-jobs,where fA and f B are regular func-tions of the completion time of the accepted A-jobs and accepted B-jobs,respectively.Four scheduling problems associated with different combinations of the two agents' objective functions are considered,fA=?CjA and fB?(?)When(fA,fB)=((?)),we provide two pseudo-polynomial time algorithms and a(1+?)-approximation algorithm.For the other cases,we give a pseudo-polynomial time algorithm,respectively.In Chapter 3,the two-agent single machine scheduling problems with deteriorating jobs and rejection are studied.There are two competing agents A and B.Each has a set of jobs to be processed on a single machine.The actual processing time of any jobs JjX is an increasing simple linear function of its starting time,i.e.,pjX=bjX(a+bt),X ? {A,B}and the job can be rejected.The objective is to minimize the sum of the total completion time of the accepted A-jobs and the total rejection penalty of the rejected A-jobs subject to an upper bound on the sum of the given objective function fB of the accepted B-jobs and the total rejection penalty of the rejected B-jobs,where fB?{CmaxB,?CjB}.We design algorithms and(1+?)-approximation algorithms based on dynamic programming for these problems,respectively.In Chapter 4,we study the batch scheduling with deteriorating jobs and rejection.There are n jobs to be processed in batches by an unbounded parallel-batch machine,each job's processing time is an increasing simple linear function of its starting time,i.e.,pj=bjt,and the job can be rejected.We study the following five cases:(1)minimize the makespan of the accepted jobs subject to an upper bound on the total rejection penalty of the rejected jobs;(2)minimize the total rejection penalty of the rejected jobs subject to an upper bound on the makespan of the accepted jobs;(3)minimize the total weighted completion time of the accepted jobs subject to an upper bound on the total rejection penalty of the rejected jobs;(4)minimize the total rejection penalty of the rejected jobs subject to an upper bound on the total weighted completion time of the accepted jobs;(5)minimize the maximum tardiness of the accepted jobs subject to an upper bound on the total rejection penalty of the rejected jobs.For the first two cases,we assume that the jobs have release dates,while for the last three cases,all jobs are available at time t0,where t0>0.We show that all these cases are NP-hard and present a dynamic programming algorithm and a fully polynomial time approximation scheme(FPTAS)for the top four cases,respectively.In Chapter 5,we mainly research the two-machine flow shop scheduling with an operator non-availability period.We are given n jobs to be processed on two machines.Each job Jj consists of two operations O1j and O2j with non-negative processing time aj and bj,j=1,2,…,n.Each job is first processed on machine 1,then on machine 2,and operation O2j cannot be processed on machine 2 before the completion time of O1j.The objective is to minimize makespan,where there exists an operator non-availability period(s,s+L)in the first stage.We first show that the problem is NP-hard,even if the length of the operator non-availability period is no more than the processing time of any job on the first machine.i.e.,aj>L,j=1,2,…,n.Then we show that the worst case error bound of Johnson's algorithm is 2 and the bound is tight.Finally,an approximation algorithm with a worst case error bound of 3/2 is provided.In Chapter 6,we focus on the supply chain scheduling with rejection.There are n jobs and m parallel machines,a job is either rejected with a rejection penalty has to paid,or accepted and processed on one of the m parallel machines.The jobs finished on the machine should be delivered to the customer in batches.We assume that the delivery time is 0 and the delivery cost of a batch from the processing facility to the customer is f,the objective is to minimize the weighted sum of the time when the last accepted job is delivered to the customer and the total cost of rejecting and delivering jobs.We first point out the error in the literature.Then a 2-approximation algorithm is given.