混合流程生产系统优化调度方法研究

1 问题描述及模型

    混合流程生产系统是一种具有离散加工过程和连续生产过程的复杂生产方式，是现代化生产中有普遍意义的加工方式，常见于轧钢和冶炼行业及化工等行业之中) 解决混合生产调度问题有重要的实际价值) 由于调度问题的复杂性和高难度，目前的研究主要采用的方法有遗传算法和整数规划算法，笔者研究的混合流程生产系统模型如图1所示，优化调度目标为生产成本最小。

    为了使优化调度更简单、明晰，可将优化调度问题分解为两个层次进行建模：


    上层优化调度和下层优化调度) 上层调度是将n个任务分为F个批次B（1），B（2），……，B（F）进入混合加工系统。

2 最优解的性质与方法分析

    由于上述模型的优化问题属于NP困难问题，为了满足实际生产中及时调度时间的要求，考虑使用启发式分枝定界算法进行优化，因此需要对所研究的混合流程加工系统进行分析，找出其内在的一些规律和性质，以便构造出相对可行的启发式分枝定界算法。

    对于混合系统，在上层分批优化调度时，可给出以下规则：

    规则1 一批次任务的完工时间为一批次任务中第一个任务的交货期。

    对于下层优化调度问题，由于M2要连续加工，故有如图3所示的分批时间顺序， 根据分批调度的原理，可给出以下调度规则 ,T2为机床M2加工时间。

    规则2 如果一个任务相对于当前一批次任务完工时间的提前" 拖期惩罚大于开工一次的加工费用，则要重新分配一批次任务。

    规则3 在一批交货期不同的任务中，最优完工时间为第K个任务的交货时间，这里所有任务相对D的提前/拖期惩罚F为

3 启发式分枝定界算法

   3.1 算法步骤

    根据调度规则，可构造相对简单可行的启发式分枝定界算法，在上层调度与下层调度中使用反向调度方法。 即首先在下层调度中，按产品交货期确定任务在上的交货期，再根据上的分组与加工时间，得到M1上的交货期，再由循环次数可推出上层调度中，所有任务集进入混合系统的交货时间。

   在下层分批调度的基础上，可得到任务集对混合系统的交货期! 据此可进行上层优化调度，其具体方法是：为保证按期交货，以第一个任务交货期作为第一次的投入时间，然后根据规则% 逐个判断每个任务是否满足重新分批的条件，如若不满足条件，再分配下一个工件进入本批，继续上述判断。当满足分批条件时，本批次分组结束，再根据规则3确定新的一批次的投入时间重复上述分批过程，直至所有工件分批完成。

    3.2 算法实现

    启发式分枝定界优化调度的基本方法是，所有任务Ji首先按交货期Di的非减序排列，再逐个将任务放进混合流程生产系统中+ 然后再对每次排序进入系统的工件根据式（3）对Y进行判断，这样就完成了上层的优化调度分批。

    在上层优化分批完成之后，接下来就要解决下层优化调度中每批内部的排序与调度问题，采用批调度优化方法，使用启发式算法进行优化。

    根据前面的分析与算法具体步骤，可用形式化语言描述优化算法，算法形式如下：

4 结束语

    在对混合系统分层建模的基础上，笔者针对加工系统的具体要求，推导出了优化调度规则，简化了混合流程加工系统模型的复杂度，得到了典型的混合流程加工系统模型，并通过分析混合流程加工系统内在的特点和性质，针对上层模型和下层模型分别构造了一种效率较高的启发式分枝定界算法，最后给出了两种算法的具体过程。