摘 要： 在工厂实际生产中，模具的换模时间在生产调度中不可忽略。为了更合理地研究平行机车间调度问题，本文将存在序依赖的换模时间考虑进调度模型之中，同时以最小完工时间和最小拖期时间为目标，在经典遗传算法的基础上，对算法选择算子以及交叉变异概率进行改进，避免早熟现象的发生。通过计算结果的比较，证明本文中调度模型更符合实际生产情况，改进后的算法能够得出更高质量的解，且求解效率更高。
关键词： 换模时间； 平行机调度； 改进的遗传算法

    对生产过程进行作业计划时，生产调度作为一个关键模块，是整个先进生产制造系统实现管理技术、运筹技术、优化技术、自动化与计算机技术发展的核心。调度的任务是根据生产目标和约束，为每个加工对象确定具体的加工路径、时间、机器。一般调度以最小完成时间和最少拖期惩罚等为目标。目前生产调度问题的研究很多，何莺等[1]提出了以工件提前/拖期惩罚代价最小、生产周期最小为目标的多目标优化调度算法，可得到满意的较优解；孙志峻等[2]提出了针对批量生产的柔性作业车间调度方案；Runwei等[3] 研究了遗传算法在作业车间调度问题中的应用;参考文献[4]讨论了双目标下，带一种资源约束的工件成型类别的并行机调度问题。参考文献[5]讨论了安装时间受资源约束的单机成组调度问题。参考文献[6]则讨论了不确定条件下不同交货期窗口的Job Shop调度。
    本文所针对的是带有模具换模时间的平行机调度问题。单机调度指的是所有工件均需在指定的单台机器上加工完成，即单机排序问题；平行机调度指的是能够完成某种功能的机器不止一台，即平行机排序问题。模具是用来成型物品的工具,它主要通过所成型材料物理状态的改变来实现物品外形的加工。使用不同种类模具的工件之间需更换模具，在此之间需要消耗换模时间，换模时间存在序依赖。每个工件有交货期和加工时间，其加工时间预先确定,其生产时间为前一个工件的结束时间。这类问题的一个典型应用是模注加工，如注塑车间,塑料件由注塑机加工而成,每个塑料件的加工都必须有一种模具装设在注塑机台上,经过一段成型周期加工而成，不同元件的加工中间需更换模具,并需一定的工时。
1 平行机调度问题建模
    调度问题的实质是安排最优的作业加工顺序，让机器的空闲度最低，换模时间最省，实现机器使用最大化，并且使各产品的拖期时间最少，工件最大完工时间最短。该平行机问题可描述为:给定m台相同的机器，待加工工件为n个，每一个工件只需要加工一道工序，每一个工件在加工均要使用模具，按照工件使用模具的种类不同可分为g类。
    问题假设如下：(1)每台设备同一时刻只能加工一个工件；(2)每个工件只有一道工序； (3)加工时间预先确定，且工件的安装、卸载时间忽略不计或者认为被包含在所给加工时间内;(4)模具的安装需要安装时间，模具更换需要换模时间(安装时间包括在内),时间预先确定；(5)所有机器在t=0时刻都可用;(6)所有工件在t=0时刻都可被加工。(7)模具使用时间能满足生产需求。
 

2.2 初始种群的产生
    初始种群的大小和优劣对算法的执行效果有明显的影响。考虑到搜索效率和质量，为防止产生非法解,在初始化种群时,采取如下的初始化方法：先随机产生?渍个(种群尺寸)n维向量(ji)分别作为初始种群?渍个个体的第一行，其中ji为互不相同的自然数；依照此办法随机生成每个个体的第二行向量。
2.3 目标函数评价
    目标函数即适应度的计算，由于上述问题是一个多目标问题，目标为完工时间最小化和拖期时间最小化，在不同的生产环境要求的目标不一样。因此，本文通过权重、线性组合的方式将多目标转化成单目标问题。
    Z=βz1+γz2 　　　　　　　　　　　　　　 (5)
式中，β、γ分别为总完工时间和最大拖期时间的权重系数。通过AHP层次分析法来确定这些指标项的权重系数的大小，将多目标问题转化成单目标问题。
2.4 遗传算子

    遗传算子主要由选择、交叉、变异三种构成，针对文中问题具体设计主要内容如下：
    (1)选择
    传统的选择操作容易造成在进化初期,有可能适应度很高的个体被选择的概率很大, 从而复制出很多后代,因个体单一而无法继续进化使搜索陷入局部最优；并且在进化后期,当各个个体的适应度差距不大时,该方法已经不再具有选择能力,体现不出个体的优劣。本文选用如下方法，将群体中的所有个体按照适应度从大到小进行排列,排在最前面1/4的个体复制两份,中间的2/4复制一份,最后面的1/4抛弃。用此方法来进行选择,可以将适应度比较低的个体直接淘汰掉,并且增加了适应度较好的个体的数目,从而在一定程度上解决了上述问题。
    (2)交叉
    交叉操作用于组合出新的个体，在解空间中进行有效搜索，同时降低对有效模式的破坏概率。在此将两个父代个体中的一个个体作为参照，对另一个个体中的位置进行重组，然后与其实现一个循环链，并将对应位置的基因填入相应的位置，循环组成后再将另一个个体各位置的基因填入相同的位置。
 
3 计算实例与结果
    根据上述建模思想和算法进行算例分析。例：该生产任务包括50个工件，工件按照使用模具种类的不同分为8组，有6台机器可用于加工，工件的加工时间如表1所示，工件交货期以及模具的安装时间和换模时间已知。为了验证算法的有效性,本文算法通过Visual C++编程实现。算法主要参数假设如下：种群个数20，变异率和交叉概率由程序中自适应得出，循环迭代次数为50。

    通过AHP层次分析法得出最大完工时间以及拖期时间的权重分别为0.68与0.32。经计算机运算分析可知，目标函数为100.64；这批零件的最大完工时间至少为148，并且没有发生零件生产周期延误。通过该程序与传统遗传算法进行比较，本文算法能够在较短的时间内找到比较满意的解。
    本文在分析平行机调度问题的基础上，建立了符合实际情况的调度模型。该模型加入了模具换模时间，且换模时间存在序依赖，以拖期时间最小化和生产时间最小化为目标，使得该模型具有更高的实用价值。针对经典遗传算法进行了分析，改进了遗传算法的交叉和变异概率，并通过仿真实验验证了算法的有效性。但对于受资源约束的调度问题，还有待进一步研究。
参考文献
[1] 何莺，蔡鸿明. 基于需求优先的多目标柔性车间调度研究[J]. 微型电脑应用，2002，7(5): 1-3.
[2] 孙志峻，乔冰，潘奎科,等. 具有柔性加工路径作业车间批量调度优化研究[J]. 机械科学与技术,2002，3(4):348-350.
[3] Cheng Runwei, GEN M, TSUJIMURA Y. A tutorial survey of Job-Shop scheduling problems using genetic algorithms partⅡ: hybrid genetic search strategies[J]. Computers and Industrial Engineering, 1999,36(2):343-364.
[4] 曾相戈,韩伯棠. 一种求解带资源约束的并行机器多目标调度问题的遗传算法[J].系统工程理论与实践, 2005,25(9):58-62.
[5] 闫杨，赵传立. 安装时间受资源约束的单机成组调度问题[J].电机与控制学报，2007,11(1):70-73.
[6] 李平,顾幸生.不确定条件下不同交货期窗口的Job Shop调度[J].管理科学学报，2007,7(2)：22-26.