Robust Job Shop Scheduling With Uncertainty Based On Scenario And Fuzzy Description

In the actual production process, production scheduling is the headquarters of production running in enterprises. Improving the quality and efficiency of production scheduling will play an important role in enhancing economic and social benefits of enterprises. In the theoretical research, scheduling problems are multi-objective multi-constrained optimization problems, and most of them are NP-hard. Therefore, it has important theoretical significance and practical values for production scheduling research. Shop scheduling problem which faced discrete manufacturing systems is one kind of the most important production scheduling problems.The Job Shop scheduling problem (JSSP) is one of the most classical shop scheduling problems. The model of JSSP has been widely used in many fields, such as vehicles management, train schedules scheme, logistics, course scheduling system and so on. In addition, it has effect on the research and application of the ERP which is popular in enterprise at present. Therefore, it is significant to research the Job Shop scheduling problem.In the past 40 years, shop scheduling problem has attracted numerous researchers of great interest. There has been a considerable research effort on scheduling, most of which has been focused on deterministic problems. However, manufacturing operations can be faced with a wide range of uncertainties, and time uncertainty are often caused by some uncertain events .This paper discusses the job shop scheduling problem with uncertain processing times, which are described by use of scenario planning approach and by fuzzy approach respectively. Different robust optimization models are established based on different description of uncertainties. A hybrid heuristic algorithm, which integrates genetic algorithm and simulated-annealing algorithm, is used to address the uncertain problems with robust optimization models. The main tasks of the paper are as follows: (1)The Job Shop scheduling problem with uncertain processing times to minimize the makespan is discussed. The scenario planning approach is used to represent the uncertain processing times. A robustness measure is formulated to reflect the decision-maker's preference of risk aversion, and based on this robustness measure a robust scheduling model combining the expected makespan and the robustness measure is established in this paper. The robust model can prevent the risk of deteriorating performances in bad scenarios while keeping the expected performance with little sacrifice. A genetic simulated annealing algorithm is applied to solve the robust JSSP. The performances for the robust model were compared with those for classical existing models. The computational results show that the robust model presented in this paper can compromise the expected performance and the robustness, and it is advantageous to the existing models.(2)The earliness/tardiness Job Shop scheduling problem with uncertain processing times is discussed. The uncertain processing times are described by triangle fuzzy numbers. The requirement for the due date of the product is flexible and is described by trapezoidal fuzzy number. On the basis of qualitative possibility theory, a measure of schedule robustness is defined to protect the worst-case performance. The robust optimization criterion is established by combining the robustness and the satisfaction degree of the most plausible performance.(3) A hybrid heuristic algorithm called Genetic Simulated Annealing algorithm is used in this paper after analysed the the advantages and disadvantages of enetic algorithm and simulated-annealing algorithm. A lot of experiments are done to show the efficiency of the Genetic Simulated Annealing algorithm.