确定出最佳的作业顺序看似容易,只要列出所有的顺序 然后再从中挑出最好的就可以了,但要实现这种想法几乎 是不可能的。 例如,考虑32项任务(工件),有32!≈2.6×1035种方案 假定计算机每秒钟可以检查1 billion个顺序,全部检验完毕 需要84×1015个世纪 如果只有16个工件,同样按每秒钟可以检查1 billion个顺 序计算,也需要2/3年 以上问题还没有考虑其他的约束条件,如机器、人力资源、 厂房场地等,如果加上这些约束条件,所需要的时间就无 法想象了 所以,很有必要去寻找一些有效算法,解决管理中的实 际问题
确定出最佳的作业顺序看似容易，只要列出所有的顺序， 然后再从中挑出最好的就可以了，但要实现这种想法几乎 是不可能的。 例如，考虑32项任务（工件），有32！2.61035种方案, 假定计算机每秒钟可以检查1 billion个顺序, 全部检验完毕 需要8.41015个世纪. 如果只有16个工件, 同样按每秒钟可以检查1 billion个顺 序计算, 也需要2/3年. 以上问题还没有考虑其他的约束条件, 如机器、人力资源、 厂房场地等，如果加上这些约束条件，所需要的时间就无 法想象了。 所以，很有必要去寻找一些有效算法，解决管理中的实 际问题
22排序问题的分类 根据机器数的多少 单台机器的排序问题 多台机器的排序问题 根据加工路线的特征 单件车间排序( Job Shop) 流水型排序( Flow Shop) 根据工件到达系统的情况 静态排序 动态排序 根据参数的性质 确定型排序 随机型排序 根据要实现的目标 单目标排序 多目标排序
2.2 排序问题的分类 • 根据机器数的多少 单台机器的排序问题 多台机器的排序问题 • 根据加工路线的特征 单件车间排序(Job Shop) 流水型排序(Flow Shop) • 根据工件到达系统的情况 静态排序 动态排序 • 根据参数的性质 确定型排序 随机型排序 • 根据要实现的目标 单目标排序 多目标排序
23排序常用的符号 J-工件i,i=1,2..n d-工件i交货期 P-件的加工时间,P=∑p,Pn-件i在机器上的加工 时间j=1,…,m W--工件i系统内的等待时间,W=∑wn,形-工件在机器j 前的等待时间,j=,,m C-工件完成时间,在工件都已到达的情况下,C=P,+W F工件i的流程时间,在工件都已到达的情况下,F=P+W L工件的延误时间,L1=C-d,L1=0按期或完成提前; L>0延误 T-件的延期量,T=maxO,L E-工件提前完成的时间
2.3 排序常用的符号 J i ----工件i，i=1,2,....n di ----工件i的交货期 Pi ----工件i的加工时间, , pij----工件i在机器j上的加工 时间,j=1,…,m = = m j Pi pij 1 = = m j Wi wij 1 Wi ----工件i在系统内的等待时间, , wij----工件i在机器j 前的等待时间, j=1,…,m 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提前完成的时间
24排序问题的表示方法 排序问题常用四个符号来描述 n/M/AB 其中,n-工件数; 机器数 A--2间类型,F流水型排序 P=排列排序 G=一般类型,即单件型排序 B--标函数
2.4 排序问题的表示方法 排序问题常用四个符号来描述: n/m/A/B 其中, n-----工件数； m-----机器数； A----车间类型, F=流水型排序 P=排列排序 G=一般类型,即单件型排序 B-----目标函数
第3节单台机器的排序问题 31单台机器排序问题 n个工件全部经由一台机器处理 离开系统 机器 (机器) 到达系统工 件的集合
第3节 单台机器的排序问题 3.1 单台机器排序问题 n个工件全部经由一台机器处理 J1 J2 J3 Jn 机器 到达系统工 件的集合 离开系统 （机器）