Studies on insensitive job shop schedules to the effect of uncertainty

点击翻译按钮获取中文摘要

Actual production environments often involve several uncertainties, and it is often required to obtain less sensitive schedules to the occurrence of uncertain events. Job shop schedules often involve inevitable idle states on machines, and this research started from an idea that such idle states can absorb the occurrence of uncertain events. Our previous study has proposed a new measure named instability to evaluate the sensitivity of a schedule against the uncertainty of processing times. The minimum instability schedule is insensitive to the one time unit of completion delay in any operation. Based on this measure the following three subjects are discussed in this study : (i)develop effective instability minimization methods, (ii)explore the relationship between minimum instability schedules and minimum makespan schedules, and (iii)apply the instability minimization to the decomposition-based job shop scheduling. To minimize the instability efficiently, a new lower bound calculation … More method is developed. In addition, a search tree with a complete schedule in each node is proposed to accelerate the search. The relationship between minimum instability schedules and minimum makespan schedules is clarified by enumerating all active schedules. The results indicated that it is generally difficult to minimize instability and makespan jointly, the degree of conflict between these two objectives is relatively low, and the number of optimal schedules is small for each objective. In the decomposition-based makespan minimization, two sub-problems are generated by dividing machines into two cells. Each sub-problem is solved to minimize the makespan, and then to minimize the instability in order to relax the operation conflicts when combining two sub-schedules. Numerical experiments showed that the minimum instability sub-schedules often produced better results when compared with the maximum instability sub-schedules, although all these sub-schedules are optimized in terms of the makespan. Less