Research On The Robust Scheduling Of Job Shop With Stochastic Processing Times

The uncertainties in a real-life job shop manufacturing environment,such as random machine breakdown,shortage of tools or materials,difference of worker's proficiency level,will lead to the randomness of realized processing times.Under severe circumstances,the processing time variation will lead to the deviation of the actual schedule from the optimal schedule,which will seriously affects the delivery requirements,the allocations of workers and raw material,thus worsen the production costs,system stability,and customer satisfaction degree.In order to ensure the stable and efficient execution of the schedule under the stochastic variation of processing times,it is needed to optimize the scheduling performance and reduce the potential influences of stochastic processing times on the scheduling performance simultaneously.Thereby,it is of great theoretical and practical significance to study the job shop scheduling problem with stochastic processing times(SJSSP).This paper focuses on the SJSSP and employs the robust scheduling method to resist the processing time variation.The SJSSP robust scheduling problems under different constraints are systematically studied based on processing time scenarios,with the aim of providing schedule that take both performance and robustness into account to the decision makers.First,the robust scheduling of SJSSP based on stochastic processing time scenario is studied considering the influence of uncertainties on the processing times.Second,aiming at the resources waste and scheduling disorder that caused by prematurely start or deliberately delay due to the subjective factors of the workers,the robust scheduling of SJSSP considering the negative subjective factors of the workers is studied.Thereafter,considering the controlling function of the worker's proficiency on the randomness of processing times,the SJSSP robust scheduling problem with machine-worker dual-resource constraints is studied.The main contents and contributions of this dissertation are given as follows:1.The modeling of robust scheduling of SJSSP considering the stochastic processing timesThree robust scheduling models are formulated using the corresponding robust scheduling strategies by analyzing the characteristics of the SJSSP under different constraints.First,the expected performance is used as a robust evaluation function to formulate a robust scheduling model of SJSSP(SJSSP-SSP).Second,considering the “Student Syndrome” and “Parkinson's Law” of the workers,the “railway execution strategy” is employed with the aim of reducing resources wastage and scheduling disorder.Thus,an SJSSP robust scheduling model based on the expected processing time scenario is formulated(SJSSP-ESP).Furthermore,considering the controlling function of the worker's proficiency level on the randomness of the processing times,the dual-resource constrained robust scheduling model of SJSSP-ESP is formulated(DR-SJSSP-ESP).2.Research on the robust scheduling of SJSSP based on stochastic scenarios of processing timesA hybrid estimation of distribution algorithm including an evaluation space reduction strategy is proposed to solve the SJSSP-SSP.First,a hybrid algorithm based on estimation of distribution algorithm(HEDA)is proposed.Afterward,an evaluation space reduction strategy(RS)is proposed to improve the computing efficiency of HEDA.The RS is then embedded into the HEDA to construct an enhanced RS-HEDA.The simulation results show that the HEDA has a better performance than five existing algorithms.Meanwhile,the RS-HEDA can significantly improve the computational efficiency of HEDA for solving the SJSSP-SSP without sacrificing the optimization performance.Finally,the effectiveness of the model and algorithm is verified through the simulation of the scheduling case of manufacturing enterprise.3.Research on the robust scheduling of SJSSP based on expected scenarios of processing timesA multi-objective optimization algorithm based on surrogate measures of robustness is proposed for solving the SJSSP-ESP.First,to reduce the computational burden of simulation-based robustness measure,two surrogate measures of robustness based on critical operation set and non-critical operation set are proposed.In the proposed surrogate measures,both the stochastic information of processing times and the disturbance absorption ability of the schedule solutions are employed.To obtain the Pareto solutions with both excellent performance and robustness of SJSSP-ESP,an improved non-dominated sorting based multi-objective HEDA(MO-HEDA)is developed.The effectiveness of the proposed surrogate measures for SJSSP-ESP robustness evaluation is validated by comparing the simulation results with three existing surrogate measures.Second,the proposed surrogate measures are employed to conduct the SJSSP-ESP robust scheduling and then compared with the simulation-based robustness measure under four evaluation criteria.The simulation results demonstrate that the proposed surrogate measures can achieve satisfactory Pareto solutions with significantly improved computational efficiency.Finally,through the simulation of manufacturing scheduling cases,the effectiveness of the proposed surrogate measure of robustness and the algorithm for real-life robust job shop scheduling is verified.4.Research on the robust scheduling of machine-worker dual-resource constrained SJSSP based on expected scenarios of processing timesThe machine-worker two-stage assignment method and the surrogate measure of robustness under dual resource constraints are proposed,and the MO-HEDA is used to solve the DR-SJSSP-ESP.First,a model is formulated to evaluate the relationship between the worker's proficiency and the randomness of processing time.Second,a two-stage machine-worker assignment strategy(TSAS)is proposed based on the worker's proficiency level and workload balance.Moreover,in order to improve the robustness evaluation efficiency of the MO-HEDA,a surrogate measure of robustness based on disturbance propagation is proposed by analyzing the propagation mechanism of the processing time disturbances among the operations.The effectiveness of the proposed surrogate measure of robustness and the advantages of the proposed two-phase assignment strategy are verified by simulation experiments.Furthermore,using the MO-HEDA,the Pareto robust scheduling optimization results of DR-SJSSP-ESP are analyzed.The results verify that the Pareto solutions with excellent performance can be obtained with significantly improved computational efficiency by using the proposed two-stage assignment strategy and the developed surrogate measure of robustness.Finally,through the simulation of the scheduling case extracted from the manufacturing system,the effectiveness of the proposed assignment strategy and surrogate measure of robustness for solving the real-life job shop robust scheduling problem under dual-resource constraints is verified.