Model And Optimization Algorithm For Rejectable Scheduling Problem With Machine Availability Constraints

In recent years,the manufacturing industry,as an important basis for China's economic development,industrialization development and even the enhancement of international competitiveness,has been developing rapidly.In 2018,the manufacturing industry alone brought up to 2.648 billion of output value to China,accounting for29.42% of China's GDP,making it the industry with the highest proportion among all industries in China.However,with the rapid development of the manufacturing industry as a whole,it is accompanied by difficulties and challenges that need to be solved urgently.On the one hand,the improvement of the overall pace of life of the people also puts forward high requirements on the working efficiency of the manufacturing industry.Therefore,it has become an indispensable link for enterprises to improve production efficiency by designing reasonable scheduling strategies,optimizing production procedures and improving production efficiency.On the other hand,with the continuous improvement of national living standards,users are increasingly pursuing personalized and diversified production,which makes the production mode of enterprises have to incline from mass production to personalized and flexible production mode.Therefore,in order to shorten the working cycle and improve the production efficiency of the enterprise,the enterprise will consider to reject some jobs with heavy workload but low profit so as to put the productivity into the work with higher efficiency.This paper starts with the internal optimization and external environment of the enterprise,proposes innovative scheduling problem,establishes a new model for the innovative problem,and proposes reasonable optimization algorithm and production scheduling strategy,which plays a very important role in improving the competitiveness of the enterprise.Firstly,starting from the introduction of the practical and theoretical significance of production scheduling problem,this paper introduces the research status,hot issues and existing achievements of domestic and foreign scholars successively,and also expounds the concept of scheduling theory related to this paper.Secondly,from the internal perspective of the enterprise,we find that in the production process of the enterprise,many workers will gradually improve their working speed and efficiency with the accumulation of experience,which will gradually shorten the working hours of the workers,namely the learning effect.In the process of processing,with the loss of the machine,the processing time will slowly increase,making the processing time of the work longer and longer,which is,aging effect.At the same time,we take into account that in the production process of the enterprise,the machine cannot be kept running all the time,there will be unusable period.But based on the outside of the enterprise,in order to improve the efficiency of the enterprise,the enterprise has to refuse to produce complex but low profit work.Therefore,we propose a production scheduling problem with variable processing time and machine unavailability constraints and rejections.Then,according to the variable nature and function of working time,the problem is divided into two models: working time based on position change and working time based on variable start time,and the constraint of work arrival time is added to the model of working time based on start time to expand.We first proved that all the problems studied in this paper were NP-hard problems,then designed complete polynomial time approximation scheme(FPTAS)and dynamic programming for these models respectively,and finally carried out example design and data test for FPTAS algorithm with MATLAB,and also carried out example design and data test for dynamic programming algorithm with Python,to verify the rationality and effectiveness of the algorithm.