基于遗传算法的合同计划编制模型

基于遗传算法的合同计划编制模型

1日、日合同计划的管理今天，钢铁工业的主要特点是，它不仅要在不同的条件下确保生产的连续性，还要满足对产品质量和按时交付的要求。在实现这一目标的过程中，合同计划是各生产过程中的一个重要组成部分，它决定了生产能否在不同条件下成功完成。钢厂生产计划主要包括年计划、月计划、合同计划和日生产计划.年计划主要进行全厂范围内的能力平衡,作为资源计划的依据,用于指导定货;月计划对设备的生产能力进行核定、预报;合同计划根据客户的定货要求和设备的生产能力,安排合同的生产,提出材料申请,从而指导日生产计划的编制;日生产计划根据合同计划,考虑各机组的生产工艺规程,对生产进行具体的调度.在市场经济环境下,合同计划是体现以销定产的生产计划,它的主要任务是根据合同的交货期、各生产工序上机组的生产能力等来安排一个合同的生产周期,即确定每道工序的生产时间.在合同计划编制中,要考虑各工序的生产能力和需要生产的合同(时间、数量、质量)的要求,保证整条生产线的顺利生产.国内外学者对钢厂合同计划的编制进行了许多研究,C.N.Redwine和D.A.Wismer应用混合整数规划模型来解决轧钢厂合同计划问题,目标为最小化合同总拖期,引进了拖期惩罚表,但文中未考虑过早完成合同而增加的成本,惩罚表只能表示合同重要性,而不能完全决定合同的优先权,因此不一定获得最佳经济效益.滕学等人对钢管厂热轧机组的生产过程进行了分析,建立了合同分配模型,并进行了优化分析和实验,优于人工作业.但未给出成熟的模型和算法,最小时间单位选择为月是偏大的.本文通过对钢厂生产过程的分析,提出了合同计划的一种数学模型和算法,研究工作包括三个部分:1)以半旬为最小时间单位,最小化全部合同的提前和拖期总惩罚为目标,建立了合同计划编制的整数规划模型;2)提出基于可重复自然数编码和三变异算子的遗传算法对模型求解;3)通过实验验证模型和算法的有效性.2合同计划的数学模型方法2.1合同计划和能力合同计划的编制可以概述如下:假设有N个合同、M道工序,每个合同的重量、交货期及其生产路径(通过的工序和在每道工序可使用的机器(不唯一))已知,每个合同通过的工序相同,每台机器的能力一定,合同计划是在满足能力约束和前序关系的前提下,安排每个合同在每道工序通过的机器和通过的时间,使所有合同的提前和拖期总惩罚最小.(每个合同必须通过所有工序,在每一工序必须且仅能在一台机器上加工,且同时最多只能在一台机器上生产,一台机器同时最多只能生产一个合同.)2.2合同提前、拖期总惩罚的模型如果对每种产品都只考虑大工序,其加工路径确定,这是一般的flowshop(FS)问题,问题相对简单;如果考虑某些品种在某工序有多于一台的并行机可供选择时,则是一类flexible(柔性)flowshop(FFS)问题,问题变得复杂得多.1973年,Salvador基于石油化工的工业背景首次定义了FFS问题,它是一般FS问题推广.本文的合同计划问题是一类FFS问题,不同的是本文的合同计划只对合同安排其加工的时间段,而不对该时间段内的合同排序.本模型中合同的交货期和生产时间段以半旬为单位,目标函数为所有合同的提前和拖期总惩罚最小.对于各工序,假设1)每道工序中每台机器的每半旬总能力己知;2)每道工序的各台机器相同,假设某合同,对于不同机器,其虚拟生产量不同,从而表示机器的不同性;3)各合同在各工序的通过时间(从进入一工序到本工序完成的时间)小于一个半旬,同一合同的多道工序可在同一半旬中完成;4)不单独考虑中间库存.为了便于表示,建立以下数学符号:N——合同总数;M——工序数;T——计划周期;[di-ui,di+vi]——交货期窗口(以半旬为单位)(已知);tij——第i个合同在第j道工序的开工半旬;ei——合同i的实际合同量(已知);eijk——合同i在工序j的第k机器上的虚拟生产量(已知);ci——合同i的完工半旬,即最后一道工序的通过时间(半旬);Ejkt——工序j的机器k在t半旬的总能力(已知).xtjkt={1‚合同i在半旬t内在⌶序j的第k机器上加⌶‚0‚否则‚xtjkt={1‚合同i在半旬t内在⌶序j的第k机器上加⌶‚0‚否则‚其中:xijkt为决策变量,i表示合同号(i=1,…,N),j表示工序号(j=1,…,M),k表示j工序中的机器号(k=1,…,M),t表示时间段(t=1,…,T).建立数学模型如下:其中,αi是合同i的提前惩罚系数,βi是合同i的拖期惩罚系数.目标(1)是最小化所有合同的提前—拖期总惩罚值;约束(2)保证每个合同必须通过每一工序,在每一工序必须且仅能在一台机器上加工;约束(3)保证每半旬某机器所加工合同的合同量总和不能超过此机器的总加工能力(能力约束);约束(4)表示合同i在工序j的开工时间(半旬)不小于在工序j-1的开工时间;(5)表示决策变量的取值范围.3合同计划算法algorithmoffer代理3.1遗传算法使用的原因已经证明,FFS是NP-难问题.从本文模型可以看出,该合同计划模型是一个非线性0-1整数规划模型,由于变量维数比较多,目标函数的非线性增加了计算的复杂性,用精确算法在可行时间内难以求解.遗传算法已经广泛用于TSP,flow-shop等各种组合优化问题虽然遗传算法不能使搜索空间减小,但由于群体搜索的并行性使它能在较短的时间内搜索较大的空间,所以本文决定使用遗传算法.1工序j的机器k的通过段本文采用可重复自然数编码,设计染色体的基因aijk:A={aijk}‚A={aijk}‚这里,i=1,…,N,j=1,…,M,k=1,…,Mj,aijk表示合同i在工序j的机器k的通过时间段.其中,我们称{ai11,ai12,…,ai1M1,…,aiM2,…,aiMMM}为大段,称大段中的AiMj{aij1,aij2,…,aijMj}为小段,每一小段内只有一个基因不为0(基因为0表示此合同不在此机器上加工),这种编码方式保证了约束(2)的可行性.不为0基因的数值取一时间值,同一个大段内其取值范围为1到(T+td)的自然数(详见2)),且各小段之间必须满足约束(4);不同大段之间其数值可以重复.完工半旬ci就是相应第i大段的第M小段中不为0的值.2s12,a1mm—)初始种群.根据上述染色体编码的要求,采用随机的方式产生初始种群L个染色体.①由于产生一个染色体中的每个大段的方法相同,这里先产生一个大段{a111,a112,…,a11M1,…,a1M1,a1M2,a1MM}.首先,产生一个从1到M1的随机整数k11,作为不为0的元素号,再产生一个从1到T+td的随机整数,作为此元素a11k11的值,这样就产生了第一个小段;然后,产生一个从1到M2的随机整数k12,作为不为0的元素号,再产生一个从a11k11到T+td的随机整数,作为此元素a12k12的值,于是第二个小段被产生;依次类推,直到产生一个大段;(这里T+td是为了考虑合同的拖期,td是一个辅助计算的整数)②重复①的方法再分别产生这个染色体中的其它大段,于是随机产生了一个染色体;③重复①和②的方法,再分别产生L-1个染色体.3离idl的复制设对于种群中的第l个染色体有目标函数:Fl=∑i=1Nei(aimax{0,di−ui−ci}+βimax{0,ci−di−vi}).(6)Fl=∑i=1Νei(aimax{0,di-ui-ci}+βimax{0,ci-di-vi}).(6)为了限制不满足约束(3)的染色体在新一代种群中的比例,特设计用于复制的选择函数.定义每个染色体对约束(3)的可行距离IDl,用以表征染色体l的非可行程度:IDl=∑j=1M∑k=1Mj∑t=1Tmax{(∑i=1Nxijkteijk−Ejkt),0},(7)ΙDl=∑j=1Μ∑k=1Μj∑t=1Τmax{(∑i=1Νxijkteijk-Ejkt),0},(7)则用于复制的选择函数fl为:fl=C−Fl−γIDl‚(8)fl=C-Fl-γΙDl‚(8)其中,令C=maxl∈Q{Fl+γ∑j=1M∑k=1Mj∑t=1Tmax{(∑i=1Nxijkteijk−Ejkt),0}}+λ,(9)C=maxl∈Q{Fl+γ∑j=1Μ∑k=1Μj∑t=1Τmax{(∑i=1Νxijkteijk-Ejkt),0}}+λ,(9)Q={1,2,…,L}——种群集合,L——种群规模,γ——约束(3)的不可行惩罚系数,λ——适当的正整数.本算法采用滚轮盘的方式进行复制,复制的选择概率由如下(10)式获得.Pl=fl∑a=1Lfa‚l=1,2,⋯,L.(10)Ρl=fl∑a=1Lfa‚l=1,2,⋯,L.(10)可以看出,如果C值仅设为一个较大的常数,当各染色体目标值数值不太大,而它们的值相差很大时,得到的fl值就掩盖了各染色体的质量差别,因此,本算法在复制时,C值设置为(9)式产生的变量.4erpsc按交叉概率Pc,进行部分段交叉partsectioncrossover(PSC),即把两个染色体a和b在两个随机位置间的所有大段进行交换(相应小段只交换不为0的值,而原不为0的值的位置不变).由于交叉操作以大段为单位,在对应小段之间进行,因此染色体始终保证满足约束(2)和(4).5系统实验方法由于每个染色体中存在大段和小段,用普通的变异算子不能完成计算过程,为了保证搜索的全局性和满足约束(2)和(4)的可行性,采用三变异算子,构成一次变异操作.对染色体中不为0值的基因的位置及数值进行变换.在各变异中同时完成对变异后新染色体的择优,按如下适值函数:fl′=C′−Fl−γ∑j=1M∑k=1Mj∑t=1Tmax{(∑Xijkteijk−Ejkt),0}‚(11)fl′=C′-Fl-γ∑j=1Μ∑k=1Μj∑t=1Τmax{(∑Xijkteijk-Ejkt),0}‚(11)其中,C′为一足够大的常数.变异一:大段间变异.以大段为单位,根据变异概率Pm1,在染色体A′={B1,B2,…,BN}的大段Bi间进行2交换变异.具体步骤如下:①从种群的第1个染色体开始,a=1;②随机产生从0到1的小数,如果此小数不大于Pm1,则此染色体进行变异,转③;否则,转④;③从此染色体中的第一个大段开始,分别把每两个大段进行交换(相应小段只交换不为0的值,而原不为0的值的位置不变),比较每个交换所得到的新染色体的适应值,选择一个最好的交换.如果按此最好交换产生的新染色体的适应值大于原染色体,则用此新染色体代替原染色体;否则,不接受新染色体.然后,进行小段内变异(变异二),再进行大段内变异(变异三).然后转④.④如果a<L,则a=a+1,转②;否则,结束.变异二:小段内变异.设染色体A′={B1,B2,…,BN}=A.其中Bi={ai11,ai12,…,ai1M1,…,aiM1,aiM2,…,aiMMM}为第i大段.大段Bi={Si1,Si2,…,SiM},小段Sij={aij1,aij2,…,aijMj},根据变异概率Pm2,在某染色体的每个Sij内的基因间进行2交换变异.具体步骤如下:①对此染色体,设小段j=1;②随机产生从0到1的小数,如果此小数不大于Pm2,则此段进行变异,转③;否则,转④;③把不为0的数分别放在其它Mj-1个位置上,比较交换后的Mj-1种结果的适应值,选择一个最好的交换.如果按此最好交换产生的新染色体的适应值大于原染色体,则用此新染色体代替原染色体;否则,不接受新染色体.然后转④.④如果j<M,则j=j+1,转②;否则,结束.变异三:大段内变异.①对此染色体,设大段i=1;②随机产生从0到1的小数,如果此小数不大于Pm3,则此大段进行变异,转③;否则,转④;③重新随机产生元素值,即产生一个从1到T+td的随机整数,作为元素ai1ki1的值,然后,再产生一个从ai1ki1到T+td的随机整数,作为元素ai2ki2的值,依次类推,直到产生一个大段{ai11,ai12,…,ai1m1,…,aiM1,aiM2,…,aiMMM}(原不为0的值的位置不变).如果按此方法产生的新染色体的适应值大于原染色体,则用此新染色体代替原染色体;否则,不接受新染色体.然后转④;④如果i<N,则i=i+1,转②;否则,结束.3.2快速支持的适应函数设计综上所述,本算法对传统的遗传算进行了一些改进:1)采用可重复自然数编码,满足了约束(2)和约束(4)的可行性.2)提出三变异算子,构成一次变异操作,有效地完成整个变异过程.3)算法的整个过程始终保证约束(2)和(4)的可行性.4)为了满足计算的需要,把用于复制的函数和用于评价的适应函数区分开来,对于不同迭代数下的种群,(8)式中的C为一个变量,无论染色体如何变化,(8)式都能体现出各染色体的质量差别,保证了复制的有效进行.5)适应性函数设计为(11)式,同时考虑模型的目标函数及约束(3)的可行距离,择优选择时选取目标函数和可行距离均较小的解,并未拒绝可行距离不为0的解进入新一代,这是搜索的内点法和外点法的结合,既从不可行解向可行解的方向搜索(外点法),又从质量差的可行解向质量好的可行解搜索(内点法),这保证了搜索的全局性.整个算法流程如图1.4算法的有效性验证由于热轧带钢产品在合同订货中占极其重要的地位,因此我们以上海宝山钢铁公司热轧厂合同计划为例来测试本文的模型与算法.热轧厂工艺流程紧密衔接,所涉及的生产工序包括炼钢—精炼—连铸—热轧—精整.带钢的加工过程包括炼钢—精炼—连铸—热轧—精整五道工序,由于对于每个合同,其规格的带钢通过炼钢工序后需经过何种精炼(即通过哪台精炼工位)是固定的,因此可以把炼钢和精炼看作一道工序.另外,由于工艺要求,每种产品在经过炼钢或精炼后必须立刻进入连铸机,如不考虑连铸机的选择,把炼钢—精炼—连铸抽象为一道工序,这样,原来的五道工序就可以简化为炼钢(+精炼+连铸)—热轧—精整三道工序,其中只考虑精整工序中有并行机.在宝钢实际生产中,计划员一般需掌握两个月的合同,即从两个月的合同中选取合同来编制计划,因