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

1、-. z流水车间调度问题的研究机械工程学院 2111302120 周杭超如今，为了满足客户多样化与个性化的需求，多品种、小批量生产己经为一种重要的生产方式。与过去大批量、单一的生产方式相比，多品种、小批量生产可以快速响应市场，满足不同客户的不同需求，因此，受到越来越多的企业管理者的重视。特别是以流水线生产为主要作业方式的企业，企业管理者致力于研究如何使得生产均衡化，以实现生产批次的最小化，这样可以在不同批次生产不同品种的产品。在这种环境下，对于不同批次的产品生产进展合理调度排序就显得十分重要。在传统的生产方式中，企业生产者总是力求通过增加批量来减小设备的转换次数，因此在生产不同种类的产品时，以

2、产品的顺序逐次生产或用多条生产线同时生产。这样，必然会一次大批量生产同一产品，很容易造成库存的积压。在实际生产中如果需要生产A, B, C, D四种产品各100件，各种产品的节拍都是1分钟，如果按照传统的做法，先生产出100件A产品，其次是B，然后是C，最后生产产品D。在这种情况下，这四种产品的总循环时间是400分钟。然而，假设客户要求的循环时间为200分钟(四种产品的需求量为50件)，则在200分钟的时间就只能生产出产品A和产品B，因而不能满足客户需求，同时还会过量生产产品A和B，造成库存积压的浪费。这种生产就是非均衡的，如图1所示。比拟均衡的生产方式(图2 )是:在一条流水线上同时将四种产

3、品混在一起生产，并且确定每种品种一次生产的批量。当然，如果在混合生产时不需要对设备进展转换，则单件流的生产方式是最好的。然而，在实际生产A, B, C， D四种不同产品时，往往需要对流水线上的*些设备进展工装转换。单件流的生产方式在此难以实现，需要根据换装时间来确定每种产品一次生产的批量。同时，由于现实生产中不同产品在流水线上各台机器的加工时间很难一样，因此，流水线的瓶颈会随着产品组合的不同而发生变化。当同一流水线加工多产品，并且每种产品在各道工序(各台机器)的加工时间差异较大时，瓶颈就会在各道工序中发生变化，如何对各种产品的投产顺序进展优化以协调这些变化的瓶颈是生产管理中一个很重要的问题。

4、图1 图2因而对流水线调度问题的研究正是迎合这种多品种、小批量生产方式的需要，我们要讨论得是如何对流水线上生产的不同产品的调度顺序进展优要化。流水车间调度问题一般可以描述为n 个工件要在 m台机器上加工，每个工件需要经过 m 道工序，每道工序要求不同的机器，n个工件在 m台机器上的加工顺序一样。工件在机器上的加工时间是给定的，设为。问题的目标是确定个工件在每台机器上的最优加工顺序，使最大流程时间到达最小。对该问题常常作如下假设:(1)每个工件在机器上的加工顺序是给定的;(2)每台机器同时只能加工一个工件;(3)一个工件不能同时在不同机器上加工;(4)工序不能预定;(5)工序的准备时间与顺序无关

5、，且包含在加工时间中;(6)工件在每台机器上的加工顺序一样，且是确定的。问题的数学模型：。本文中以4个工件、4台机器流水线调度为例，该流水线由四台机器M1 ，M2 ，M3 ，M4组成，加工顺序分别是M1M2M3M4，各工件在各机器上的加工时间如下表所示。工件J185410J21547J39438J439151.问题的编码方式与初始群体的生成在流水车间调度问题中，最自然的编码方式是用染色体表示工件的顺序：对于有四个工件的生产调度，第个染色体 ，表示工件的加工顺序为：。 遗传算法必须对种群进展操作，所以必须准备一个由假设干解组成的初始种群。适宜的群体规模对遗传算法的收敛具有重要意义。群体太小难以求

6、得满意的结果，群体太大则计算复杂。根据经历，群体规模一般取10160。2.确定问题的适应度函数遗传算法对一个个体(解)的好坏用适应度函数值来评价，适应度函数值越大，解的质量越好。适应度函数是遗传算法进化过程的驱动力，也是进展自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。在该调度问题中将最大流程时间的倒数作为适应度函数。令表示k个染色体的最大流程时间，则适应度值为：3.选择选择操作也称复制操作，是从当前群体中按照一定概率选出优良的个体，使它们有时机作为父代繁殖下一代子。判断个体优良与否的准则是各个个体的适应度值。显然这一操作借用了达尔文适者生存的进化原则，即个体适应度越高，其被选择的

7、时机就越多。该方法的根本思想是：各个个体被选中的概率与其适应度函数值大小成正比。设群体大小为n，个体i的适应度为，则个体i被选中遗传到下一代群体的概率为:计算群体中所有个体的适应度函数值(需要解码);利用比例选择算子的公式，计算每个个体被选中遗传到下一代群体的概率；采用模拟赌盘操作(即生成0到1之间的随机数与每个个体遗传到下一代群体的概率进展匹配)来确定各个个体是否遗传到下一代群体中。它是先按个体的选择概率产生一个轮盘，轮盘每个区的角度与个体的选择概率成比例，然后产生一个随机数，它落入轮盘的哪个区域就选择相应的个体穿插。显然，选择概率大的个体被选中的可能性大，获得穿插的时机就大。4. 穿插操作

8、穿插操作是对两个染色体操作，组合两者的特性产生新的后代。 两个父代在穿插时，可能会产生非法的后代。在该调度问题中，如果用单点穿插算子，就可能出现如2312的非法解，在该染色体中，有两个重复的基因2，它们都表示产品，但丧失了产品。因此，采用局部映射穿插算子。 在染色体中随机产生两个穿插点，交换两个父染色体穿插点中间的局部，如果生成的子染色体中假设有非法的重复局部，用穿插局部对应的基因替换穿插点两侧的基因。在该调度问题中假设有两个染色体父代1和父代2，其局部映射穿插操作如下:后代1和后代2，是中间染色体穿插操作中的过渡状态。5. 变异操作变异操作是一种根本运算，在染色体上自发地产生随机的变化。该调度问题中的一个染色体为4123，对其进展变异，任意交换第1个基因与第3个基因的位置。变异前：4123变异后：21436.参数确定种群规模m=50；遗传运算的终止进化代数T=100；穿插概率;变异