j 1
j=1,…,m
8
Ci----工件i的完成时间, 在工件都已到达的情况下, Ci= Pi+ Wi
Fi----工件i的流程时间,在工件都已到达的情况下, Fi= Pi+ Wi Li----工件i的延迟时间, Li= Ci- di , Li<=0 按期或完成提前;
Li>0 延迟 Ti----工件i的延误, Ti=max{0, Li} Ei----工件i提前完成的时间
例如,考虑32项任务(工件),有32!2.61035种方案,假定计 算机每秒钟可以检查1 billion个顺序, 全部检验完毕需要8.41015个 世纪.
如果只有16个工件, 同样按每秒钟可以检查1 billion个顺序计算, 也需要2/3年.
以上问题还没有考虑其他的约束条件, 如机器、人力资源、厂房 场地等,如果加上这些约束条件,所需要的时间就无法想象了。
12
• 根据工件到达系统的情况 静态排序 动态排序
• 根据要实现的目标 单目标排序 多目标排序
13
1.3.5 排序问题的表示方法
排序问题常用四个符号来描述: n/m/A/B
其中, n-----工件数; m-----机器数; A----车间类型, F=流水型排序 P=流水型同顺序排序 G=一般类型,即单件型排序 B-----目标函数
•
平均延误时间: 1
T
1 n
n
Ti
i1
最大延误时间:Tmax max{Ti}
• 2)以工件的完工时间和工件的流程时间为目标函数
• 最长完工时间:Cmaxmax{Ci} 最长流程时间:Fmax max{Fi}
•
平均完工时间:
C
1 n
n