在优化该问题前，编码是一个重要的环节。不用于其他类型的调度问题，本章研究的调度问题考虑了工序排序、机器分配和工序的实际加工时间。因此，根据问题的特点，本章提出了一种基于三层信息的编码机制，该编码机制由三个独立的数据结构构成：第一个数据结构o表示工序排序，第二个数据结构u表示工序对应的机器编号（索引），第三个数据结构v表示工序的实际加工时间。第一个数据结构o由工件索引构成，其中工件i出现了ni次。第二个数据结构u是一个与机器编号相关的整数矩阵。第三个数据结构v是在每台机器上所有工序的实际加工时间。每个矩阵的长度都等于所有工序的总数和。

为了进一步解释这种编码机制，表7-1展示了一个规模为3个工件、3台机器的实例，其中数值表示工序操作的加工时间范围。图7-1描述了3个独立的数据结构，其中每个数据结构矩阵的长度都为9。第一个数据结构o包含了一个矩阵，其为［2，1，1，3，1，2，3，3，2］。它表示了一个工序序列，即O21—O11—O12—O31—O13—O22—O32—O33—O23。工序O21具有最高的优先级，它首先被加工，然后是工序O11被加工，以此类推。第二个数据结构u存储的是加工工序的机器编号。例如，机器1和机器2分别用来加工工序O11和O23。第三个数据结构v记录着来自数据结构u中每道工序的实际加工时间。

表7-1　所有工序操作的加工时间范围

图7-1　解表达式(www.daowen.com)

一个解的解码机制就是将每道工序分配在合适的机器上且以适当的加工时间进行加工。当一个解被解码时，数据结构o首先被转化为一个工序序列，然后根据数据结构u将每道工序分配到可选机器上，最后从数据结构v中获得对应的加工时间。调度通常被分为三类：非延迟调度、主动调度和半主动调度［26］。就规则目标而言，主动调度包含了一个最优调度方案。在本研究中，每一个解（病毒）被解码为一个主动调度。也就是说，只有当工件的先前工序都完工了，当前工序才能开始加工。机器k上的工序Oij在闲置时间区间［Sx，Ex］上是可用的（其中x表示机器加工工序Oij上的第x个闲置时间区间），需满足以下条件：

如果工序Oij可被插入可用闲置时间区间［Sx，Ex］，其开始时间是max｛Sx，Ci，j-1｝和Sx两者之一。如果在机器k上不存在任何可用闲置时间区间，则Oij被分配到机器k的末端。例如，图7-2展示了一个解（即图7-1）通过主动解码获得的甘特图。从图中可看出，相比半主动调度，主动调度可以获得一个较好的最大完工时间目标值。因此，本章采用了主动调度方式来对该调度问题进行解码。

图7-2　半主动调度和主动调度的甘特图