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

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

作　　者：贾春福[1] 

机构地区：[1]南开大学信息技术科学学院,天津300071

出　　处：《系统工程学报》2003年第6期552-555,共4页Journal of Systems Engineering

基　　金：天津市自然科学基金重点资助项目(033800611).

摘　　要：讨论了加工时间随机的单机调度问题.工件的加工时间服从指数分布,目标函数具有一般形式,涉及工件完成时间与交货期偏差的正规和非正规目标函数,如工件关于交货期拖后时间期望和,工件完成时间关于交货期绝对偏差的期望和等,都是其特殊情形.给出了最优解的特征,包括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.

关 键 词：单机随机调度问题 最优解 目标函数 指数分布加工时间 

分 类 号：O224[理学—运筹学与控制论]