流水作业排序问题 —— 加工路线相同
2020/3/6
第一节 作业排序的基本概念
2. 按工件到达车间的情况不同,可以分成 静态的排序问题 —— 排序时所有工件都已到达,可以一次 对它们进行排序. 动态的排序问题 —— 排序时工件陆续到达,要随时安排它们 的加工顺序
3. 按目标函数的性质不同,也可划分不同的排序问题 使平均流程时间最短
通过 n / m /A / B 这4个符号，就可以简捷的表述 一般的排序问题了。例如， n / 3 / P / Cmax 表示n 个 工件经3台机器加工的流水作业排列排序问题，目标 函数是使最长完工时间最短。
2020/3/6
• 排序问题常见的分类方法有按机器、工件、目标函数的特征分类。
• 排序问题由4个参数表示：n / m /A / B。
到完工,不得中途停止插入其它工件。 4. 工件在每道工序的加工只在一台机器上进行。 5. 工件数（或批量）、机器数已知，单件加工时间已知,
完成加工的时间与加工顺序无关。 6. 每台机器同时只能加工一个工件。
2020/3/6
符号说明
• Ji —— 第 i 工件，i = 1,2,…,n ；
• Mj —— 第 j 台机器，j =1,2,…,m；
本节只讨论排列排序问题。但对于2台机器的排序问题,实际上不 只是排列排序问题，因为两者的最优解及其解法是相同的。
2020/3/6
一、最长流程时间Fmax的计算 最长流程时间就是工件在车间实际停留的最长时
间。 本节所讨论的是n/m/ρ/Fmax问题,目标函数是使最 长流程时间最短。最长流程时间又称作加工周期,它 是从第一个工件在第一台机器开始加工时算起,到最 后一个工件在最后一台机器上完成加工时为止所经过 的时间。由于假设所有工件的到达时间都为零(r = 0 ，i = 1,2,…,n),所以Fmax等于排在末位加工的工件在 车间的停留时间,也等于一批工件的最长完工时间 Cmax。
