Research On Dynamic Programming Algorithm To Solve Single-machine Scheduling Problem

As a kind of combinatorial optimization problem,production scheduling problemis usually NP-hard problem with the characteristics of nonlinearity,randomness and high complexity.Single-machine scheduling problem,as a kind of production scheduling problem,is ubiquitous in production and has important guiding significance to the research of complex multi-machine scheduling problem.It has become a research hotspoot in the field of production scheduling to design approximate algorithms for complex single-machine scheduling problems.Dynamic Programming is an accurate method which can theoretically botain the optimal solution of complex optimization problems.And Fully-Polynomial Time Algorithm is an approximate algorithm which can theoretically solve the approximate optimal solution of complex optimization problems.In this paper,DPA and FPTA are applied to complex single-machine scheduling problems.The main works are as follows:(1)For the Single-machine Batch Scheduling Problem with Maintenance Interval,the NP-hard attribute of this problem was firstly proved,and the Shortest Processing Time rule was shown to be the optimal scheduling rule of SMBSP.A DP based Pseudo-Polynomial Time Algorithm was proposed and the computational complexity of DPA was proved.Finally,State Cutting Technique was applied to DPA to design a Fully-Polynomial Time Algorithm,and the computational complexity of FPTA was proved.(2)For the Single-machine Green Scheduling Problem considering machine switching state,the NP-hard attribute of this problem was firstly proved,and then the SPT rule was proved to be the optimal scheduling rule of the problem.An accurate algorithm based on DP was designed to solve small-scale problems,and a Bird Swarm Algorithm was proposed to solve large-scale problems.At last,DPA and BSA were compared under 10 different problems scales.(3)Aiming at the Single-machine Green Scheduling Problem with dynamic energy threshold with the optimization index of Total Weighted Completion Time,the NP-hard property of this problem was firstly proved.And Maximum Processing Power-Weighted Shortest Processing Time with Energy Threshold Constraint(MPP-WSPT-ETC)rule was proposed and proved to be the optimal scheduling rule for the first time in academia.An accurate algorithm based on DP was designed and its computational complexity was proved.Then a FPTA based on DP was proposed and its computational complexity was proved.