Research Of Scheduling Algorithm On Large Automated Storage And Retrieval System

Automated storage and retrieval systems (hereafter, "AS/RS") have been a significant link in modern logistics and CIMS and have been playing an increasingly role in the production of modern enterprise. AS/RS is defined as a complex system with the discrete, random, dynamic, multi-factor and multi-objective characteristics. To realize the intelligent management for AS/RS leads to the complex optimization problems. As an important development for the automated warehousing system (AS/RS), the large warehouse systems are the kinds of systems which need more complex control strategies and higher optimize efficiency requirements. The traditional optimization methods for solving these problems require longer time, higher costs and more difficult to obtain the optimal solution.In this thesis, the optimization-methods researches of AS/RS are carried out by combining the theoretical research of fast genetic algorithms (hereafter, "GA") with the large warehouse system of institute of electrical and mechanical project of Beijing capital international airport in order to improve the intelligent management and the overall system efficiency of the large warehouse. The study has an important engineering significance for improving the intelligence level of the large warehouse system, increasing the warehouse efficiency, reducing the operating costs and improving the competitiveness of logistics operations, research and development enterprise. The important theoretical values of the research lie on the main research objectives of genetic algorithms, such as how to obtain an efficient, stable, fast and reliable GA, how to better simulate the adaptive process and evolution behavior of the complex systems, how to reach a global convergence in solving optimization problem, how to assess the search efficiency, how to combine with other algorithms and how to better meet the engineering needs.The main contents of the thesis are as follows:1. To take the catering automated warehouse of Beijing Capital International Airport as the example, the AS/RS workflow and characteristic are analyzed, especially for the large warehouse system. Then, the direction and content about intelligent control parts are proposed and the optimization models of the large warehouse system are established. In addition, GA is adopted as the main optimization algorithm with the optimization objective functions and the constraints of the large warehouse system.2. A fast single-objective constrained GA is designed. The constraint handling method of the algorithm is proposed by using infeasible solutions to expand the search scope and it can avoid the introduction of the penalty factor as well. Meanwhile, we designed a kind of "remember" cross-operator that could prevent the phenomenon of individual’s "atavism" avoid the repeated search and improve the efficiency of search. The mutation operators with the various step length and direction are developed to ensure the quick search capabilities in the early period and the retention capacity of the optimal solution in the later period. The elitism strategy is used to make the best individuals of the parent to pass down to their offspring. Thus, the algorithm has strong robustness. The performance analyses show that the algorithm is a first-order and fast convergence GA, which has the convergence rate three times over the other genetic algorithms. As for the convergence rate, it will be no influence with the different choice of parameters. Thus, this algorithm could find the global optimal solution after the fifth iterations.3. A fast multi-objective constrained GA is proposed. A kind of crossover operator that could simultaneously search from the feasible solution space to the infeasible solution space is designed. Combining the constraint conditions with the objectives, a new partial-order relation for comparing the merits among the individuals is introduced. Thus, a new Niche computation method for maintaining the diversity of population is suggested and the repeated search is avoided using the searched solution space. To use Markov chains as an anal tical tool, the convergence of the algorithm is proved. The simulation results show that this algorithm could rapidly converge at global Pareto solutions and maintain the diversity of population comparing with the current MOEAs.4. Genetic algorithms are adopted to optimize the cargo space and the picking-up path of the automated warehouse. For an AS/RS, the optimal control objectives, such as the optimal warehouse assignments, the optimal locations assignments and the optimal travel time, are proposed based on a stochastic storage strategy. To use the penalty function methods, the constraints conditions are handled including the capacity and the travel speed of storage/retrieval machines (SRMs), the rules of SRMs in a multi-command cycle such as storage first and retrieval last, storage from near to far and retrieval from far to near. The optimal Pareto solution of the dynamic location assignment and the optimal picking-up path were obtained by using GA in the large automated warehouse, in which some spaces have been already occupied. The experiments show that the methods proposed in the thesis could meet the practical engineering needs of the optimal control warehouse.5. The dynamic standby position of stacker is studied in the AS/RS. According to the library strategy of the storage time priority, m possible access points{Pi|i=1,..., m} are determined. The flow rates of those points are determined using random storage strategy one by one. Meanwhile, it has been proved that m possible access points were the parts of Glassman space. The dynamic standby position of stacker is solved by using multi-particle center of gravity method, which are the mapping from Glassman space to affine space. The results show that the overall performances of the proposed methods are superior to the existing research results. 6. Based on the above research results, the performances of a large storage system are analyzed. Dynamically selecting of the cargo space is determined by means of GA in automated warehouse and the dynamic standby position of stacker is obtained by using multi-particle center of gravity method. Moreover, we found the average operating time of the stacker in the automatic warehouse by the use of the acceleration and deceleration curves and obtained the storage capacity of the automatic warehouse ultimately. By then, the contribution of the improvement of out of storage capacity the location assignment, the optimal picking-up path and the dynamic standby position were analyzed. Accordingly, the results reflect the engineering value of this research project.The research results of the thesis have been partly implemented in the large warehouse system of Institute of Electrical and Mechanical project of Beijing Capital International Airport with the excellent optimization effect.