Parallel Machine Scheduleing With Common Due Date To Maximize Early Work

Production scheduling is an important part of supply chain.With the development of economy and information technology,the innovation of production scheduling model must also be considered.Advanced modeling and optimization algorithms are important in enhancing the competitiveness in the manufacturing part of the supply chain.Therefore,this thesis mainly considers the problem of scheduling on the identical machines to maximize the total early work with a common due date of all the jobs.In the production enterprises of supply chain,the use of conveyor belt,conveyor,packaging machine and other logistics machines can be regarded as parallel machine production scheduling problems.By studying the reasonable matching of jobs and machines,we can improve the production efficiency and resource utilization in the supply chain.In order to maximize the total early work,the thesis uses the corresponding approximate algorithm.First of all,the thesis introduces the background,practical significance,theoretical significance and related research status in the current manufacturing environment.Secondly,in the production link of the supply chain,there may be situations where the jobs cannot be completed on time,which further causes delays in delivery and low customer service satisfaction.Therefore,considering due date and jobs sorting is very important in the manufacturing part of the supply chain,The thesis considers the problem of scheduling on the identical machines with a common due date of all the jobs,whose target is to maximize the total early work and complete jobs as many as possible under the use of approximate algorithms.In order to improve the production efficiency and resource utilization in the production enterprises,the classical LPT approximate algorithm is adopted as the problem is NP-hard and analyze the worst-case ratio of the classical LPT algorithm for the problem.In the process of studying the problem,the thesis studies the worst-case ratio of the general scheduling model for the algorithm is2m/(m+1)On this basis,the thesis further analysis a few machine scheduling models and obtain better worst-case ratio for the LPT algorithm.The worst-case ratio for the algorithm is12/11in two-machine scheduling model,which is tight,and the worst-case ratio for the algorithm is6/5in three-machine scheduling model.Finally,the thesis uses Java and LINGO tools to do example analysis of the algorithm.GAP value is used to obtain the relative error bound between the algorithm solution and the optimal solution in each specific example.In a word,we verify the effectiveness of the algorithm from practice and draw some relevant conclusions.