Approximation Algorithm Of Scheduling Problem

Scheduling as an important branch of operational research, has a profound practical background and broad application field. It is extracted from some universal problems of operations research production, and then use mathematical methods to solve. It is widely used in production management, scientific management, computer science and engineering. Its essence is a combinatorial optimization problem, obtaining optimal solution in the feasible field. But during the actual production processing, due to some limitations, some sort of problem does not have optimal solution. Or it needs to run a very long time and large storage space to find the optimal solution. In order to meet the needs of practical problems, we can use approximation algorithm. The approximate solution is obtained to replace the optimal solutions of the problem in a short period of time. It can simplify the algorithm and reduce the time complexity. In order to meet practical application, the approximate solution and the optimal solution must satisfy the certain error precision. In this paper, we study some approximation algorithm for two machine models. The main content is as following:The first chapter mainly introduces the definition of scheduling problems and the three-field notation. In addition, we introduce the background of several scheduling problems and our innovation works in this paper.The second chapter mainly deals with parallel machine scheduling problem with a resumable availability constraint. One of the objectives is to minimize the makespan. The problem is NP-hard in the ordinary sense. Therefore, we need to find an approximate solution that fulfills the required error bound. To get a better approximation solution in a polynomial running time, we propose a fully polynomial-time approximation scheme(FPTAS) by trimming states space. This FPTAS is a better approximation algorithm and its running time is n O23)( e, where n is the number of jobs and e is the required error bound. The other objective is to minimize the sum of weighted completion times. The problem is NP-hard in the ordinary sense. We obtain a FPTAS by procedure partition. Its running time is Ln O455)( e, where n is the number of jobs, L is the input size and e is the required error bound.The third chapter mainly deals with uniform parallel-machine scheduling with deteriorating jobs and rejection. The processing time of a job is a linear increasing function of its starting time and jobs can be rejected by paying penalties. The objective is to minimize the scheduling cost of the accepted jobs plus the total penalty of the rejected jobs. We use rounding-the-input-data technique to get a FPTAS. Its running time is)(mmm---1112Ln O e, where n is the number of jobs, L is the input size and e is the required error bound.