改进混沌遗传算法寻优敏捷供需链动态调度的几

本文转载《商业研究》 作者简介：孔令夷（1977-），男，山东烟台人，西安邮电大学管理工程学院副教授，研究方向：敏捷制造、供应链管理、生产运营管理、计算智能、工业工程与管理。
　　基金项目：国家自然科学基金项目，项目编号：71102149；国家社会科学基金项目，项目编号：11CJY064；工信部通信软科学研究项目，项目编号：2013R01-2；教育部人文社会科学研究项目，项目编号：12YJC790084；陕西省教育厅专项科研计划资助项目，项目编号：12JK0056；西安邮电大学青年教师科研基金项目，项目编号：ZL2011-22。 知识世纪已来临，企业间竞争升级为供需链间竞争，产品制造模式和市场营销方式都发生实质性转变。全球化及不确定性客户需求的外部市场环境，对供需链提出了敏捷性的客观要求，敏捷供需链（Agile Supply Chain，简称ASC）ASC成为全球供需链转型升级的首选捷径，以及商业界和理论界的近期研究热点。作为新世纪供应网络的全新模式，ASC整合精益生产、并行工程等先进制造技术及理念，在高度竞合、动态多变的外部商业环境中，集成供应商、制造商、服务商、外包商、经销商等成员企业，快速实时响应外界商机和需求变化。ASC区别于传统供应链的最大特点是基于虚拟化运作方式，快速动态调度供应链成员企业所有可用资源，包括资源组合、调整、配置及解散。若要成功调度供需链资源，不但需要ICT技术、现代管理方法、强大的网络基础等，而且时段等瓶颈资源调度技术也是必不可缺的前提要件，即在ASC的稀缺时段资源约束下，怎样选择、组织、配置ASC资源，确定有效的进货、生产、储存、运输、销售、服务协同调度计划，以最低成本完成复杂多变的订单作业。
　　一、相关研究述评
　　很多学者已展开ASC进产存运销的调度研究，成果颇丰。在知网搜索主题为“敏捷供需链”及“调度”的2000年以来文献有83篇；在EI数据库中做同样查新，得到外文61篇；在Springer数据库中也做同样查新，得到16篇；经过比对，EI库与Springer库有5篇重复者，有效外文文献合计72篇，因此中外文相关文献共计155篇。经过系统梳理，ASC调度研究分类如下：
　　1.运筹规划法。文献[1]研究两工厂构成的ASC的产运协同调度，运用混合整数规划求解运能无约束条件下的最优调度解。文献[2]研究零产品库存下MTO型ASC的产运协同调度，求解了最优生产路线及运输路径。文献[3]研究MTO型ASC的产运一体化调度，构建面向交货期延迟违约费、运输费及加班费最小化等多目标的最优动态调度规划模型，给出求解方法。文献[4]研究倒行树状结构ASC的供产运动态调度问题，基于生产运输批量和运输配送变量设计，构造并探究总成本最低的供产运动态优化调度模型，提出适宜有效的动态规划算法。文献[5]评估MC模式下供应链动态调度的矛盾性，基于供应链总收益和成员满意的双视角，分析供应链动态调度的收益偏好决策，建立非线性调度规划模型，示例检验了模型适用性。文献[6]剖析大规模定制下ASC动态调度的影响因素，开发建立有针对性性、适宜MC模式、随机约束下、供需链调度优化的动态规划模型，论述了优化调度目标的合理性，解释优化调度实现过程，对变量赋予随机数值，仿真MC模式下复杂、多目标、动态优化火车生产供应链调度过程，经验证效果理想，并展望其实践应用。文献[7]研究面向确定性需求的多级ASC调度，构建期量约束下的线性规划模型，以高度柔性及精益性实现为目标而开发两阶段调度贪婪算法。文献[8]鉴于ASC复杂性以及其组成部分的生产系统规划的过大计算量，引入一种生产总体规划及确定最佳生产起始点的新方法——夹点分析法，通过混合供需数据而深刻理解ASC运作过程，简化再计划及快速决策，并提出混合整数规划模型求得最优调度解。实证分别取自单一产品以及单处理机生产的多产品，前者的最优生产计划用加法模型求得；对于后者，也给出一种算法以优化多产品出产顺序，其计算次数仅为传统解法的1/6。
　　总第437期
　　孔令夷：改进混沌遗传算法寻优敏捷供需链动态调度时段
　　····
　　商 业 研 究
　　2013/092.遗传算法。文献研究ASC质量兼容产运调度问题，融入模糊理论构建质量及成本约束下的生产和运输一体化调度模型，该模型以模糊化交货期客户满意度最优为目标函数，并提出了模型求解的遗传算法。
　　3.其他元启发式算法。除了遗传算法以外，还发现不少其他算法用于ASC调度方案求解。文献[11]设计供需链调度矛盾解决途径，剖析动态调度机制，采用蚁群算法寻优供需链运作动态调度。文献[12]剖析拉式供需链动态调度本质，指出调度瓶颈，引入针对性改进蚁群算法，数值实验显示寻优性较强。文献[13]研究多工厂构成的ASC的产运动态调度，提出引入并行工程以实现订单的准时生产、及时交货，面向零排队时间及零空闲时间，设计启发式算法寻优无限产能条件下的动态调度方案。文献[14] 研究面向大规模定制的ASC集成调度问题，以信息及过程集成作为调度目标，建构整合供应商评选及外协商排序的综合调度优化模型，开发了稳定且有效求解的蚁群算法。文献[15]构建面向多个不同地点市场的单机生产、单个运输工具的产运销协同调度模型，调度目标是作业到达累计时间最小化，该问题被证明是强NP难问题，开发了多项式时间算法。
　4.其他定性方法。文献[16]分析供需链协同调度过程及相应使能模型，论述大规模定制环境下协同供需链调度模式及实施架构，但是缺乏对调度技术的探究。文献[17]剖析ASC制约因素及追究其复杂矛盾性，系统性描述动态优化调度的三方面瓶颈环节，评述因素、矛盾及瓶颈之间的交互关系，基于此，设计优化调度对策，然而并未给出有效的定量计算方法。
　　对以上几类文献进行归纳及分析评鉴，都能发现存在明显的局限性。首先透析运筹规划法，所求出的调度解方案与车间现场的单元调度偏差太大；仅仅采用静态、单一的调度方法来解决动态、多变的ASC调度问题，效果必然大打折扣；适用性较差，只能得到非常有限的应用价值，而不能满足ASC动态调度的实际需要。其次，TG A存在早熟收敛及冗余迭代的常见固有缺陷，导致求解效率低，而且经验证只能获得局部最优解，无法获得全局最优解。环境如果发生变化，传统算法就显得无能为力，还必须考虑更高级算法。再次，启发式算法都局限于改善ASC调度的局部环节，并不能真正解决TGA的早熟缺陷，也就不能确保真正求得ASC全局性调度最优解；而且它仅适用于有限条件，如无限产能、动态种群、距离对称、大规模定制等，其局限性较为明显。最后一类属于定性方法，不能给出最优解，实用性不足。而且，已有文献大多致力于供需链集成调度模式、机制及管理策略，对作为关键性、瓶颈性、核心性资源的可调度时段优化调度研究尚显不足，亟待深入探究。ASC动态优化调度的实质是怎样配置供需链成员企业的可调度时段，使其以最小供需链成本获得最大产出。对于调度时段的形式，已有研究大致有两种选择可参照：其一是连续时段，各生产商可调度时段不能分割，基于单件生产时间就简单得出产出量，这种方法局限性明显，如果单件加工时间与整个时段不构成理想的倍数关系，则会造成时段资源浪费；其二是ASC的各企业或车间所辖若干时段为已知，一个时段能且仅能完成一个生产工序，产出一件在制中间品（加工作业）或部件（部装作业）或制成品（装配作业）。本文拟选取后一种情形，以最大程度地提高ASC的精益性、敏捷性、资源配置效率及其总投入产出比。
　　近些年越来越多学者采用混沌论思想，大幅度增强算法搜寻最优解的能力，确保优良染色体基因的严格遗传继承，本文就是要通过引入混沌搜索的寻优技术能更接近ASC动态调度时段的现实情境，更贴切地表现并符合复杂多变、不确定性、随机性的外部商机及需求，能生成随机性强的优良种群；本文还将利用混沌寻优法的起始态敏感性优良特性，应用贪婪机制改进算法的种群初始化、起始编码方案，以图实现混沌技术从一开始就能发挥最大效能；针对当前被广泛用于算法改进的 Logistic 混沌法的均衡性差、收敛速度和精确度不满意的现状，本文拟对混沌搜索实施优化，采纳更优的幂函数载波混沌搜索技术，优化混沌向量，提升混沌寻优速度； Bierwirth等基于各种算法数值实验比较研究，开发优先保留交叉法（Precedence Preservation Crossover，PPX），极大地提升TGA的全局寻优性能；最后，基于贪心法执行启发式目标导向变异操作（Goal Orientation Mutation，GOM），同步匹配于混沌搜索的随机性，确保优良基因保留传承，进一步提高算法的随机寻优性。因此，本文基于对供需链生产、储存、运输调度研究文献述评，对ASC动态时段调度建模，基于混沌理论及贪婪机制，开发一种对TGA全过程、系统性改进的高级前沿算法——改进混沌遗传算法（Improved Chaos Genetic Algorithm，简称ICGA），对编码方案、种群初始化、遗传相关算子操作、搜索操作、适值函数设置、选择操作、最优解判定等作出全面、整体、彻底改进，克服TGA因过度依赖参数和算子、早熟收敛、冗余迭代而无法得到ASC动态调度全局最优的缺点，也弥补已有大量文献拘泥于某种单一算法而不能实现ASC全链条优化的不足，最后采用制造业实例检验CGA在时段调度方面的相对高效性。
　　相对于前述以往的调度算法或方法，本文提出ICGA所表现出的无可替代优势在于：复杂、不确定、随机情境下种群个体的高智能性、快速收敛、复杂问题简单化、易于操作、变量设置较少、局部优化与全局优化相结合而保持统一化等。在中国知网数据库再次对ICGA作文献查新，以“混沌遗传算法”为篇名，2008年至今刊载于核心期刊仅有33篇，说明该领域研究明显不足、极其缺乏、亟待推进。因此更有必要展开ASC动态调度的ICGA研究，以弥补不足，尝试突破。
　　二、ASC动态调度时段模型构建
　　（一）问题提出
　　ASC动态调度时段问题是指沿ASC方向的生产、运输、销售型上中下游企业根据复杂多变的市场商机快速优选组合成员企业，敏捷地构建动态联盟或虚拟企业，响应大规模客户的个性化、多元化需求，联合制定进、产、存、运、销协同整合的动态调度计划，确保具有可调用时段作业特征的供需链各方协同运作，实现ASC全局优化。假设ASC涉及多家企业的组合协作，下辖若干个生产车间，分别或共同执行某类加工装配型产品的所有组件加工工序，最后完成总装给客户交货。某一道加工工序可能有多家候选企业或候选车间都能胜任，某家企业或车间也能为多家其他企业或车间提供外协加工、代加工或供应生产用零部件。因为企业或车间的运输距离、时间及运输配送物料价值量的不同，所以ASC内部成员企业的运输成本各有不同；由于各生产车间的可用调度时段、加工对象价值量有异，因此企业或车间的生产及储存成本也各不相同。而且，完成下道组件加工工序的企业或车间唯有所有上道（游）工序完工后才能进行生产，即该类产品属于成套性加工性质。供需链的企业或车间之间运输采用顺序移动方式：上道工序按照客户订单将所有组件加工完毕后，由运输商一次性地专项运输配送给负责下道工序的企业或车间，运输批量等于产品订货数量。
　　ASC调度时段问题可表述为：给定ASC的已有企业或车间分别负责加工的组件种类、产能、可用调度时段、相互间运输时间及各种成本发生系数等，为完成产量为Q的产品生产、储存、运输作业任务，在确定交货期D的约束下，寻求各组件在不同企业或车间的调度时段最优选择方案，划定ASC企业或车间之间的分工协作及供求关系，从而使ASC以最低的总运营成本最大限度地满足动态需求，敏捷地捕捉动态商机，为各成员企业或车间获得最大供需链总收益。综上，ASC调度时段问题的本质就是可调度时段优选及重组，可以根据运筹规划法建模，以及借助聚类分析法解析。
　（二）调度时段优化模型构建
　　设计以下参量：设ASC需完成的成品产量为Q，交货期为D；ASC容纳有n个企业或生产车间，用集合W表示，W={W1，…，Wi，…，Wj，…，Wn}，其中1≤i
　　式（1）第一部分是ASC的储存成本，Bj=minBjk/xjk是车间j的第一个被调度时段的开工时刻，易知Bjk0=+∞，B0=D，Fi=maxFikxik是车间i的最后一个被调度时段的完工时刻。式（1）第二部分是ASC的生产成本，第三部分是ASC的运输成本。约束条件式（2）是加工量约束，表示第h道工序耗用全部胜任其 车间的可用调度时段总个数，即第h道工序的加工总次数，必等于成品产量Q。式（3）是ASC各关联车间调度时段均衡性及匹配性约束，表示第h道工序耗用车间j的调度时段数量等于全部胜任其上道工序车间提供给车间j的用于第h道工序加工对象组件的相关零部件加工的调度时段数量。式（4）是成套性加工约束，表示车间j的最早开始生产时间必然大于其所有上道工序车间的完成加工时间再加上中间品运输时间的最晚者。式（5）是按时交货约束，表示总装车间1的最迟完成时间必须小于客户交货期，确保ASC准时给客户交货。式（6）是决策变量约束，表示当车间i的时段k未被调用，那么时段k就不会生产组件给其他车间，反之反亦，必有且仅有唯一的下游车间j接收时段k完工的组件。式（7）也是决策变量约束，表示两个车间若没有运输时间，则不存在上下游供求关系。
　　三、ASC动态调度时段的改进混沌遗传算法
　　通过ASC动态调度时段模型，能够发现该问题复杂性极高：不但选择供需链协作方，还要选择各协作方的调用时段；不但确保组件生产商可调用时段满足下游装配需求，还要确保组件生产商及时从上游供货商处获取物料而正常开工；不但要平衡产能与需求计划，还有平衡储运能力；不但控制生产成本，还要管控运输及储存成本。加之众多期量约束、调度时段可得性约束等，显而易见，根据理论信息学中的信息复杂度理论，该问题具有NPC计算强复杂性，是典型的NP难问题。本文拟基于混沌理论应用ICGA求解得出ASC动态调度时段最优方案，选用优于二进制的分节式时段编码方法，引入与混沌搜索的高随机性相匹配的贪婪法，再执行强随机性的顺序交叉、移位变异、局部邻域及混沌搜索操作，采用轮赌盘法进行染色体串选择，迅速求得ASC最优调度时段决策方案。
　　（一）编码方案
　　常用的二进制编码方式在时段调度中有明显缺陷：码长过大，严重冗余，极大地影响了算法运行效率，因而设计有效的分节式时段编码方案，结合时段号、车间号及组件号三个十进制码而得出。
　　（二）初始化种群
　　初始种群的优良性直接关系到混沌寻优操作成效，可谓极其关键。随机法不能确保其满足大量的约束条件（如式2-8），易混杂许多无效个体，影响算法效率。拟利用贪心机制产生更多较优染色体，改进初始种群质量，即选取若干局部最优的可调度时段染色体纳入到初始种群中，以包括贪心法的局部最优解和随机法的其他个体。
　　（三）交叉变异操作
　　GOM源自步步寻优的贪心机理，如果父串中能找出两个相邻基因的生产、储存及运输的总供应链成本是父串中所有相邻基因间总成本最大者，则这两者相邻就很可能不太合理。处理方法是：任选二者其中一个基因与其他随机生成的第三个基因对调，也就是以总的供需链成本目标函数最小化为导向，若对调后的新染色体串具有更高的适应度，则变异操作成功，反之，再次更换一个随机的基因与之对调，试图增大其适应度值。多次变异操作后的染色体串还不能真正获取比原先父串更高的适应度值，就针对二者其中另一个基因实施上述完全同样的与随机基因对调操作，再次试图提高父串被变异操作后的适应度值。假如还未取得实效，根据启发式思想，只好判定二者相邻是合理的存在，但是还可以再考虑对原先二者的基因对调，若对调后适应度值提高，则用新串替换原串。反之，若在前述任一个环节取得了适应度值提高的实效，即被变异操作后的串的适应度值高于原父串，则替换父串，子串由此被生成。不难看出，GOM比对换、移位、插入、反序等变异操作能更多保留染色体内基因的逻辑关系及合理顺序，使得父串的优点被遗传下去。
　　（四）局部邻域搜索及混沌搜索
　　5.若达到停止条件，即最优调度时段解的判定条件，获取最高适应度值，则结束混沌搜索，得出最优解x*ik ；反之，回到式（9） ，使g增加1，再算出n个新数，继续向下操作。
　　（五）适应度函数及选择操作
　　适应度值是衡量染色体质量的关键参数，因本文追求总供需链成本最小化，所以，令适应度函数：
　　其中，α是常量，ci为各车间的可调度时段数量，n为供需链的车间数量，m为加工组件的数量，z为实际发生成本，即目标函数值。
　　生物物种不断向高级演化的动力机制就在于大自然选择。基于染色体适应度评判，就能区分其优良与否，即适应性的高低。适应度值较高者更有可能优先被选择，其在子代中的比例也将逐代增大，从而子代也将在演化过程中持续地优于父代。本文拟用轮赌盘法选择调度时段染色体个体，最大限度地保留最佳基因片段，保证算法的较高寻优性。
　　TGA运行过程难免有很多不可行解，浪费CPU资源，拖延寻优时间，致使效率不堪。因此拟对最优解作出以下判定和鉴别：
　　先算得zmax=maxi，j，kz（i，j，k），根据决策变量约束，各企业车间的调度时段为有限资源，存在不可用时段，非调度范围内，而且企业或车间之间的供求关系也是受限定的，因此对包括不可调度时段或不存在上下游供求关系的ASC调度时段染色体串的总运作成本设置为zp=z（ip，jp，kp）=λ*zmax+1，λ为足够大的正整数，若子串中含有不可调度时段或不存在供求关系的基因，必有下式（11）存在：
　　即该子串的适应度值最小，很快被淘汰掉，也就去除不满足有限调度时段约束及供求关系约束的不可行最优解出现的可能情形，以确保不破坏算法寻优的可行性，即求出的最优调度时段解必定是可行的。反之反亦，下式（12）一旦满足，必然子串可行可信，若是最优解，则可以成立而输出。总之，若ICGA求得ASC可调度时段最优解的适应度值小于 （六）算法步骤