40
14
40÷55+3=8
8-5=3
8+1=9
9-4=5
9+4=13 13-8=5
13+2=15 15-7=8
50
21
50÷5=10 21÷5=4.2
13
第2节流水作业排序问题
• 流水作业排序问题的特征是每个工件的加工路线 都是一样的,常见的目标函数有时间表长和加权 总完工时间。
14
一、时间表长的计算
对于给定n个工件、m台机器的排列排序问题
Fm|prmu|Cmax,设工件顺序为J1,J2,…,Jn,其中Jj为排第 i位加工的工件的代号,以Cij表示工件Jj在机器Mi上 的完工时间,pij表示工件Jj在Mi上的加工时间 (i=1,2,…,m;j=1,2,…,n),那么:
i
C i1 p l1
232
338
446
本例Cmax=46。
17
二、问题 F2 || Cmax的排序算法 对于两台机器的流水作业排序问题,约翰逊 (S.M.Johnson)于1954年提出了一个有效算法, 用于解决多种工件在两台设备上加工的流水作业 排序问题,这就是著名的Johnson算法。Johnson算 法的适用条件是: (1)排序的目标是使全部完工时间最小; (2)工件在两台设备上的加工顺序完全相同; (3)所有工件同时到达第一台设备等待加工; (4)每种工件在每台设备上的加工时间均已知。
三个参数为:α,β,γ,分别代表特定的机器环境、工件 特征和最优准则,它们是排序问题的三个组成部分。
• 机器环境:描述机器的数量、类型、不同机器之 间的关系以及环境
• 工件特征:描述一般可用工件的性质,加工要求和 限制,资源的种类,数量和对加工的影响等来描述。