流水车间调度问题的研究
机械工程学院 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 i n j m ==L L 。
问题的目标是确定个工件在每台机器上的最优加工顺序，使最大流程时间达到最小。
对该问题常常作如下假设:
(1)每个工件在机器上的加工顺序是给定的;
(2)每台机器同时只能加工一个工件;
(3)一个工件不能同时在不同机器上加工;
(4)工序不能预定;
(5)工序的准备时间与顺序无关，且包含在加工时间中;
(6)工件在每台机器上的加工顺序相同，且是确定的。
问题的数学模型：
{}12(,) ,,, m i i n c j k j k j j j n L ：工件在机器上的加工完工时间，：工件的调度个工件、台机器的流水车间调度问题的完工时间：
111(,1)j c j t =
111(,)(,1),2,...,j k c j k c j k t k m
=-+= 11(,1)(,1),2,...,i i i j c j c j t i n -=+=
1(,)max{(,),(,1)},
2,...,;2,...,i i i i j k c j k c j k c j k t i n k m -=-+==max (,)n c c j m =最大流程时间：
{}12max ,,,n j j j c L 调度目标：确定使得最小。
本文中以4个工件、4台机器流水线调度为例，该流水线由四台机器M 1 ，M 2 ，M 3 ，M 4组成，加工顺序分别是M 1 →M 2 →M 3→M 4，各工件在各机器上的加工时间如下表所示。
1.问题的编码方式与初始群体的生成
在流水车间调度问题中，最自然的编码方式是用染色体表示工件的顺序：对于有四个工件的生产调度，第k 个染色体 [1,2,3,4]k v =， 表示工件的加工顺序为：12,34,,J J J J 。
遗传算法必须对种群进行操作，所以必须准备一个由若干解组成的初始种群。
合适的群体规模对遗传算法的收敛具有重要意义。
群体太小难以求得满意的结果，群体太大则计算复杂。
根据经验，群体规模一般取10~160。
2.确定问题的适应度函数
遗传算法对一个个体(解)的好坏用适应度函数值来评价，适应度函数值越大，解的质量越好。
适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。
在该调度问题中将最大流程时间的倒数作为适应度函数。
令max k
c 表示k 个染色体的最大流程时间，那么适应度值为： max 1()k k eval v c =
3.选择
选择操作也称复制操作，是从当前群体中按照一定概率选出优良的个体，使它们有机会作为父代繁殖下一代子孙。
判断个体优良与否的准则是各个个体的适应度值。
显然这一操作借用了达尔文适者生存的进化原则，即个体适应度越高，其被选择的机会就越多。
该方法的基本思想是：各个个体被选中的概率与其适应度函数值大小成正比。
设群体大小为n ，个体i 的适应度为i F ，则个体i 被选
中遗传到下一代群体的概率为:
1/n i i i i P F F ==∑
计算群体中所有个体的适应度函数值(需要解码);
利用比例选择算子的公式，计算每个个体被选中遗传到下一代群体的概率；
采用模拟赌盘操作(即生成0到1之间的随机数与每个个体遗传到下一代群体的概率进行匹配)来确定各个个体是否遗传到下一代群体中。
它是先按个体的选择概率产生一个轮盘，轮盘每个区的角度与个体的选择概率成比例，然后产生一个随机数，它落入轮盘的哪个区域就选择相应的个体交叉。
显然，选择概率大的个体被选中的可能性大，获得交叉的机会就大。
4. 交叉操作
交叉操作是对两个染色体操作，组合两者的特性产生新的后代。
两个父代在交叉时，可能会产生非法的后代。
在该调度问题中，如果用单点交叉算子，就可能出现如[2312]的非法解，在该染色体中，
有两个重复的基因2，它们都表示产品
J，但丢失了产品4J。
因此，
2
采用部分映射交叉算子。
在染色体中随机产生两个交叉点，交换两个父染色体交叉点中间的部分，如果生成的子染色体中若有非法的重复部分，用交叉部分对应的基因替换交叉点两侧的基因。
在该调度问题中假设有两个染色体父代1和父代2，其部分映射交叉操作如下:
后代1'和后代2'，是中间染色体交叉操作中的过渡状态。
5. 变异操作
变异操作是一种基本运算，在染色体上自发地产生随机的变化。
该调度问题中的一个染色体为[4123]，对其进行变异，任意交换第1个基因与第3个基因的位置。
变异前：[4123]
变异后：[2143]
6.参数确定
种群规模m=50；
遗传运算的终止进化代数T=100；
P=;
交叉概率0.85
c
P=;
变异概率0.01
m
利用遗传算法得到的产品调度顺序为:J2→J4→J3→J1。
即先生产产品J2，然后生产产品J4和产品J3，最后生产产品J1，总的完工时间为40。
遗传算法调度得到的产品的调度顺序如下图3。
图3
从本实例仿真可以看出，利用遗传算法可以有效地解决流水线车间调度问题。
