本系列为⾃⼰学习调度相关知识的记录，如有误请指出，也欢迎调度⽅向的⼩伙伴加我好友共同交流。
FJSP 的染⾊体编码
染⾊体编码是将所研究的问题的解⽤染⾊体的形式来表达的，这是遗传算法的关键。编码的⽬的是为了实现交叉、变异等类似于⽣物界的遗传操作。必须考虑染⾊体的合法性、可⾏性、有效性，以及对问题解空间表达的完全性。良好的编码⽅式可以在后续遗传操作中易产⽣可⾏解，提⾼执⾏效率；否则，经过遗传操作会产⽣不可⾏解，需要⼀定的修补措施，这样就降低了执⾏效率。染⾊体编码对求解速度、计算精度等有着直接的关系，对算法具有重要影响。
FJSP包括两个⼦问题：机器选择和⼯序排序。机器选择解决每道⼯序在可选机器集中的哪台机器上进⾏加⼯的问题；⼯序排序解决所有⼯序确定加⼯机器后的排序和开⼯时间问题。针对编码过程中对两个⼦问题编码处理的不同，⽬前主要有以下两种不同的编码⽅法。集成编码 集成编码染⾊体中的每⼀个基因位（h,j,i）代表⼀个⼯序任务，表⽰⼯件ｊ的第ｈ道⼯序在机器ｉ上加⼯，染⾊体总长度等于所有⼯件的⼯序总和。Kacem称为TSL（task sequencing list）或OLC（operat
ions list coding），Kacem和Zribi等在其⼀系列⽂献中均采⽤此编码⽅法。这种编码⽅法易于表达，但是每⼀个基因位包括信息过多，在必须满⾜⼯序约束的条件下进⾏遗传操作较为复杂，容易产⽣⾮法解。因此适应此编码⽅法的交叉和变异⽅法较少，不易改进提⾼。
分段编码
分段编码染⾊体有A/B两部分组成，将⼯序信息分开处理，分别代表FJSP的两个⼦问题，两部分染⾊体长度都等于。在有的⽂献中也称为双层编码或主副串编码，是⼀种较为常⽤的编码⽅式。Chen提出⼀种A/B编码，Ａ部分表⽰每道⼯序选择的机器，Ｂ部分表⽰机器上的⼯序编码，如此易产⽣⾮法解，使得需要采取修补措施修正⾮法解。余琦玮、杨晓梅、卢冰原和⾕峰等均采⽤染⾊体两层编码机制，只是在局部有所不同。Ho和Tay等对⼏种编码⽅式进⾏⽐较并且做了改进，取得了较好的效果，但是由于机器选择部分采⽤⼆进制数编码⽅法，使得求解效率不⾼。
FJSP包含T-FJSP和P-FJSP两种类型，染⾊体编码必须适应不同类型的问题.
结合分段编码易表现、易操作等特点，对以往编码⽅法进⾏了改进，设计了⼀种整数编码MSOS。由两部分组成：机器选择部分（machines selection MS）和⼯序排序部分（operations sequencing OS).此编码不但适合T-FJSP⽽且适合于P-FJSP。
如下为MSOS染⾊体结构：
1.机器选择部分
监控摄像机主板机器选择部分染⾊体长度为。每个基因位⽤整数表⽰，依次按照⼯件和⼯件⼯序的顺序进⾏排列，每个整数表⽰当前⼯序选择的加⼯机器在可选机器集中的顺序编号，并不是对应的机器号，这保证了后续交叉、变异等操作后产⽣的解仍然是可⾏解。这种编码不但适应T-
FJSP，⽽且更适合P-FJSP，对⼯序可选机器台数的多少没有要求，长度确定，操作⽅便。以往较多⽂献中求解P-FJSP时，需要先转换为T-FJSP，使得染⾊体中产⽣⼤量冗余信息，计算时间⼤幅度增加，计算效率降低。
以之前的P-FJSP为例，如下图所⽰依次是⼯件和⼯件的所有⼯序。⼯序有5台机器可以选择，对应的4表⽰可选机器集中第4台机器，即在机器上加⼯，同理，⼯序有2台机器可以选择，分别为机器和机器，图中对应的1表⽰可选机器集中的第1台机器，即在机器
上进⾏加⼯。
2.⼯序排序部分零时刻
T o T o T o J 1J 2O 11M 4O 12M 2M 1M 2
当⼯序的加⼯机器确定后，对⼯序的排序类似⼀般JSP。此部分采⽤Gen提出的基于⼯序的编码⽅式进⾏编码，染⾊体长度等于所有⼯件的⼯序之和。每⼀个基因⽤⼯件号直接编码，⼯件号出现的顺序表⽰该⼯件⼯序间的先后加⼯顺序，即对染⾊体从左到右进⾏编译，对于第ｈ次出现的⼯件号，表⽰该⼯件ｊ的第ｈ道⼯序，并且⼯件号的出现次数等于该⼯件的⼯序总数。如此编码柔性很⾼，可满⾜调度规模变化、⼯件⼯序数不定等各种复杂情况，⽽且任意置换染⾊体中的顺序后总能得到可⾏调度，在解码过程中可以产⽣活动调度.
如上图中，假设⼯序染⾊体为[2 2 1 1 2]，则其中第⼀个2表⽰⼯件的⼯序，第⼆个2表⽰⼯件的⼯序.依次类推，转换成各⼯件⼯序的加⼯顺序为FJSP 的染⾊体解码
解码运算并不是编码的简单反运算，按照不同的⽅法可以解码成活动调度、半活动调度和⾮延迟调度等类型。
1.调度类型
对于⼀个FJSP染⾊体，机器选择部分是确定的，⼯序排序部分存在⼤量的可⾏解，因为任意两道⼯序之间可以插⼊⽆限的闲置时间。在不考虑任何两道连续⼯序之间存在闲置时间的情况下，调度问题可以分为三种类型，它们的定义分别如下。活动调度（active schedule）在不推迟其他操作或破坏优先顺序的条件下，其中没有⼀个操作可以提前加⼯。半活动调度（semi-active schedule）在不改变机器上加⼯顺序的条件下，其中没有操作可以提前
⾮延迟调度（non-delay schedule）⾄少存在⼀个⼯件等待加⼯时，对应不存在相应处于空闲的机器。
三者包含关系如下：
活动调度集包含在半活动调度集中，也就是说：当调度处于⾮活动调度下，⼀定可以到某些⼯序，使其可以更早加⼯。例如在同⼀台机器上⼀个⼯序在前道⼯序完成后，可将其插⼊到同⼀台机器中⼯序时间⽐它早的另⼀个⼯序之前；换⾔之，就是插⼊到另⼀个⼯序还未开始加⼯前的空闲时间内。虽然⾮延迟调度集包含在活动调度集中，但不能保证包含最优解。对于正规调度性能指标，已经证明最
优调度必在活动调度集中。因此，对于正规调度性能指标在设计优化算法时，将搜索空间限于活动调度集中，不仅能够保证最优调度的存在，⽽且能够提⾼优化效率。但是对于⾮正规调度性能指标，如提前／拖期惩罚代价最⼩等调度问题，活动调度不能保证包含最优解，有可能最优解存在于半活动调度集中。本章中对于单⽬标的优化，均采⽤最⼤完⼯时间最⼩的正规调度性能指标，下⾯介绍FJSP染⾊
体如何解码成活动调度。
2.染⾊体解码
FJSP染⾊体MSOS由两部分组成，分别对它们进⾏解码，关键是需要将⼯序排序部分解码成对应于机器选择部分的活动调度，具体的解码步骤如下
感应式小便器
步骤1
对机器选择部分进⾏解码，从左到右依次读取并转换成机器顺序矩阵和时间顺序矩阵Ｔ。其中表⽰⼯件的⼯序的机器号，表⽰⼯件的所有⼯序按优先顺序加⼯的各个机器号的排列；表⽰⼯件的⼯序的加⼯时间。与的关系是⼀⼀对应的。
上图中机器选择部分【4 1 2 4 4】转换为机器顺序矩阵和时间顺序矩阵后为
表⽰⼯件的⼯序在机器上加⼯，表⽰⼯件的⼯序在机器上的加⼯时间为8。
步骤⼆
T o h j J 2O 21J 2O 22O −21−>O −22−>O −11−>O −12−>O 23
J ＭJ (j ,ｈ)ＭJ j O ｈJ (，∗)M J j Ｔ(j ,ｈ)J j O ｈJ (j ,ｈ)ＭＴ(j ，ｈ)J =M [43425]
T =[368
68]
J (1,2)=M 4J 1O 12M 2T (1,2)=8J 1O 12M 2
对⼯序排序部分的染⾊体从左到右依次读取。按照步骤１对应的机器顺序矩阵和时间顺序矩阵依次得
到每个⼯件⼯序对应的加⼯机器和加⼯时间，并对此⼯序进⾏排序得到调度结果。
下⾯是⼀种⼯序插⼊式⽅法，确保染⾊体解剖后产⽣活动调度。
（１）读取OS部分的⼀个基因，转换成相应⼯序。
（２）通过机器顺序矩阵和时间顺序矩阵Ｔ得到⼯序的加⼯机器和加⼯时间（３）如果⼯序在机器是第⼀道加⼯⼯序，那么直接从它的上道⼯序的结束时间开始加⼯即可。如果⼯序是⼯件的第１道⼯序，那么直接从机器的零时刻进⾏加⼯。否则，到机器上所有间隔空闲时间段，表⽰间隔时间段的开始时间，表⽰间隔空闲时间段的结束时间。按下式得到⼯序最早开始加⼯时间，能够满⾜⼯件加⼯⼯序的顺序约束。
（４）按下式1判断间隔空闲时间段是否满⾜插⼊条件，如满⾜则插⼊当前空闲时间段内，如图a所⽰；否则，按下式2的时间在机器上进⾏加⼯，其中表⽰当前机器最后⼀道⼯序的结束时间，如图b所⽰。
式1
式2
（５）判断OS部分的染⾊体是否读取完毕，如满⾜，则结束；否则，转(1)继续。
到此染⾊体解码完毕，⽣成活动调度。可以得到每个机器上⼯序的加⼯顺序和对应的开始时间、结束时间，即可画出调度⽢特图。对其进⾏操作可以得到相应的⽬标值，例如，对每台机器最后⼀道⼯序的完⼯时间进⾏⽐较，可得到最⼤完⼯时间。
FJSP 的初始化
O jh J M O jh M =i J (j ,h )M p =ijh T (j ,h )
O jh M i O j (h −1)O jh J j M i M i [TS ,TE ]i i TS i TE i O jh t a t =s maxc ,TS j (h −1)i
t b M i LM i M i t +a p ≤ijh TE i t =b max {c ,LM }j (h −1)i
种初始化在进化算法中是⼀个关键问题，初始解的质量对遗传算法求解的速度和质量有⾮常⼤的影响。FJSP不但要解决机器选择问题，还要解决所有⼯序排序问题。⽬前，⼤部分⽂献⼀般采⽤的是随机初始化⽅法，使得初始解的质量偏低，机器之间负荷不均衡，导致要增加迭代次数或种⼤⼩来达到最优解或近似最优解，这势必增加优化时间。
Kacem等提出利⽤分配时间表的AL（approach by localization）⽅法进⾏种机器选择的初始化，取得了⼀定的成效。然⽽，记录所有⼯序加⼯机器的时间表在不断复制、更新时加⼤了资源的消耗，增加了算法的复杂性。搜索机制是在所有的备选机器中选择最⼩的，虽然效果上有明显改善，但是搜索时间过长。并且它需要设置变量参数，将P-FJSP转换为T-FJSP，增加了⼤量冗余信息。以之前的为例，转换为T-FJSP如下表所⽰，表中的9999代表当前⼯序不能在当前机器上加⼯。Ho和Tay等利⽤经典JSP问题中的规则，提出混合规则启发式机器排序初始化⽅法（composite dispatching rues，CDRs）。Ho N.B.（２００５年）利⽤GP进⾏函数发现，形成更加复杂的组合规则，然⽽这些规则主要应⽤于⼯序排序的初始化，没有考虑机器选择问题。⽽对于FJSP，机器选择⽐⼯序排序要更为重要，
如何能较好地
考虑机器负荷平衡，是⾮常有意义的。
针对FJSP特点，结合以上⽅法的优点，下⽅是⼀种GLR机器选择⽅法，包括：全局选择(global selection GS)局部选择(local selection LS)和随机选择(radom selection RS).
GS和LS主要是为了考虑机器选择的负荷问题，使各台被选择的机器的⼯作负荷尽量平衡，充分提⾼机器的利⽤率。ＲＳ主要考虑尽量使初始种分散地分布于整个解空间。通过三者的有机结合，提⾼初始解在机器选择部分中解的质量。下⾯分别介绍三种选择⽅法的具体执⾏步骤。
全局选择双面粘合衬
设置⼀个数组，长度和机器数相等，数组的顺序依次对应加⼯机器的顺序，每⼀位上的值对应相应机器上的加⼯时间。随机在⼯件集中选择⼀个⼯件，从当前⼯件的第１道⼯序开始，将当前⼯序的可选加⼯机器的加⼯时间加上数组中对应的时间。从中选择最短的时间作为当前⼯序的加⼯机器，并且将数组更新，即把被选择的加⼯机器的加⼯时间加到数组中相应的位置上，以此类推，直到当前⼯件的所有⼯序的加⼯机器选择完毕后，然后再随机选择⼀个⼯件开始，直到所有⼯件的⼯序选择完毕为⽌。这样保证了最短加⼯机器先被选到⽽且保证了加⼯机器上的⼯作负荷平衡。具体执⾏步骤如下。
步骤１设置⼀个整型数组，长度等于机器总数ｍ，依次为机器号顺序，数组对应机器上的总负荷。同时初始化数组中每⼀个元素值为零。步骤２随机从⼯件集中选择⼀个⼯件，同时选择当前⼯件的第１道⼯序。步骤３将当前⼯序的可选加⼯机器集中的加⼯机器的加⼯时间和数组中相应机器位置的时间数值相加，但不更新数组。
步骤４从相加后的时间值中，选择最⼩的那台机器作为当前⼯序的加⼯机器，将被选的机器在可选机器集中的顺序号设置为ＭＳ部分相应基因位的值。步骤５将当前被选择的加⼯机器的加⼯时间加到数组中相应位置机器的加⼯负荷中，同时更新数组作为下⼀次选择的依据。步骤６选择当前⼯件的下⼀道⼯序，重复执⾏步骤３到步骤５，直到当前⼯件的所有⼯序的加⼯机器选择完毕为⽌。
步骤７从⼯件集中除去已被选择的⼯件，从剩下的⼯件集中随机选择⼀个⼯件，同时选择当前⼯件的第１道⼯序，重复执⾏步骤３到步骤６，直到⼯件集中的所有⼯件被选择完毕为⽌.
刮膜棒
以前例来说，假设第⼀次随机选择到的加⼯⼯件是⼯件，第⼆次选择⼯件
，则前四道⼯序的执⾏过程如下图所⽰。
[M ,M ...M ]12m J 1J 2
局部选择
局部选择同全局选择原理上基本⼀致，但是每次对⼀个⼯件选择完毕时，数组需要重新设置为零，不存在随机选择⼯件。设置⼀个数组，长度和机器数相等，选择⼯件集中第１个⼯件，选择当前⼯件的第１道⼯序开始，将当前⼯序的可选加⼯机器的加⼯时间加上数组中对应的时间。从中选择最短的时间作为当前⼯序的加⼯机器，并且将数组更新，即把被选择的加⼯机器的加⼯时间加到数组中相应的位置上，以此类推，直到当前⼯件的所有⼯序的加⼯机器选择完毕后，然后数组每⼀位重新设置为零，
选择下⼀个⼯件，直到所有⼯件选择完毕为⽌。这样保证了⼀个⼯件的⼯序中优先加⼯时间最短或说选择机器负荷最⼩的加⼯机器进⾏加⼯。具体执⾏步骤如下
步骤１设置⼀个整型数组，长度等于机器总数ｍ，依次为机器号顺序，数组对应机器［Ｍ１，Ｍ２，…，Ｍｍ］上的总负荷。同时初始化数组中每⼀个元素值为零。步骤２选择⼯件集中的第１个⼯件，同时选择当前⼯件的第１道⼯序。步骤３将当前⼯序的可选加⼯机器集中的加⼯机器的加⼯时间和数组中相应机器位置的时间数值相加，但不更新数组。
步骤４从相加后的时间值中，选择最⼩的那台机器作为当前⼯序的加⼯机器，将被选的机器在可选机器集中的顺序号设置为ＭＳ部分相应基因位的值。步骤５将当前被选择的加⼯机器的加⼯时间加到数组中相应位置机器的加⼯负荷中，同时更新数组作为下⼀次选择的依据。步骤６选择当前⼯件的下⼀道⼯序，重复执⾏步骤３到步骤５，直到当前⼯件的所有⼯序的加⼯机器选择完毕为⽌。步骤７将数组中的每⼀位元素的值重新设置为零。单元测试流程
步骤８从⼯件集中除去已被选择的⼯件，选择⼯件集中下⼀个⼯件，同时选择当前⼯件的第⼀道⼯序，重复执⾏步骤３到步骤７，直到⼯件集中的所有⼯件被选择完毕为⽌。
以前例为⽰，依次选择⼯件和⼯件，那么⼯件
的三道⼯序的加⼯机器的选择执⾏过程如下：
3.随机选择
为保证初始种的多样性，初始种应分散于解空间。⼀部分种的机器选择部分采⽤随机初始化⽅法。RS与GS、LS的主要区别在于每⼀个基因位上的数字即表⽰⼯序可选机器集中的顺序号是随机产⽣的。具体执⾏步骤如下。步骤１选择⼯件集中的第１个⼯件，同时选择当前⼯件的第１道⼯序。
步骤２在区间内随机产⽣⼀个数，即从当前⼯序的可选加⼯机器集中随机选择⼀个机器；同时将产⽣的随机数设置为MS染⾊体部分相应基因位的值。步骤３选择当前⼯件的下⼀道⼯序，执⾏步骤２，直到当前⼯件的所有⼯序的加⼯机器选择完毕为⽌。
步骤４选择⼯件集中的下⼀个⼯件，重复执⾏步骤２到步骤３，直到⼯件集中的所有⼯件被选择完毕为⽌。
每个染⾊体的OS部分采⽤随机的⽅法⽣成。
交叉操作
交叉的⽬的是利⽤⽗代个体经过⼀定操作组合后产⽣新个体，在尽量降低有效模式被破坏的概率基础上对解空间进⾏⾼效搜索。交叉操作是主要的遗传操作，ＧＡ的性能在很⼤程度上依赖于所使⽤的交叉操作，它决定了ＧＡ的全局搜索能⼒。在设计交叉操作时必须满⾜可⾏性、特征的有效继承性、完全性和信息⾮冗余性等指标。特征的有效继承性保证⽗代中的优良信息能够保留到⼦代；信息⾮冗余性保证⼦代中不会产⽣过多⽆⽤信息，这两个特征在交叉操作设计中是两个重要的指标。ＧＡ中较常见的交叉操作有单点交叉（single point
crossover，SPX）、多点交叉（multiple point crossover，MPX）、均匀交叉（uniform crossover，UX）、部分映射交叉
（partially mapping crossover，PMX）、次序交叉（order crossover，OX）、线性次序交叉（linear order crossover，LOX）、基于位置的交叉（position-based crossover，ＰＸ）、循环交叉（cycle crossover，CX）、基于⼯件顺序的交叉（job-based order crossover，JOX）和基于⼯件优先顺序的交叉（precedence preserving order-based crossover，POX）等。J 1J 2J 1[1,m ]jh
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议