随机JIT排序问题

Stochastic JIT Scheduling Problem

讨论随机JIT排序问题.由于目标函数是完工时间与工期平方偏差和的数学期望(ESSD)时,有些问题的求解变的非常困难,采用的目标函数是期望完工时间与工期平方偏差和(SSDE).证明极小SSDE函数的最优排序具有V-形性质,这个性质对构造有效算法是非常有用的.于是使有的问题变得简单,使有的不能解决的问题得以解决.还证明了ESSD函数和SSDE函数的差别并不大.

In this paper we discuss stochastic JIT scheduling problem. When object function is the expected sum of squared deviations（ESSD） of the job completion times, some problems are very hard for solving. Our object function is the sum of squared deviations of the job expected completion times（SSDE）. We prove that the optimal scheduling for minimizing SSDE function has V-property. It is very useful for constituting effective algorithm. So, some problems become simpler, and some problems can be solved. We proved that difference between ESSD function and SSDE function is small.