The Dynamic Programming Algorithm Solves The Green Single-machine Scheduling Problem

Green manufacturing is one of the strategic tasks of"Made in China 2025",and Green shop scheduling problem(GSSP)is an important measure to achieve green manufacturing.Conventional workshop scheduling considers the economic indicators of controlling costs,shortening the construction period,and reducing the delay of the workpiece.On this basis,GSSP also considers green indicators of energy saving and consumption reduction.Obviously,GSSP is more complex and has more theoretical and engineering value.In recent years,GSSP has attracted the attention of academia and become a current research hotspot,but related research is still relatively limited.Therefore,research on such issues is of great significance.Single machine scheduling problem(Single machine scheduling problem,SMSP)is the prototype and foundation of various multi-machine scheduling problems.It not only widely exists in manufacturing and process industries,but also is a sub-problem that often needs to be solved in the decomposition and optimization of complex production scheduling problems.Studying the problem of green single-machine scheduling is not only of great academic significance but also of certain application value,which has attracted the attention of scholars in the field of production scheduling.Dynamic programming algorithm(DPA)is an accurate algorithm,which can theoretically obtain the optimal solution of complex optimization problems.In the past fifty years,dynamic programming has been widely used in various fields:Aiming at a type of green single-machine scheduling problem that exists widely in production,that is,a single-machine green scheduling problem with release time and machine speed,with total energy cost(TEC)as the optimization goal,a An accurate dynamic programming algorithm to solve.First of all,considering the constraints of different release time and expected completion time of each workpiece,taking into account the different energy consumption of different speeds of the machine,and the different processing time of the workpiece at different speeds,the problem sequencing model was established;An exact dynamic programming algorithm(EDPA)is used to solve the problem;finally,the effectiveness of the proposed algorithm is demonstrated through simulation calculations.An exact dynamic programming algorithm(EDPA)is proposed for a kind of green single-machine scheduling problem,i.e.,the low-carbon single-machine scheduling problem with release times and due dates.The first and second optimization objectives are the maximum tardiness and the total carbon emissions,respectively.Firstly,the permutation-based model of the considered problem is built.This model can be described by triplet1|a gr(r _j,d _j)|TCE/T_{ma x},which is an NP-hard problem.Secondly,an earliest due date(EDD)rule based on both the job permutation and the selection of machine state is presented by analysing the properties of the permutation-based model.Thirdly,the state recurrence equation is constructed via the presented rule,and then an EDPA is designed by using the constructed equation to execute the state-tree search in solution space.This algorithm is an exact algorithm with pseudo-polynomial time,and it can obtain optimal solution of the considered problem.Finally,the simulation experiments on the testing and real-world instances manifest that the proposed algorithm can not only minimize the maximum tardiness,but also reduce the total carbon emissions effectively.Aiming at the problem of green single machine batch scheduling,a green single machine scheduling problem in batch mode is studied.The primary and secondary optimization goals are maximum completion time and total energy cost,respectively.First,establish a sorting model of the problem based on the constraints of the workpiece size,processing power,processing time,and machine capacity.The problem is expressed by the three-parameter method1|B|TEC/C_{ma x},and the NP-hard attribute of the problem is proved by combining the partitioning problems;The LPT rules for batching of workpieces were designed,and a pseudo-polynomial time algorithm based on dynamic programming was designed.Finally,the effectiveness of the proposed rules and algorithms was proved by simulation experiments.