也谈不上流水型或单件作业B目标函数例5个工件经过4台设备.ppt

加工顺序 ② ③ ① ④ (1) (2) （3） 2 12 9 8 6 27 18 10 ti1 ti2 Fi1 Fi2 ti3 Fi3 2 4 6 1 3 9 8 2 5 8 4 2 11 19 23 29 当L=2时，排序为②一③一①一④ Fmax=29 故按CDS法排序结果为：①一②一③一④ Fmax=28 i 1 2 3 4 L=1 ti1 1 2 6 3 ti3 4 5 8 2 L=2 ti1+ ti2 9 6 8 12 ti2+ ti3 12 9 10 11 ?设备 零件 ① ② ③ ④ ⑤ （1） 4 8 2 5 9 （2） 2 3 6 4 1 （3） 5 7 3 8 4 （4） 6 2 16 7 8 课堂练习： 分别用零件的斜率指标法、关键零件法、 CDS法对下列流水型问题排序，并求加工周期。 4、实际应用例题 例：东风汽车维修和上漆公司正在争取一份名为“风暴的合同，这个合同的一个主要要求就是迅速交货，即如果能够将5辆需要维修和喷漆的车在24小时内整修并重新喷漆，这份合同就成交．下面是东风汽车维修和上漆公司对这5辆车进行整修和上漆分别所需的作业时间．问东风汽车维修和上漆公司能否取得这份名为风暴”的合同．工艺要求在喷漆之前必须先进行整修． 汽车 整修时间(小时) 喷漆时间(小时) A 6 3 B 0 4 C 5 2 D 8 6 E 2 1 铣床 到达系统工件的集合 离开系统 （机器） J1 J2 Jk . . Jn 车床 磨床 车床 离开系统 （机器） 磨床 铣床 Ji Jk 单件作业排序问题的特征：零件的加工路线不同 第四节 单件作业排序问题 1、问题的描述 2、排序方法 3、优选调度法则 1、问题的描述 (1)对于流水型作业排序问题，第K道工序永远在MK上加工，没有必要将工序号与机器号分开. (2)对于单件作业排序问题，要描述一道工序，必须将工件号、工序号和机器号结合在一起。 试说明事件 (3，4，1)和事件(2，3，3)的含义 (3)上图中每个方框表示一个事件。事件的表达方式为： (i，j，k)，i表示工件号，j表示工序号，k表示完成i工件的第j道工序的机器代号。 J1,1,铣床 J1,2, 车床 J1,m，磨床 J1 Jk,1,车床 离开系统 （机器） Jk,2,磨床 Jk,m,铣床 Jk 离开系统 （机器） (5)用加工描述矩阵D来描述所有工件的加工 每一行描述一个工件的加工，故每一行的工件号相同，每一列的工序号相同．? (6)加工时间矩阵 2 4 2 3 5 4 T＝ 1,1,1 1,2,3 1,3,2 2,1,3 2,2,1 2,3,2 D＝ 单件作业计划种类: 半能动作业计划（Semi-active schedule） 各工序都按最早可能开（完）工时间安排的作业计划。 能动作业计划（Active schedule） 任何一台机器的每段空闲时间都不足以加工一道可加工工序的半能动作业计划。 无延迟作业计划（Non-delay schedu1e） 没有任何延迟出现的能动作业计划。 “延迟”： 有工件等待加工时，机器出现空闲，即使这段空闲时间不足于完成一道工序。 2 两种单件作业排序方法 2 两种单件作业排序方法 例：加工描述矩阵和加工时间矩阵如下，分别按下列两种方法进行作业排序． ? (1)最小最早完工时间法（能动作业计划） (2)最小最早开工时间法（无延迟作业计划） 1,1,1 1,2,3 1,3,2 2,1,3 2,2,1 2,3,2 D＝ 2 4 2 3 5 4 T＝ (l)最小最早完工时间法 1,1,1 1,2,3 1,3,2 2,1,3 2,2,1 2,3,2 D＝ 2 4 2 3 5 4 T＝ 序列 可排事件 最早可能开工时间 最早可能完工时间 最小最早可能完工时间 所需机器 排定事件 1 2 3 4 5 6 1,3,2 M2 14 14 12 1,3,2 2,3,2 M2 9 9 12 7 8 1,3,2 2,3,2 2,2,1 M1 8 9 8 7 3 1,3,2 2,2,1 1,2,3 M3 7 7 8 3 3 1,2,3 2,2,1 2,1,3 M3 3 6 3 2 0 1,2,3 2,1,3 1,1,1 M1 2 2 3 0 0 1,1,1 2,1,3 排定事件条件 最小最早完工时间法选择排定