多阶段流水生产系统的批量流调度问题

1、多阶段流水生产系统的批量流调度问题 调度问题通常可按就绪时间或加工时间进行划分。 按工序就 绪时间的异同可划分为动态调度问题和静态调度问题； 按工件加 工时间的性质可分为确定型调度问题和非确定型调度问题。 二、批量流调度问题的概念和分类 1. 基本概念与分类 批量流就是把一个被加工的产品批量划分为若干个子批量， 按子批量分别组织加工和工序间的运输， 当在一台机器上一个子 批量加工完成以后， 这个子批量无须等待， 就可以直接转运到下 台机器加工。 2. Lot Streaming 调度问题的一般假设条件 （ 1）假设在零时刻，所有产品准备就绪。（ 2）产品数、机 器数、每种产品每个零件在各台机器

2、上的加工时间及产品加工的 工艺约束加工路线是已知的。（ 3）被加工的产品批量划分为 若干个子批量，按子批量分别组织加工和工序间的运输。（4） 当在一台机器上一个子批量加工完成以后，而且相继机器空闲， 这个子批量无须等待其余子批量在此机器上的加工完成， 就可以 直接转运到下台机器上进行加工。 （ 5）子批量的大小是一致的。 （6）子批量的加工时间和它的大小成正比，。 （ 7）独立的调整 时间（或可分离的设置时间）：在一台机器上，从加工一种产品 转到加工另一种产品要求机器的调整。（ 8）允许产品在工序之 间等待，允许机器在产品未到达时闲置。 以上假设条件允许改变和放松，由此可构成不同类型的 Lot

3、 Streaming 调度问题。 3. 多阶段、多产品流水车间批量流调度问题的符号和变量 以最小化最大完工时间为目标函数， 考虑各产品的子批量可 以混排的情况， 给出多阶段、 多产品流水车间调度问题的数学模 型。 符号和变量： 决策变量： 三、混合遗传算法的设计 1. 产品的基因编码 举例说明，例如：对于产品，可以表示成： 其中“ *”代表的是第个产品的一个单位产品， 两个“ 1”之 间代表这个产品的一个子批量所含的单位产品数。 也就是， 用位 来表示，第一位是“ 1”，表示一个子批量从这里开始，到下一 个“ 1”之间就是这个子批量所含的产品零件数， 再从这个“ 1” 到下一个“ 1”是另一个

4、子批量所含的产品零件数，直到最后一 位“ 1”。为了存储方便，基因表示成所有“ 1”所在的位置，如 下： 其中的数字是表示“ 1”所占的位置。那么这个产品的三个 子批量大小是： 计算公式是：第个子批量大小 =第+1 个位置的数值 - 第个位 置的数值 -1 另外“ * ”所占据的位置可以表示成： 2. 染色体 举例说明： 例如：对于 4 种产品，每种产品所含零件数分别是 25、30、 24、 28，子批量数分别是 3、5、3、4，子批量大小如表 3.1 中 所示这样一个问题。 表 3.1 产品的子批量大小 Sublot1 sublot2 sublot3 sublot4 sublot5合计 产品

5、 1 7 6 12 25 产品 2 5 11 2 6 6 30 产品 3 9 8 7 24 产品 4 8 10 5 5 28 3. 初始种群 对于产品来说，需要满足，第一个子批量的大小是随机从 1 到选的一个整数；第个子批量（第二个到第个子批量）是从 1 到 中随机选取的整数；第个子批量 =。 4. 适值函数设计 最初试验用的适值函数是： （9） 其中是这一种群中产生的最大， 迭代初期适值函数值相差很 大，选择压力大不适于扩展空间搜索， 迭代后期适值函数值相差 不大，选择压力小不适于局部最优搜索。 为了改变这种情况，迭代初期适值函数设计成： （10） 在原适值函数加上后， 迭代初期适值函数值相

6、差不大， 选择 压力小，适于扩展空间搜索。 迭代中期适值函数设计成： （11） 迭代中期适值函数趋于平稳， 相差不是特别大， 因而无需加 上。 迭代后期适值函数设计成： （12） 迭代后期适值函数值趋于常量， 相差不大， 因而将原适值函 数平方，加大选择压力。试验表明后一个适值函数好于前者。 其中的计算如下： （13） （14） （15） （16） （17） 其中是产品在机器上的加工时间。 5. 选择 每个染色体的选择概率 （即生存概率） 正比于它的适值： （ 1） 对各染色体计算适值； （ 2）计算种群中所有染色体的适值之和； （ 3）对各染色体，计算选择概率；（ 4）对各染色体，计算累积

7、概率。 6. 交叉方案 （1）每种产品的交叉方案：采用的是单断点交叉法。随机 选取一个断点进行交叉， 交换双亲上断点的右端， 产生新的后代。 （2）染色体的交叉方案：采用对染色体中所有产品都进行交叉 和部分染色体进行交叉两种交叉方案。 7. 修复方案 由于交叉操作后， 产生了不可行的染色体， 所以必须进行修 复。 若产生编码如下： 1 9 6 9 18 21 基因编码就是不可行的，第二位和第四位都是9，对这种情 况就要进行修复。 这里采用的修复方法是先对染色体中的数字进 行排序， 然后对两个位置上数值相同的基因进行修复， 本例中的 第三位和第四位数值相同，随机选取其中的一个9，在零件所占 的位

8、置上随机选取一个数值进行替换。 8. 变异方案 每种产品的变异方案： 举例说明： 例如对进行变异， 随机选取一个除了两端位置的 任何一个位置，再随机从零件所占据的位置中随机选一个替换。 1 5 8 12 9. 排序 1983年 M.nawaz, E.E.Enscore 和 I.Ham 提出 NEh算法。据 文献报道，该算法是目前已知的求解排列排序 Flow shop 调度问 题最小加工周期时性能最好的算法之一。 该算法是基于这样一个 基本假设：一个产品的总加工时间越长，它具有越高的优先权。 具体步骤如下：（ 1）将个产品按各自在机器上加工的总时 间降序排列；（ 2）单独考虑开始两个产品，并以极

9、小化部分加 工全长为目标将它们排序；（ 3）对转入步骤（ 4）；（ 4）将初 始排列中的产品插入到前面个可能位置中的一个位置， 而使部分 加工全长最小。 10. 混合遗传算法流程 （1）生成初始种群；（2）交叉、变异修复；（3） NEH非 序；（ 4）选择；（ 5）若未达终止条件，转 2；否则结束，输出 结果。 四、计算实验 通过实验发现非混合遗传算法比混合遗传算法效果好， 所以 下面的实例均是选中非混合遗传算法。 Example1. 实验是以 10*10（10 个工件和 10 台机器）为模型 的。 设置：不考虑设置时间，可等待； 每个工件所含的单元数和必须被分的子批量数如下： 每个工件每个单位在每台机器上的加工时间： 图1 不采用批量流的方法时，用NEH算法进行计算，最小最大完 工