Abstract: For the job-shop scheduling problem with processing time variability,the processing time variability was described by interval number method.Based on analyzing 6 kinds of relations between job complete time interval and job due window,the calculate method of Earliness/Tardiness (E/T) penalty interval corresponding with processing time interval was given.The wave range of E/T penalty could be estimated by E/T penalty interval,which provided theoretic support to the transformation from uncertain scheduling problem to interval scheduling problem.Based on selecting E/T penalty interval as optimization goal,a new interval model was developed.The possibility degree of interval number was used to evaluate uncertain E/T target between different schedules,which solved the problem of fitness value evaluation in the evolution of genetic algorithm.The numerical simulation was conducted to demonstrate the effectiveness of proposed interval number theorem and model.

Key words: processing time variability, job-shop scheduling, ear1iness/tardiness, interval number, possibility degree of interval number

摘要： 针对一类难以获取工序加工时间变量的准确分布规律或隶属度函数的作业车间调度问题,采用区间数方法描述工序加工时间不确定变量,在分析工件完工时间区间与交货期时间窗的6种关系的基础上,分析归纳出提前/拖期惩罚取值区间的求解方法|论证了提前/拖期惩罚区间可以预估提前/拖期惩罚值的波动范围,为不确定调度问题转化为区间调度问题求解提供了理论支撑。以提前/拖期惩罚的取值区间为优化目标构建了区间调度模型。通过区间可能度方法对不同的提前/拖期指标区间值进行定量比较,解决了遗传算法求解区间调度模型时适应度值的比较问题。通过算例仿真验证了区间数定理和调度算法的有效性。

关键词: 加工时间不确定, 作业车间调度, 提前/拖期, 区间数, 区间可能度