流水车间调度问题的研究-周杭超

流水车间调度问题的研究 机械工程学院 2111302120 周杭超 如今 为了满足客户多样化与个性化的需求 多品种 小批量 生产己经为一种重要的生产方式 与过去大批量 单一的生产方式 相比 多品种 小批量生产可以快速响应市场 满足不同客户的不 同需求 因此 受到越来越多的企业管理者的重视 特别是以流水 线生产为主要作业方式的企业 企业管理者致力于研究如何使得生 产均衡化 以实现生产批次的最小化 这样可以在不同批次生产不 同品种的产品 在这种环境下 对于不同批次的产品生产进行合理 调度排序就显得十分重要 在传统的生产方式中 企业生产者总是力求通过增加批量来减 小设备的转换次数 因此在生产不同种类的产品时 以产品的顺序 逐次生产或用多条生产线同时生产 这样 必然会一次大批量生产 同一产品 很容易造成库存的积压 在实际生产中如果需要生产 A B C D 四种产品各 100 件 各种产品的节拍都是 1 分钟 如果按 照传统的做法 先生产出 100 件 A 产品 其次是 B 然后是 C 最后 生产产品 D 在这种情况下 这四种产品的总循环时间是 400 分钟 然而 假设客户要求的循环时间为 200 分钟 四种产品的需求量为 50 件 那么在 200 分钟的时间内就只能生产出产品 A 和产品 B 因 而不能满足客户需求 同时还会过量生产产品 A 和 B 造成库存积 压的浪费 这种生产就是非均衡的 如图 1 所示 比较均衡的生产方式 图 2 是 在一条流水线上同时将四种产 品混在一起生产 并且确定每种品种一次生产的批量 当然 如果 在混合生产时不需要对设备进行转换 那么单件流的生产方式是最 好的 然而 在实际生产 A B C D 四种不同产品时 往往需要 对流水线上的某些设备进行工装转换 单件流的生产方式在此难以 实现 需要根据换装时间来确定每种产品一次生产的批量 同时 由于现实生产中不同产品在流水线上各台机器的加工时间很难相同 因此 流水线的瓶颈会随着产品组合的不同而发生变化 当同一流 水线加工多产品 并且每种产品在各道工序 各台机器 的加工时间 差异较大时 瓶颈就会在各道工序中发生变化 如何对各种产品的 投产顺序进行优化以协调这些变化的瓶颈是生产管理中一个很重要 的问题 图 1 图 2 因而对流水线调度问题的研究正是迎合这种多品种 小批量生 产方式的需要 我们要讨论得是如何对流水线上生产的不同产品的 调度顺序进行优要化 流水车间调度问题一般可以描述为 n 个工件要在 m 台机器上加 工 每个工件需要经过 m 道工序 每道工序要求不同的机器 n 个 工件在 m 台机器上的加工顺序相同 工件在机器上的加工时间是给 定的 设为 问题的目标是确定个工件在每台 1 1 ij t in jm 机器上的最优加工顺序 使最大流程时间达到最小 对该问题常常作如下假设 1 每个工件在机器上的加工顺序是给定的 2 每台机器同时只能加工一个工件 3 一个工件不能同时在不同机器上加工 4 工序不能预定 5 工序的准备时间与顺序无关 且包含在加工时间中 6 工件在每台机器上的加工顺序相同 且是确定的 问题的数学模型 12 m iin c j kjkjjj n 工件在机器上的加工完工时间 工件的调度 个工件 台机器的流水车间调度问题的完工时间 1 11 1 j c jt 1 11 1 2 j k c j kc j ktkm 11 1 1 2 i iij c jc jtin 1 max 1 2 2 i iiij k c j kc jk c j ktin km max n cc j m 最大流程时间 12max n jjjc 调度目标 确定使得最小 本文中以 4 个工件 4 台机器流水线调度为例 该流水线由四 台机器 M1 M2 M3 M4组成 加工顺序分别是 M1 M2 M3 M4 各工件在各机器上的加工时间如下表所示 工件 1M2M3M4M J185410 J21547 J39438 J43915 1 问题的编码方式与初始群体的生成 在流水车间调度问题中 最自然的编码方式是用染色体表示工 件的顺序 对于有四个工件的生产调度 第 个染色体 k 1 2 3 4 k v 表示工件的加工顺序为 12 34 J J JJ 遗传算法必须对种群进行操作 所以必须准备一个由若干解组 成的初始种群 合适的群体规模对遗传算法的收敛具有重要意义 群体太小难以求得满意的结果 群体太大则计算复杂 根据经验 群体规模一般取 10 160 2 确定问题的适应度函数 遗传算法对一个个体 解 的好坏用适应度函数值来评价 适应度 函数值越大 解的质量越好 适应度函数是遗传算法进化过程的驱 动力 也是进行自然选择的唯一标准 它的设计应结合求解问题本 身的要求而定 在该调度问题中将最大流程时间的倒数作为适应度 函数 令表示 k 个染色体的最大流程时间 那么适应度值为 max k c max 1 k k eval v c 3 选择 选择操作也称复制操作 是从当前群体中按照一定概率选出优 良的个体 使它们有机会作为父代繁殖下一代子孙 判断个体优良 与否的准则是各个个体的适应度值 显然这一操作借用了达尔文适 者生存的进化原则 即个体适应度越高 其被选择的机会就越多 该方法的基本思想是 各个个体被选中的概率与其适应度函数 值大小成正比 设群体大小为 n 个体 i 的适应度为 则个体 i 被 iF 选中遗传到下一代群体的概率为 1 n iii i PFF 计算群体中所有个体的适应度函数值 需要解码 利用比例选择算子的公式 计算每个个体被选中遗传到下一代 群体的概率 采用模拟赌盘操作 即生成 0 到 1 之间的随机数与每个个体遗传 到下一代群体的概率进行匹配 来确定各个个体是否遗传到下一代群 体中 它是先按个体的选择概率产生一个轮盘 轮盘每个区的角度 与个体的选择概率成比例 然后产生一个随机数 它落入轮盘的哪 个区域就选择相应的个体交叉 显然 选择概率大的个体被选中的 可能性大 获得交叉的机会就大 4 交叉操作 交叉操作是对两个染色体操作 组合两者的特性产生新的后代 两个父代在交叉时 可能会产生非法的后代 在该调度问题中 如果用单点交叉算子 就可能出现如 2312 的非法解 在该染色体中 有两个重复的基因 2 它们都表示产品 但丢失了产品 因此 2J4J 采用部分映射交叉算子 在染色体中随机产生两个交叉点 交换两个父染色体交叉点中 间的部分 如果生成的子染色体中若有非法的重复部分 用交叉部 分对应的基因替换交叉点两侧的基因 在该调度问题中假设有两个染色体父代 1 和父代 2 其部分映 射交叉操作如下 后代 1 和后代 2 是中间染色体交叉操作中的过渡状态 5 变异操作 变异操作是一种基本运算 在染色体上自发地产生随机的变化 该调度问题中的一个染色体为 4123 对其进行变异 任意交换第 1 个基因与第 3 个基因的位置 变异前 4123 变异后 2143 6 参数确定 种群规模 m 50 遗传运算的终止进化代数 T 100 交叉概率 0 85 c