Research On Exact And Approximation Algorithms For Two-machine Flow-shop Scheduling Problem

This paper studies the scheduling problem of maximizing the?weighted?early work with a common due date in two flow-shop machines,that is,arranging the jobs to be processed on the two flow-shop machines under the constraint of a common due date,and obtaining the maximum?weighted?early work by arranging the processing sequence of jobs reasonably,this problem is NP-hard.This article first studies the exact algorithms for this problem:For the weighted model,This paper optimizes the dynamic programming method DP1?The time complexity of DP1 is O?n²d⁴??published in 2005 EJOR to solve this problem,by adding some judging conditions,appropriately reducing the calculation step size of DP1,the optimization method DP2 is obtained;For the unweighted model,its early work on M₁ is fixed,based on this property and combined with the idea of DP1 division,this paper proposes a new dynamic programming DP3with time complexity of O?n²d²?.Furthermore,this paper analyzes the approximation algorithms of the problem.First of all,this paper proves that the most important algorithm——Johnson's algorithm in the field of two-machine flow-shop problem has an approximation ratio lower bound ?2wmax?/?wmin?.From the perspective of approximation ratio analysis,it can be considered as one of the worst algorithms.Therefore,this paper designs a fully polynomial time approximation scheme?FPTAS?A_?for this problem.In the end,numerical experiments are performed on the exact and approximation algorithms respectively.The experiment of exact algorithm shows that DP2 can shorten the time of solving the exact solution to a certain extent,while DP3 can solve a larger scale problem in the effective time.For the approximation algorithm,this paper puts Johnson's algorithm and A_?algorithm together for numerical experiment comparison,the results show that:Johnson's algorithm is much better than A_?algorithm in running time,and for the weighted model,A_?algorithm is better than Johnson's algorithm in solution accuracy.