The New Model And Optimization Algorithm Of Parallel Machine Scheduling With Machine Resource Limitation

As the cornerstone of China's national economic development,industrialization development and steady improvement of international competitiveness,the manufacturing industry has always maintained a benign development trend since the reform and opening up.However,with the rapid development of China's national economy,people's demand are becoming more widespread and rapidly increasing,and various resources are being consumed more quickly.Moreover,the extensive growth of China's economy has led to such serious problems in China's manufacturing industry as resources waste caused by high input,high pollution,high consumption and low efficiency,unbalanced supply and demand caused by resources dispersion and resources shortage,which has hindered the development of traditional manufacturing industry.Reform and innovation are urgently needed.It is necessary to carry out theoretical innovation on actual resources waste,resources dispersion and resources shortage in order to coordinate production resources,production time,production costs,production environment and human resources.At the same time,with the development of the economy and improvement of information technology,the innovation of the manufacturing model must also keep pace.The new manufacturing model should be adopted to study the production scheduling problem in order to propose the optimization algorithm and reasonable production scheduling strategy,which plays an important role in improving the competitiveness of enterprises.This paper first introduces the background,practical significance,theoretical significance of the scheduling problem as well as the hot issues and results of studies that scholars both from home and abroad have conducted.Secondly,focusing on the problem of resources shortage in the actual operation process of the enterprise,this paper innovatively proposes a resource limitation scheduling model with new resource-time function which includes linear function relationship,concave function relationship and convex function relationship.During the production process of the enterprise,the speed of processing will gradually increase with the accumulation of workers' experience,which shortens the processing time of the job.This kind of phenomenon is known as the learning effect.As the processing time of the job becomes shorter,the human resources spent on the job are correspondingly reduced.To this end,a learning function,the DeJong learning function,is proposed based on the job itself and the actual processing position.Therefore,this paper targets at the resource limitation scheduling problem by combining DeJong learning effect and new resource-time function in order to maximize the minimum machine load and use limited resources to process more jobs.After verifying the NP-hardness of the problem,two approximation algorithms are proposed to analyze the worst-case ratio and some examples.In addition,considering the strategic cooperation between the company and the customer,the company will produce all orders for this customer,but the production of all orders will exceed its own production capacity.At the same time the enterprise will use funds to add the production lines,it will produce the corresponding purchase cost of production lines(machines),that is the problem of machine cost.Machine cost is one of the hot issues in the field of scheduling.The corresponding machine cost will rise when the number of machines increases,but meanwhile the production time decreases.How to balance the time cost and machine cost is a major difficulty in the field of scheduling.Therefore,this paper considers the resource limitation scheduling problem combined with machine cost and new resource-time function to study the preemptive and non-preemptive models.The goal is to minimize the sum of machine cost and makespan and balance the time cost and machine cost.A polynomial time algorithm is proposed for the preemptive problem.For the non-preemptive problem,an approximation algorithm is proposed to analyze the worst-case ratio after verifying the NP-hardness of the problem.