flow-shop

flow-shop（精选3篇）

flow-shop 篇1

0 引言

生产车间调度问题,就是根据需求合理分配产品制造资源,从而达到合理利用产品制造资源、提高企业经济效益的目的。所以对该问题的研究具有很高的理论价值和实际意义。以某纺织企业的纺纱车间为背景,研究如何优化生产调度问题。

1 纺纱工艺流程

南通某纺织有限公司是典型的小批量多品种基于订单的生产模式。该企业主要以纺纱为主,同时小规模制线。纺纱车间分为环锭纺与气流纺两种类型,而环锭纺又分为精梳与普梳两类工艺要求。根据类型及工艺要求的不同,该纺织企业纺纱车间的工艺流程大致可概括为以下3类:

(1)环锭纺(精梳):清花—梳棉—预并条—条并卷—精梳—头道并条—二道并条—粗纱—细纱—络筒。

(2)环锭纺(普梳):清花—梳棉—头道并条—二道并条—粗纱—细纱—络筒。

(3)气流纺:清花—梳棉—头道并条—二道并条—气流纺纱。

企业车间调度员根据各车间生产工艺流程进行正确、合理的生产安排调度。选取第一种工艺流程,即环锭纺(精梳)作为调度问题的依据。

2 Flow-Shop调度模型的建立

纺织企业一般以订单为驱动,而每个生产流程都有多台设备,且每个设定的流程路线基本都相同,这与Flow-Shop调度问题非常类同。

Flow-Shop调度问题通常是针对如何配置资源而实现目标优化而展开的,其任务就是确定工件的加工顺序,也称为排序问题。

Flow-Shop调度问题研究的是n个工件在m台机器上的加工过程。每个工件在m台机器上加工的顺序相同,且每道工序要求使用不同的机器。问题的目标是确定n个工件在每台机器上的最优加工顺序,使调度方案的评价指标最优化。调度方案的评价指标主要有总流程时间、平均流程时间、最大交货误期、平均交货误期、交货误期的工件数、平均制品库存量和费用指标等。选取总流程时间作为性能指标。此外,为简化问题,认为Flow-Shop调度问题为确定型问题,即加工时间是已知的确定量。

纺织企业接到订单后,客户提出的是对具体产品的需求,而Flow-Shop调度需要确认的是在生产加工过程中需要的原料的批量数。销售员将订单生成生产销售协调通知单,而调度员则根据生产销售协调通知单生成具体的生产调度通知单,最后车间调度员根据生产调度通知单最终生成改纺通知单,以得出各订单所需求的原料数量及相应要求,并分为具体的批量进行生产。

该纺织企业纺纱车间环锭纺(精梳)的Flow-Shop调度问题可以描述为:根据工艺要求,n批原料(如棉花、涤纶、黏胶、莫代尔等)首先经过圆盘机进行清花工序,完成混棉的目的;然后依次经过梳棉、预并条、条并卷、精梳、头道并条、二道并条、粗纱、细纱、络筒各工序,完成在m台纺纱设备上生产加工的过程,最终生产出成纱。每道工序对应一台相应的设备(如粗纱工序对应粗纱机)。除清花工序外,其他各道工序加工后的产品均为半制品,而每道工序后的半制品相对下道工序而言都是下道工序的“原料”。每一批原料及其之后相应的各半制品{J1,J2,...,Jn}在m台设备{M1,M2,...,Mm}上加工的顺序相同,且每台设备上各批原料及其半制品的加工顺序亦相同。每道工序的加工时间给定,且是连续无间断的加工过程。

令Cmax为n批原料的最大完工时间;T(Jj,k)为原料或半制品Jj在设备k上的加工时间;{J1,J2,...,Jn}表示原料的调度;C(Jj,k)表示原料或半制品Jj在设备k上的完工时间。则对于有m台纺纱设备、n批原料的纺纱车间Flow-Shop调度模型的完工时间的计算可表示如下:

则最大完工时间为:

纺织企业纺纱车间Flow-Shop调度问题的目标函数与上式最小化最大完工时间相对应。

3 调度问题的求解

3.1 算法选择

车间调度问题的求解方法主要有数学规划法、规则调度法、离散仿真法及智能优化算法4种。而随着车间调度问题研究的不断深入及实际问题的不断复杂化,对该问题的求解算法主要集中于智能化优化算法。这类算法主要包括遗传算法、模拟退火算法及禁忌搜索算法等。智能优化算法自身求解过程的快速性,使其在车间调度问题的研究中占据了主导地位。

研究证明,微粒群算法用于解决车间调度问题要比经典算法具有更好的优势和可行性,且能够取得更好的调度效果。

3.2 DPSO算法求解Flow-Shop调度问题

Flow-shop调度问题是一类离散空间组合优化问题,调度解属于离散的整数空间域。因此,PSO求解Flow-shop调度问题时不能用粒子位置直接表示调度问题的解。目前,使用PSO求解离散组合优化问题主要有:基于离散空间的PSO算法和基于连续空间的PSO算法。采用离散PSO(DPSO)算法求解纺织企业纺纱车间Flow-shop调度问题。

DPSO算法的微粒速度-位置更新公式为:

其中,Xpbest为微粒自身最佳位置,Xgbest为群体最佳位置。

在DPSO算法中,粒子是随机产生,粒子的排列顺序相同的概率很小,保证了解的可行性。所以,将每个粒子的位置映射为一批原料的排序,粒子的位置不断更新,也就是调度解空间不断变化,这样就可以通过粒子的迭代寻求到调度问题的最优解。

DPSO算法求解纺织企业纺纱车间Flow-Shop调度问题的流程图如图1所示,其中psize为粒子总数,n即为原料的批次数。

4 仿真实验及结果

最后在MATLAB软件上完成DPSO算法求解Flow-shop调度问题的程序设计及仿真。选取9种测试规模问题(从20×5至100×20),对每个测试规模问题均独立运行20次,取平均值。加工时间为确定量,各规模问题加工时间矩阵根据Taillard标准测试集中Flow-Shop问题的描述处理得到。

表1为DPSO算法对各规模问题仿真结果,由结果可以看出,DPSO算法很好地解决了纺织企业纺纱车间Flow-Shop调度问题,证明了DPSO算法求解该调度问题的有效性。

摘要：以某纺织企业纺纱车间为背景,针对Flow-Shop调度问题,以“最大完工时间最小化”为调度性能指标建立数学模型,应用微粒群算法(PSO)对该问题进行求解,通过仿真实现验证了其有效性。

关键词：纺织企业,生产调度,Flow-Shop,微粒群算法

参考文献

[1]蒋南云,文尧奇,路致远,等.基于订单管理的纺纱企业生产调度研究[J].江苏纺织,2008,10

[2]张险峰.纺织企业车间生产调度方法和遗传算法的研究与实现[J].计算机技术与自动化,2009,(01)

[3]王凌,刘波.微粒群优化与调度算法[M].北京:清华大学出版社,2008

[4]E.TAILLARD.BENCHMARKS FOR BASIC SCHEDU-LING PROBLEMS.ORWP89/21,1989

flow-shop 篇2

制造企业的实际生产中,许多产品需要大批量生产,如汽车零部件、轴承等,其主要生产组织方式为流水生产。在流水生产中如何确定产品的生产顺序和节拍至关重要,此类问题可归结为流水车间排序问题。不合理的生产顺序会导致设备得不到有效利用,降低企业的生产效率。

流水车间排序问题是典型的NP-hard问题,至今没有可以精确求得最优解的多项式时间算法。随着计算机技术的发展,各种智能技术在作业排序问题的研究中得到了应用[1~4]。遗传算法具有不依赖问题的具体领域、搜索结果全局近优等特点,一直是研究的热点;但它是一种搜索算法,在寻优过程中,防止早熟、局部收敛非常重要。遗传操作中的交叉操作在遗传算法中起着关键作用,是产生新个体的主要方法[5]。为了提高其求解流水车间排序问题的寻优性能,许多学者在交叉算子方面做了研究,如在交叉操作中混合使用LOX和单点交叉两种交叉算子来改善遗传算法求解Flow-Shop问题的质量[6];利用四种新的交叉算子:SJOX、SBOX、SJ2OX和SB2OX,解决交叉操作中子代适应度值小于父代的问题[7]。本文针对Flow-Shop问题,通过分析典型单点交叉算子的优缺点,根据其进化缓慢的缺陷,提出一种改进型单点交叉算子,以提高遗传算法的寻优性能。

1 Flow-Shop问题的数学描述

流水车间排序问题也常称为Flow-Shop问题,一般可以描述为:n个工件在m台机器上加工,每个工件需要经过m道工序,每道工序要求不同的机器。n个工件在m台机器上的加工顺序相同,工件在机器m上的加工时间是给定的。问题的目标是确定n个工件在每台机器上的最优加工顺序,使最大流程时间达到最小。

令Pij为工件i在机器j上的加工时间,Cij为工件i在机器j上的完工时间,不失一般性,假设各工件按机器1至m的顺序进行加工,令为所有工件的一个排序,以上定义和假设用数学模型表示为[8]:

式(1)为作业σn在机器m上的完工时间,表示以最大完工时间最小化为指标,即Makespan指标;式(2)表示作业σ1在机器1上的完工时间;式(3)表示作业σi在机器1上的完工时间;式(4)表示作业σ1的第j道工序必须在第j-1道工序完成后才能开始;式(5)表示作业σi-1在机器j上加工完成后和作业σi在机器j-1上加工完成后,才能在机器j上加工作业σi。

2 Flow-Shop问题的求解

2.1 遗传算法求解Flow-Shop的基本流程

求解流水车间排序的遗传算法基本操作流程如图1所示。

第一步,随机生成N个个体组成初始种群。其中,每个个体表示染色体的基因编码,对于流水车间排序问题,编码方式可采用基于工件的自然数编码。例如,对于六个工件的流水车间排序问题,假设工件的加工顺序是j2,j1,j5,j4,j3,j6可将其编码为:[2,1,5,4,3,6]。

第二步,计算个体的适应度。根据遗传算法目标函数的方向与适应度值变化方向相同的原则,本次采用的适应度函数为式(1)目标函数的倒数。

第三步,选择操作。本文采用最常用的轮盘赌选择算子,用正比于个体适应度值的概率来选择个体,这种选择思想与生物的自然选择相似。

第四步,交叉操作。交叉操作是产生新个体的主要方法,在遗传算法中起着关键作用。本文将在下一节重点对其进行展开分析。

第五步,变异操作。常用的变异方法有交换变异、倒位变异、插入变异等。本文采用交换变异,即交换染色体中两个基因座的基因值。例如一条染色体为[2,1,5,4,3,6],随机选取两位置2和4,则交换变异的结果是[2,4,5,1,3,6]。

2.2 交叉算子

单点交叉操作与生物的交配重组类似,是基本遗传算法中最常用的交叉算子之一。基于工件编码的单点交叉操作为:1)随机产生一交叉点;2)把两父代交叉点前的基因复制给子代1和子代2;3)从父代2(或1)中找出子代1(或2)中缺少的基因,并将其按顺序复制给两子代交叉点后的位置。如图2所示。

从单点交叉的操作可以看出,单点交叉使子代继承了父代交叉点前的基因,交叉操作只改变了交叉点后的部分基因,而交叉点前的基因一直未发生改变。这样,交叉点前的基因进化只能依靠变异操作进行,而变异的概率是很低的,显然,进化对初始种群依赖较大,进化速度缓慢。

为了提高寻优质量,本文提出了一种改进型单点交叉算子。取上述父代1、父代2为例,其操作为:首先随机产生一交叉点;然后产生一个随机数(rand),确定交叉段的保留部分,具体如下。

1)当rand小于等于0.5时,把两父代交叉点后的基因复制给两子代,然后从父代2(或1)中找出子代1(或2)中缺失的基因,并将其按顺序复制给两子代交叉点前的位置。此时得到的子代如图3所示。

2)当rand大于0.5时,把两父代交叉点前的基因复制给子代,然后从父代2(或1)中找出子代1(或2)中缺失的基因,并将其按顺序复制给两子代交叉点后的位置。此时得到的子代同图2。

从以上操作可知,改进型单点交叉使父代交叉点前后的基因以等概率的方式得以保留或改变。与典型的单点交叉相比,改进型单点交叉有机会改变染色体中的所有基因,增加了染色体基因的改变范围,提高了基因重组的程度,这样就扩大了解空间的搜索范围,有利于提高进化速度和优解的质量。

3 实验分析

本实验用标准测试案例Car05[9](10×6,即10个工件,6台机器)作为测试数据,其标准最优解为7720。针对Flow-Shop问题,对上述两种交叉算子进行比较分析。在计算实验时,使用相同的初始种群,种群个数60,交叉率0.8,变异率0.05,进化代数300;分别独立运行50次。

图4、图5是这两种交叉算子具有一定代表性的进化历程图。

从图4、图5中的进化历程图可知,两种交叉算子的平均适应度曲线都有爬升趋势,表示种群整体都有往收敛方向搜索的趋势。

图5中,改进型单点交叉进化历程前期平均适应度曲线上升速度比单点交叉快;从平均适应度曲线可以看出,改进型单点交叉算子种群整体进化历程明显优于单点交叉算子。

得到的最好染色体是[5 4 2 1 3 8 6 10 9 7],最优解为7720,图6是相应的的甘特图,图中的数字表示工件。

表1中的数据为50次计算的统计结果。

由表中的数据可知,改进型单点交叉算子的全局收敛能力比单点交叉算子强,全局收敛次数是单点交叉算子的近2倍;且首次出现最优解的平均代数小,平均在130余代就能找到最优解。实验结果显示,改进型单点交叉算子性能良好。

本实验对大规模问题也进行了测试,种群整体进化趋势与上述案例类似,改进型单点交叉算子无论是求解质量还是寻优速度都优于单点交叉算子。限于篇幅,不再具体展开。

4 结论

本文提出一种改进型单点交叉算子,通过改变染色体基因的变化范围,扩大解空间的搜索范围,提高了进化速度。标准测试案例表明,改进型单点交叉算子在求解流水车间排序问题时的性能优于典型的单点交叉算子。

参考文献

[1]赵良辉,邓飞其.用于作业车间调度的模拟退火算法[J].制造业自动化,2006,28(3):10-13.

[2]王娟,王建.自适应蚁群算法在流水车间调度的应用[J].计算机应用与软件,2008,25(11):117-119.

[3]伊华伟,张秋余.求解置换Flow_shop调度问题的改进遗传算法[J].计算机工程与应用,2007,43(22):41-43.

[4]Bassem Jarboui,Mansour Eddaly,Patrick Siarry.A hybridgenetic algorithm for solving no-wait flowshop[J].Int JAdv Manuf Technol,2010,11.

[5]周明.遗传算法原理及应用[M].北京:国防工业出版社,1996.

[6]涂雪平,施灿涛,李铁克.求解置换流水车间调度问题的改进遗传算法[J].计算机工程与应用,2009,45(36):50-53.

[7]Rubén Ruiz,Concepción Maroto,Javier Alcaraz.Two newrobust genetic algorithms for the flow-shop schedulingproblem[J].OMEGA,2006,34:461-476.

[8]武维,管晓宏,卫军胡.Flow shop问题的嵌套分区优化调方法[J].控制理论与应用,2009,26(3):233-237.

flow-shop 篇3

Flow-shop生产调度问题是对流水线生产调度问题的模拟,因而Flow-shop调度的研究对于实际流水线调度问题的解决具有重要的借鉴与指导意义。现阶段对Flowshop问题的研究大致可分为三类:第一种是用新算法对标准Flow-shop问题进行求解[1,2];第二种是提出了一种特殊的Flow-shop调度模型,并对模型进行求解[3,4];第三种是对原有算法进行改进或提出一种新颖算法求解相应的Flow-shop调度模型[5,6]。本文对不确定加工时间环境下的Flow-shop调度问题进行了研究,提出了一种改进遗传算法,最后通过仿真比较分析了改进遗传算法在模型求解上的有效性。

1 六点模糊数Flow-Shop问题描述

1.1 六点模糊数基础

论域U上的模糊子集构成了模糊集ξ(U),即

由于模糊数隶属度函数难以精确定义的特点,本文采用Romme Lfanger[7]提出的隶属度函数获取方法,如下:

基于上述描述,六点模糊数可以表示为以下形式:

1.2 六点模糊数运算法则

1.3 Flow-Shop鲁棒调度问题

现有n个工件以相同的顺序依次经过机器集Ω(M)={M1,M2,…Mj…Mm}中的设备;工件同一时刻只能被一台设备加工;设备某一时刻只能加工一个工件;工件在机器之间的搬运时间可以忽略;机器加工是一种无延迟加工;加工过程不可中断;本文采用最大完工时间跨度和最大完工时间的组合目标作为鲁棒调度的鲁棒性测度RM。

目标函数:

决策变量:

zij为工件加工顺序决策变量。

2 算法设计

遗传算法(Genetic Algorithm,GA)是一种随机优化算法,算法依靠选择、交叉以及变异等操作完成种群的进化。遗传算法的交叉操作是通过对被选择的个体彼此间遵循一定的规则完成基因的交换,其子代个体的优劣充满随机性。本文采用改进遗传算法(Improved Genetic Algorithm,IGA),采用单染色体遍历方式替代染色体间的交叉操作,以增强子代个体的确定性。

2.1 编码

本文采用实数编码规则,如图1所示,数字表示工件的序号,数字编码顺序表示工件的加工顺序。

2.2 遍历操作

遍历操作具体步骤如下:

步骤一:确定当前染色体遍历的基因个数N,采用线性递减方式,N=(1-t/T)×M/2+1。

式中:t为当前迭代次数;T为最大迭代次数;M为工序加工顺序编码基因个数。

步骤二:依据遍历基因数,随机生成遍历基因位置,依次从左至右完成基因遍历,如在染色体编码中随机选择(1,4)号基因作为遍历基因遍位置,则首先从1基因位置开始遍历,保留1左边基因顺序不变,将1基因右侧基因依次与1对调,计算对调后的染色体的适应度值,保留最优染色体,若1号基因完成遍历后最优个体恰是与4号基因完成对调后的染色体,则4号基因不在进行遍历操作,反之,4号基因继续上述操作直至完成遍历。

2.3 变异操作

本文采用随机法在编码处确定两点基因变异位置,如(5,7)号基因,截取包括(5,7)号基因在内的基因片段,参照图1所示编码,此处基因片段为(5,6,1,4,7),采用倒序方式将基因片段插入到原基因中,最终变异后的基因为(3,7,4,1,6,5,9,2,8)。

2.4 改进遗传算法基本步骤

步骤一:令ite=0,随机初始化种群大小为N的种群Pop(0),选择率Pc、变异率Pm,概率P,相似度阈值Thr,最大迭代次数Ite。

步骤二:计算种群Pop(ite)中各个体的适应度值(fitness value)。

步骤三:判断算法终止条件是否满足。满足,则输出适应度值最高个体,否则,进入步骤三。

步骤四:采用轮盘赌法从种群群众选择出Pc×N个个体,复制进入选择临时种群Tem Pop中。

步骤五:对Tem Pop各个体赋予随机数ε,ε∈[0,1]。

步骤六:若Pm≥ε,对该个体进行变异操作;否则,对个体进行遍历操作。将完成操作的个体放入下代种群Pop(ite+1)中。

步骤七:从Pop(ite)选取适应度值高的个体补足种群大小。在选取个体时,若P≥θ,θ∈[0,1],则计算个体与Pop(ite+1)中个体的相似度Sim,若个体相似度Sim≥Thr,对个体进行重新排序后放入Pop(ite+1);反之,则直接放入Pop(ite+1)。

步骤八:ite=ite+1,返回步骤二。

3 实例验证

为了测试改进遗传算法(IGA)对求解Flow-shop调度问题的有效性,本文分别将IGA和GA用于Flow-shop调度问题的求解,在求解的过程中采用多个问题多次求解的方式,即针对不同的加工工件规模进行算法求解。在[1,10]之间随机生成6个数据并依照大小依次排序,从而构成工件模糊加工时间;Pc=0.2,Pm=0.1,N=50,P=0.8,Ite分别为500、1000、2000次。针对不同的加工规模以及不同的迭代次数进行试验比较,具体仿真数据如表1所示,其中Size表示加工规模,BV表示搜索最优值,RT表示算法搜索耗时。

对上述数据进行进一步分析可知,加工规模为10时,在500、1000以及2000次迭代试验下IGA算法相较于遗传算法最优值分别提升11%、11%、6%,搜索耗时分别降低了9%、8%、14%;在工件规模为20时,精度提升25%、25%、23%,耗时降低7%、12%、12%;工件规模为20时,精度提升18%、18%、18%,耗时降低6%、8%、9%;工件规模为25时,精度提升14%、9%、12%,耗时降低5%、7%、3%;工件规模为30时,精度提升17%、18%、20%,耗时降低15%、10%、9%。由此可知IGA在求解Flow-shop调度问题上是明显优于传统遗传算法的。

4 结语

本文的研究内容主要可以分为以下几点:

1)利用六点模糊数方式描述了加工时间不确定的Flowshop调度车间问题;2)构建了Flow-shop调度模型,并利用改进遗传算法对模型进行求解。

摘要：对不确定加工时间环境下的Flow-shop调度问题进行了研究,利用六点模糊数对不确定加工时间进行描述,以最大完工时间和最大完工时间跨度的权重和为鲁棒性测度构建模糊加工时间Flow-shop调度模型。提出了模型求解的改进遗传算法,算法采用单染色体遍历操作代替染色体交叉操作,用以增强种子代繁衍的确定性,最后仿真分析验证了算法的有效性。

关键词：Flow-shop调度,六点模糊数,改进遗传算法

参考文献

[1]陈雄,杨凤霞,吴启迪.Flow-shop调度问题的自适应模拟退火算法[J].控制理论与应用,2003,20(3):445-448.

[2]周宏根,戚雪峰,景旭文,等.基于遗传算法的作业车间调度研究与应用[J].现代制造工程,2006(8):5-8.

[3]锦钿,刘建军,陈庆新,等.两机flow-shop类型模具热处理车间批调度算法[J].计算机集成制造系统,2014,20(7):1665-1674.

[4]王莉,杜广宇,刘洪,等.带有交货期窗口模糊加工时间的Flow-shop调度问题[J].2005,14(6):532-536.

[5]李俊青,潘全科,王法涛.求解混合流水线调度问题的离散人工蜂群算法[J].运筹与管理,2015,24(1):157-163.

[6]桑红燕,潘全科.求解流水车间批量流集成调度的离散入侵杂草优化算法[J].控制理论与应用,2015,32(2):246-250.

[7]ROMMELFANGER H.Fulpal:An Interactive Method for Solving(multiobjective)Fuzzy Linear Programming Problem[M]//Slowinski R,Teghem J(eds.),Stochastic Versus Fuzzy Approaches to Multiobjective Mathematical Programming Under Uncertainty.Dordrecht:Kluwer,1990:279-299.