一种有限运输条件下柔性作业车间调度的编码与解码方法

摘要

本发明公开了一种考虑有限运输条件下柔性作业车间调度的编码与解码方法，该方法中包括两个方面分别是具有运输冗余的三层编码方式和具有校验与前插机制的解码策略。在编码方式中设计了由工序排序基因串、加工设备选择基因串以及具有冗余的运输设备选择基因串组成的三层染色体编码。在解码策略中有三个部分，分别为对运输设备选择基因串的校验阶段，三层编码转换成两层编码的重组阶段和为了提高在该编码下调度完工时间的前插阶段。本发明为有限运输条件下柔性作业车间调度问题提供了一种编码与解码的方法，通过运用该方法有效的解决了调度中工序排序、加工设备选择以及运输设备选择的问题。

说明书

技术领域

本发明涉及生产车间的调度技术，尤其在有限运输条件下针对柔性作业车间生产调度的一种编码与解码方法，属于先进制造控制与调度技术领域。

背景技术

柔性作业车间调度问题广泛存在于离散加工车间中，是面向多品种、小批量柔性排产的最有效的方法之一。目前大多数柔性作业车间调度的问题聚焦于加工阶段，对加工阶段的前期准备以及后期调整阶段的影响已有研究，然而对于运输阶段仅仅将运输时间作为调度过程的影响因素。在工艺过程复杂、多工序并行的混合生产车间中，具有多种加工设备与多台运输设备，运输过程将对生产过程以及生产效率带来严重的影响。

柔性作业车间是一种典型混合作业车间生产模式，在该模式中，工件的工序可以被不同设备进行加工，不同设备加工同一个工序时，当设备的加工能力不同时，所需要的加工时间也不同。因此在该生产模式下，不仅仅需要解决传统调度上的工序排序问题，还需要解决每道工序的加工设备选择问题，除此之外，在有限运输条件下，还需要对每道工序解决运输设备的选择问题，以及运输设备与加工设备之间的关联问题。有限运输条件包括运输前的准备过程、运输后的调整过程以及多台运输设备的选择，这些运输因素对于加工过程具有强制性的约束限制，增加了生产调度的难度，严重影响生产效率。因此，研究有限运输阶段与加工阶段相结合的调度技术，对于柔性作业车间调度是十分有意义的，对于生产调度技术应用在实际制造过程中也是十分有价值的。

发明内容

本发明设计了一种考虑有限运输条件下柔性作业车间调度的编码与解码方法，该方法中包括两个方面分别是具有运输冗余的编码方式和具有校验与前插机制的解码策略。基于该编码与解码策略，可以采用遗传算法等启发式方法，对有限运输条件下柔性作业车间调度问题实现生产排产与优化计算。这种编码方式可以解决调度问题的基本需求：工序排序、加工设备选择以及运输设备选择，除此之外，提高了染色体进行交叉以及变异操作的可操作性。该编码与解码的方法分为两个部分，分别为：具有运输冗余的三层编码过程和具有校验与前插机制的解码过程，具体如下：

1.具有运输冗余的三层编码过程

在考虑有限运输条件下柔性作业车间调度问题的染色体编码设计中，需要解决两个问题：工序排序与设备选择，由于有限运输条件的约束，对于设备选择不仅要解决加工设备选择的问题，还需要解决运输设备选择的问题，因此设计了由工序排序、加工设备选择以及运输设备选择的三层染色体编码，分别为：工序排序的基因串(以OS表示)；加工设备选择的基因串(以MS表示)；具有冗余的运输设备选择的基因串(以TS表示)。

工序排序的基因串：以3个工件为例介绍工序编码方式，三个工件的工序数依次为4，1，3。则按照工序总数生成序列1-1-1-1-2-3-3-3，然后随机排序生成OS(1-2-3-3-1-3-1-1)。其中内部数字表示工件号，同一个数字出现的次数表示该数字代表工件的工序号，如工序基因串第一个位置为1，且数字1是第从左往右第一个，则表示工件1的第1道工序O

加工设备选择的基因串：加工设备选择的基因串是根据工序排序的序列而生成，依照上述工序排序为O

具有冗余的运输设备选择的基因串：运输设备选择的基因串按工序排序依次在每道工序的可选运输设备集中随机选择该工序运输的设备，如按照上述工序生成运输设备基因串TS(1-1-2-1-1-2-1-2)，其中内部数字表示运输设备号，设备基因串的第一个位置为1，表示负责O

2.具有校验与前插机制的解码过程

解码过程不仅对编码做了正确性的评价，改进了编码的可实施性，并且提高了在该编码下调度的完工时间指标。解码过程分为三个步骤，分别为校验、重组和前插。校验阶段对编码做正确性评价，重组阶段对编码做可实施性调整，前插阶段提高了编码表示的调度指标。

校验阶段：当同一个工件前后两道工序的加工设备是同一台设备时，将不存在运输阶段，因此对运输编码序列TS进行解码校验，根据加工编码序列，计算出不需要运输的阶段并设定为0。如在OS(1-2-3-3-1-3-1-1)，MS(2-1-3-4-2-3-1-2),TS(1-1-2-1-1-2-1-2)的编码下，检验OS和MS发现，OS的第1位和第5位，即工件1的前两道工序在MS中第1位和第5位都选择M

重组阶段：为了降低编码复杂度，便于程序的编写，在解码过程中将修正完的三层编码(OS，MS，TS)转换成考虑运输的工序排序(以OSC表示)与考虑运输的设备选择(以MTS表示)的双层编码。

(1)OSC生成过程：OSC由原来的编码OS中每一位依次复制生成，OSC的长度为OS的两倍，其中OSC序列中的奇数位表示运输阶段，偶数位为加工阶段。如OS(1-2-3-3-1-3-1-1)转换成OSC(1-1-2-2-3-3-3-3-1-1-3-3-1-1-1-1)，OSC的第1位为奇数位，表示工件1的工序1的运输阶段，OSC的第2位为偶数位，表示工件1的工序1的加工阶段，依次往后。

(2)MTS生成过程：MTS由原来的运输设备选择TS与加工设备选择MS交叉合并生产MTS，其中MTS的奇数位表示运输阶段的设备选择，偶数位表示加工阶段的设备选择。如TS(1-1-2-1-0-2-1-2)与MS(2-1-3-4-2-3-1-2)转换成MTS(1-2-1-1-2-3-1-4-0-2-2-3-1-1-2-2)，MTS的第1位为奇数位，表示工件1的工序1的运输阶段选择的运输设备号，即为TS中的第1位，MTS的第2位为偶数位，表示工件1的工序1的加工阶段选择的加工设备号，即为MS中的第1位，依次往后。

前插阶段：为了提高编码表达的有效信息，在编码可调整范围内，通过前插操作提高完工时间。首先按照OSC和MTS的编码信息进行解码排序，在同一台设备上，可能会出现多个待机的间隙，当后续工序所花费的时间小于设备前序待机间隙时，可将该后续工序前插到待机间隙，提高完工时间。在解码过程中进行前插操作时，当待处理工序的工艺允许时刻大于等于设备允许时刻时，待处理工序不可前插；反之，可寻找前序待机间隙大于待处理工序时间段的位置，将待处理工序时间段前插至该间隙。

附图说明

下面结合附图和实施例对本发明进行进一步说明。

图1是具有冗余运输的三层染色体编码过程示意图。

图2是解码过程中校验阶段和组合阶段过程示意图。

图3是解码过程中前插阶段过程示意图。

图4是本方法的实施流程图。

具体实施方式

本发明设计了一种考虑有限运输条件下柔性作业车间调度的编码与解码方法，该方法中包括两个方面分别是具有运输冗余的编码方式和具有校验与前插机制的解码策略。在编码方式中设计了由工序排序、加工设备选择以及具有冗余的运输设备选择的三层染色体编码，在解码策略中有三个部分，分别为对冗余的运输设备选择编码的校验阶段，将三层编码转换成两层编码的重组阶段和为了提高在该编码下调度完工时间的前插阶段。下面结合附图以及具体实施方式，对本发明做进一步描述：

1.具有运输冗余的三层编码过程

如图1所示，描述了由工序排序的基因串(以OS表示)、加工设备选择的基因串(以MS表示)、具有冗余的运输设备选择的基因串(以TS表示)组成的三层编码的生成过程，具体如下：

步骤1：工序排序的基因串

如图1左侧上部分所示，以3个工件为例介绍工序编码方式，三个工件的工序数依次为4，1，3。则按照工序总数生成序列1-1-1-1-2-3-3-3，然后随机排序生成OS(1-2-3-3-1-3-1-1)。其中内部数字表示工件号，同一个数字出现的次数表示该数字代表工件的工序号，如工序基因串第一个位置为1，且数字1是第从左往右第一个，则表示工件J

步骤2：加工设备选择的基因串

如图1左侧中间部分所示，加工设备选择的基因串是根据工序排序的序列而生成，依照上述工序排序为O

步骤3：具有冗余的运输设备选择的基因串

如图1左侧下部分所示，运输设备选择的基因串按工序排序依次在每道工序的可选运输设备集中随机选择该工序运输的设备，如按照上述工序生成运输设备基因串TS(1-1-2-1-1-2-1-2)，其中内部数字表示运输设备号，设备基因串的第一个位置为1，表示负责O

如图1右侧所示，按照上述三个步骤，将生成具有冗余的三层染色体编码，该编码由工序排序(OS)、加工设备选择(MS)和运输设备选择(TS)组成。

2.具有校验与前插机制的解码过程

如图2和图3所示，解码过程分为三个步骤，分别为校验、重组和前插。图2描述了校验阶段和重组阶段的操作过程，图3描述了前插阶段的操作过程。具体如下：

步骤1：校验阶段。

如图2上侧所示，描述了校验阶段的操作过程，在此阶段当同一个工件前后两道工序的加工设备是同一台设备时，将不存在运输阶段，因此对运输编码序列TS进行解码校验，根据加工编码序列，计算出不需要运输的阶段并设定为0。如在OS(1-2-3-3-1-3-1-1)，MS(2-1-3-4-2-3-1-2),TS(1-1-2-1-1-2-1-2)的编码下，检验OS和MS发现，OS的第1位和第5位，即工件1的前两道工序在MS中第1位和第5位都选择M

步骤2：重组阶段

如图2下侧所示，描述了重组阶段的操作过程，在此阶段为了降低编码复杂度，便于程序的编写，在解码过程中将修正完的三层编码(OS，MS，TS)转换成考虑运输的工序排序(以OSC表示)与考虑运输的设备选择(以MTS表示)的双层编码。

(1)OSC生成过程：OSC由原来的编码OS中每一位依次复制生成，OSC的长度为OS的两倍，其中OSC序列中的奇数位表示运输阶段，偶数位为加工阶段。如OS(1-2-3-3-1-3-1-1)转换成OSC(1-1-2-2-3-3-3-3-1-1-3-3-1-1-1-1)，OSC的第1位为奇数位，表示工件1的工序1的运输阶段，OSC的第2位为偶数位，表示工件1的工序1的加工阶段，依次往后。

(2)MTS生成过程：MTS由原来的运输设备选择TS与加工设备选择MS交叉合并生产MTS，其中MTS的奇数位表示运输阶段的设备选择，偶数位表示加工阶段的设备选择。如TS(1-1-2-1-0-2-1-2)与MS(2-1-3-4-2-3-1-2)转换成MTS(1-2-1-1-2-3-1-4-0-2-2-3-1-1-2-2)，MTS的第1位为奇数位，表示工件1的工序1的运输阶段选择的运输设备号，即为TS中的第1位，MTS的第2位为偶数位，表示工件1的工序1的加工阶段选择的加工设备号，即为MS中的第1位，依次往后。

步骤3：前插阶段

如图3所示，描述了前插阶段的操作过程，在此阶段为了提高编码表达的有效信息，在编码可调整范围内，通过前插操作提高完工时间。首先按照OSC和MTS的编码信息进行解码排序，在同一台设备上，可能会出现多个待机的间隙，当后续工序所花费的时间小于设备前序待机间隙时，可将该后续工序前插到待机间隙，提高完工时间。在解码过程中进行前插操作时，当待处理工序的工艺允许时刻大于等于设备允许时刻时，待处理工序不可前插；反之，可寻找前序待机间隙大于待处理工序时间段的位置，将待处理工序时间段前插至该间隙。