Risk Optimization For The Job Shop Scheduling With Random Machine Breakdowns

Production scheduling directly determines the optimal allocation and efficiency of all kinds of manufacturing resources in the workshop.However,many uncertain events will disturb the execution of a schedule,which leads to the risk of production system instability and performance deterioration.In order to adapt to the dynamic and uncertain manufacturing environment and ensure the stable and efficient execution of the schedule,it is necessary to consider the impact of uncertain events in job shop scheduling and develop a anti-risk schedule.Therefore,the research on the risk optimization of job shop scheduling has extremely important theoretical value and practical significance.This paper focuses on the risk optimization problem of job shop scheduling under random machine breadowns.We will first construct the risk optimization model for the job shop scheduling,and then study in depth the schedule risk optimiaiton,including risk evaluation,risk control and optimization algorithm.This paper will break through the key technologies of risk optimization for job shop scheduling and provide theoretical and methodological support for the efficient and stable execution of job shop.The main contents and achievements of this paper are listed as follows:(1)A multi-objective risk optimization model of job shop scheduling under random machine breakdowns is constructed.First,since the existing models can not effectively model multi machine breakdowns,an operation-based probability model is constructed,to model machine breakdowns reasonably.Second,the disjunctive graph model of the job shop scheduling problem with random machine breakdowns is constructed.Third,based on the influence analysis of the random machine breakdowns on the schedule performance and stability,the makespan risk and stability risk are defined.Finally,considering makespan,makespan risk and stability risk simultanueously,a multi-objective risk optimization model of job shop scheduling is provided,which takes into account the schedule performance and schedule risk,and can meet the schedule decision makers with different risk preferences(2)A schedule risk surrogate measure based on analytic approximation is proposed,to realize the accurate evaluation of job shop schedule risk.First,based on the in-depth analysis of the internal relationship among machine breakdowns,slack time and schedule risk,the concept of operation block for the effective evaluation of schedule risk is proposed.Second,taking the operation block as the basic evaluation unit and accumulating their influence on the schedule risk,the surrogate measures for the makespan risk and the stability risk are constructed respectively.Finally,a multi-objective evolutionary algorithm is used to analyze and verify the risk evaluation performance of the proposed surrogate measures.Extensive comparative experiments show that the proposed surrogate measures are much lower than the commonly used Monte Carlo simulation method in time consumption,and better than the existing slack time-based surrogate measures in evaluation accuracy,which can ensure the efficiency and accuracy of schedule risk evaluation.(3)A schedule risk control strategy based on time buffer is proposed,to realize the effective control of job shop schedule risk.First,based on the analysis of the surrogate measures of schedule risk,the operation block is taken as the basic control unit of schedule risk.Second,to make full use of the limited extra time buffer to control the schedule risk,the optimal position of the extra time buffer in the operation block is analyzed and determined.Third,the makespan risk control strategy BS1 and the stability risk control strategy BS2 are designed respectively,under the makespan constraint.Finally,a multi-objective evolutionary algorithm based on hybrid control strategies is used to analyze and verify the actual control performance of the proposed control strateges.Extensive comparative experiments show that the proposed control strateges can provide a more widely distributed solution set in schedule performance and schedule risk,and thus significantly improve the flexibility of schedule risk control.(4)A multi-objective hierarchical optimization algorithm based on search space reduction is developed.In order to solve the problem that the general optimization algorithm has poor performance in schedule risk optimization for the sharp increase of solution space,on the basis of in-depth analysis of the solution space characteristics,pre-optimizing makespan is first proposed to reduce the search range of the algorithm in the sequence space,to improve the depth seach ability.Second,the strategy combination decomposition is proposed to reduce the search range of the algorithm in the strategy combination space,to improve the breadth search ability.Finally,a multi-objective hierarchical optimization algorithm framework based on search space reduction is designed to improve the performance of the algorithm.Extensive comparative experiments show that the proposed algorithm can significantly improve the convergence and diversity of Pareto solution set,and thus enhance the solution performance of job shop schedule risk optimization.