流水车间调度问题的研究

《流水车间调度问题的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

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四种不同产品时，往往需要对流水线上的某些设备进行工装转换。单件流的生产方式在此难以实现，需要根据挽装时间来确定每种产品一次生产的批量。同时，由于现实生产中不同产品在流水线上各台机器的加工吋间很难相同，因此，流水线的瓶颈会随着产品组合的不同而发生变化。当同一流水线加工多产品，并且每种产品在各道工序（各台机器）的加工时间差异较大时，瓶颈就会在各道工序中发生变化，如何对各种产品的投产顺序进行优化以协调这些变化的瓶颈是生产管理中一个很重要的问题。oooo口口oA□oAHo非均衡的生产方式均衡化的生产

4、方式图1图2因而对流水线调度问题的研究正是迎合这种多品种、小批量生产方式的需要，我们要讨论得是如何对流水线上生产的不同产品的调度顺序进行优要化。流水车间调度问题一般可以描述为n个工件要在m台机器上加工，每个工件需要经过m道工序，每道工序要求不同的机器，n个工件在m台机器上的加工顺序相同。工件在机器上的加工时间是给定的，设为~（/=1，…,=…，m）。问题的目标是确定个工件在每台机器上的最优加工顺序，使最人流程时问达到最小。对该fid题常常作如下假设：(1)每个工件在机器上的加工顺序是给定的；(2)每台机器同吋只能加工一个工件；⑶一个工件不能同时在不同机器上加工；(4)工序不能预定；(5)工序

5、的准备时间与顺序无关，且包含在加工时间屮；(4)工件在每台机器上的加工顺序相同，且是确定的。问题的数学模型：c(乂，幻：工件^在机器上的加工完工时间…，:工件的调度n个工件、m台机器的流水车问调度问题的完工时问：c(j'，k)=c(j”k-l)+thk,=2，."，mc(7；.,1)=c(7；_1,1)+Z7.1,i=2,…，nc{ji,k)=max{

6、是吣->M2-M3-M4,各工件在各机器上的加工吋间如下表所示。工件m2Jl85410J21547J39438J439151.问题的编码方式与初始群体的生成在流水车间调度问题中，最自然的编码方式是用染色体表示工件的顺序：对于有四个工件的生产调度，第☆个染色体V,=[1,2,3,4],表示工件的加工顺序为:7pJ2/3,74o遗传算法必须对种群进行操作，所以必须准备一个由若干解组成的初始种群。合适的群体规模对遗传算法的收敛具有重要意义。群体太小难以求得满意的结果，群体太大则计算复杂。根据经验，群体规模一般取10〜160。2.确定问题的适应度函数遗传算法对一个个体（解）的好坏用适应度函数值来评价

7、，适应度函数伉越大，解的质量越好。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。在该调度问题中将最大流程吋间的倒数作为适应度函数。令d表示k个染色体的最大流程卩寸间，那么适应度值为：evalvk}=11.选择选择操作也称复制操作，是从当前群体中按照一定概率选出优良的个体，使它们宥机会作为父代繁殖下一代子孙。判断个体优良与否的准则是各个个体的适应度值。