一类单机随机调度问题解的特征

Characters of optimal solutions on a class of single machine scheduling problems

讨论了加工时间随机的单机调度问题.工件的加工时间服从指数分布,目标函数具有一般形式,涉及工件完成时间与交货期偏差的正规和非正规目标函数,如工件关于交货期拖后时间期望和,工件完成时间关于交货期绝对偏差的期望和等,都是其特殊情形.给出了最优解的特征,包括SEPT(shortestexpectedpro cessingtime)调度,LEPT(largestexpectedprocessingtime)调度和关于加工时间参数的Λ形调度.这些特征可用于确定问题的最优解.

A problem of scheduling n jobs with random processing times on a single machine is considered. The processing times are exponentially distributed. The objective is to minimize an objective function which is a general form of several regular and non_regular objective functions, such as the total expected tardiness and the total expected absolute deviations of the completion times about a common due date, etc. The characters of the optimal schedules, including SEPT (shortest expected processing time) schedule, LEPT (largest expected processing time) schedule and Λ_shaped schedule with respect to the rates of the processing times, are derived. These characters can be used to establish the optimal solutions.