Scheduling Re-entrant Lines With Neuro-Dynamic Programming Based On Simulation

Re-entrant lines are a class of complex production systems abstracted from semiconductor and film manufacturing systems. With the development of microelectronics industry, Re-entrant lines have drawn much attention of academia and industry.System descriptions, modeling, performance analysis and scheduling of Re-entrant lines are explored and some new ideas and methods are presented in this paper, whose major contributions are as follows:1. The Re-entrant line is described mathematically, where states space and scheduling sets are built; transition probability has been derived to prove scheduling a Re-entrant line is a Continuous-Time Markov Decision Process (CTMDP). Then the algorithm of building vanishing states and tangible states is designed.2. The mathematics descriptions of bottleneck workstation and block state are presented for Re-entrant lines. It has been proven that single-bottleneck station is the busiest workstation and with the highest machine utility, upon which the model simplification method is proposed. For single-bottleneck system, the non-bottleneck stations would be omitted directly; for multi-bottleneck system, the NBJP scheduling policy is developed as compensation for omission non-bottleneck stations. Then consecutive job stages can be united to one job stage under some condition. The simplification and reversion algorithms are derived for applications.3. The equivalence of mean throughput and double-machine working time as performance index is proven for two-station closed Re-entrant lines, which has been extended to multi-station closed re-entrant lines. Based on this conclusion, the dynamic programming model for CTMDP of Re-entrant lines is developed. Different methods are adopted to discretize the CTMDPs of closed and open Re-entrant lines. Terminal state is constructed to obtain the stochastic shortest path model of Discrete-Time Markov Decision Process (DTMDP) with the two release policies.4. Simulation framework of scheduling a re-entrant line based on Neuro-Dynamic Programming (NDP) is constructed for the dynamic programming model, and the corresponding iteration algorithm is designed. With the closed and open release policies, initial states, function structures, features and its uniformization method are selected and explored properly. The idea that the performance indexes of heuristic policies are applied as features is presented and realized, simulation results are satisfactory. The throughput and machines utilization are compared and analyzed for open and closed release policies.5. Machine breakdowns and repair time taken into account, the states space, scheduling set, transition probability and transition cost are rebuilt for HP's benchmark question, TRC model. Model simplification method is applied respectively to the TRC models with three different configurations. Proper release policy is selected, features and their uniformization are properly set, NDP is applied to obtain the scheduling policy. Simulation results of scheduling policy by NDP are satisfactory, which verifies the validity and superiority of the whole scheduling policy optimization system built by this dissertation.