Scheduling Problems With Deterioration And Rejection

Scheduling is an important branch of combinatorial optimization. The schedulingtheory extensively has been applied in many areas, such as production of industry and a-griculture, transportation, management science and computer science, etc. Batch schedul-ing, scheduling with deterioration, rejection and outsourcing are relatively new schedulingmodels, which have attracted great attention of scholars both at home and abroad. Inthis dissertation, many new results of the above models on complexities and algorithmsare presented.In Chapter I, we introduce some basic fundamental knowledge of scheduling problem,and briefy summarize the research results.In Chapter II, we consider several uniform parallel-machine scheduling problems inwhich the processing time of a job is a linear increasing function of its starting time. Theobjectives are to minimize the total completion time of all jobs and the total load on allmachines, respectively. We show that the problems are polynomially solvable when theincreasing rates are identical for all jobs; we propose a fully polynomial-time approximationscheme for the standard linear deteriorating function, where the objective function is tominimize the total load on all machines. We also consider the problem in which theprocessing time of a job is a simple linear increasing function of its starting time and eachjob has a delivery time. The objective is to fnd a schedule which minimizes the time bywhich all jobs are delivered, we propose a fully polynomial-time approximation scheme tosolve this problem.In Chapter III, we consider several serial batch scheduling problems with rejection.Each job is either processed on a single serial batching machine or rejected by payingpenalty. We consider two models with rejection. The frst is to minimize the sum of thescheduling cost of the accepted jobs and the total penalty of the rejected jobs, where thescheduling costs are the total completion time, the makespan, the maximum lateness andthe weighted number of tardy jobs, respectively. For the former two problems, we proposetwo polynomial time algorithms to solve them. For the last two problems, we deriveefcient dynamic programming algorithms. The second is to minimize the makespan,given an upper bound on the total rejection cost, we present a fully polynomial timeapproximation scheme. In Chapter IV, we consider the problems of scheduling deteriorating jobs with releasedates on a single machine (parallel machines) and jobs can be rejected by paying penalties.The processing time of a job is a simple linear increasing function of its starting time. Fora single machine model, the objective is to minimize the maximum lateness of the acceptedjobs plus the total penalty of the rejected jobs. We show that the problem is NP-hardin the strong sense and present a fully polynomial time approximation scheme to solveit when all jobs have agreeable release dates and due dates. For parallel-machine model,the objective is to minimize the maximum delivery completion time of the accepted jobsplus the total penalty of the rejected jobs. When the jobs have identical release dates, wefrst propose a fully polynomial time approximation scheme to solve it. Then, we presenta heuristic algorithm for the case where all jobs have to be accepted.In Chapter V, we consider the unbounded parallel batch machine scheduling deteri-orating jobs with release dates and rejection. Each job is either accepted and processedin batches on a single batching machine, or rejected by paying penalty. The processingtime of a job is a simple linear increasing function of its starting time. The objective isto minimize the sum of the makespan of the accepted jobs and the total penalty of therejected jobs. First, we show that the problem is NP-hard in the ordinary sense. Then,we present two pseudo-polynomial time algorithms and a fully polynomial-time approxi-mation scheme to solve this problem. Furthermore, we provide an optimal O(n log n) timealgorithm for the case where jobs have identical release dates.In Chapter VI, we consider several serial batch scheduling problems with outsourcingallowed. Each job can be either processed on the in-house machine or outsourced. Theobjective is to minimize the weighted sum of the scheduling cost and the total outsourcingcost. We discuss three classical scheduling objective functions. The frst is the totalcompletion time, the second is the maximum lateness, and the third is the weightednumber of late jobs. For each problem, we derive an efcient dynamic programmingalgorithm that minimizes the total cost.