Analysis of the temporal decomposition procedure for scheduling with release and due dates

This paper first presents an improved method of temporal decomposition for minimising the searching space of scheduling problems. Next, the effects of the temporal decomposition procedure in scheduling problems are analysed. It is theoretically shown that the complexity of a scheduling algorithm using decomposed subsets varies inversely with that of the decomposition procedure. Therefore, the efficiency of the overall scheduling algorithm is strongly related to the decomposability of the set of operations to be processed on each machine. This decomposability is evaluated using a probabilistic approach where the probability distributions of the scheduling parameters are obtained from historical workshop data. The average number of decomposed subsets and the average size of these subsets are estimated. Both theoretical analysis and simulation results have revealed that the decomposition procedure leads to optimal effects when some conditions on scheduling parameters are met.