（一）問題描述
在實際生產中，經常出現多條同類流水線平行布置，且中間存在交叉點的情形。以某造船企業平直分段生產中心為例，其裝有兩條平行流水線，在流水線的中間位置有一交叉點將流水線分為兩段，交叉點處工件可在兩條流水線之間橫向流動以提高設備利用率，減少在製品數量，縮短工件生產周期。通過國內外文獻調研，未見對這種作業方式的研究，因此，本書命名其為網狀流水車間作業計劃問題CFSP（crossedflowshopschedulingproblem）［143］。采用傳統方法對CFSP進行的作業計劃是對每條流水線做獨立的調度，而不考慮其交叉情況。如此，盡管對每條流水線達到了作業計劃的優化，但並沒有實現CFSP的整體優化，仍然存在少數設備利用率不高、工件加工流程時間較長的問題。尤其在當前客戶對產品個性化要求越來越高的環境下，流水線上的產品品種日趨多樣化，其生產不均衡現象更加明顯。因此，更應該將CFSP進行整體調度，最大程度地減少設備空閑等情況的發生。
CFSP問題可用2個工件4個階段建立多級非連接圖模型。其包含4個階段，前2個階段包含兩條平行流水線，後2個階段也包含兩條平行流水線。
始於N點的起始弧連接第一階段對應所有工件的PN，所有最後階段的PN用結束弧指向終點F，起始弧與結束弧均為單向連接弧。同一PN對於不同工件存在雙向連接弧，表示各個工件在該階段的可能順序關係。對工件排序時，需要將雙向連接弧明確為單向連接弧，即明確各工件在該階段的實際加工順序。前一階段對應所有工件的PN，均有指向後一階段各PN的單向連接弧。上述雙向連接弧與單向連接弧存在相互約束關係，具體反映在ACO算法的allowedk中。當某PN被選擇後，需進一步在第二級非連接圖中對其代表的平行流水線進行尋徑，即從平行流水線中選擇一條用於工件的加工。
（二）所用算法
本書分別應用GA算法、ACO算法、GA.ACO算法和HACO算法進行CFSP問題求解，並對比這些算法應用於該問題時的性能。隻要確定了GA算法的算子和ACO算法的allowedk，則GA.ACO算法以及HACO算法即可按第3章的方法構建。
本問題采用GA算法進行調度。但由於CFS內在的工件交叉流動及工件加工順序在流水線各段不可顛倒的特性，傳統的用於單條流水線作業計劃的GA算法已無法滿足CFS作業計劃的要求，需對其進行改進。根據CFS作業計劃的需要，本書對傳統GA算法在編碼方法、遺傳操作、適應值計算和優化過程等方麵進行了改進。
由於CFS由交叉點分離成多段，每段流水線上工件的排列可能發生變化，其對應的染色體也將相應改變。因此，本書提出了多階段編碼方法，其階段數與流水線段數相等，多階段染色體組合構成一條總染色體。各階段染色體按多條流水線交叉編碼規則進行編碼，染色體的基因采用非負整數。具體編碼過程如下：對第一階段染色體，先用自然數編碼，然後在該階段染色體的隨機位置加入v個“虛基因”，令其值為0，本書稱其他非零的基因為實基因。對應n個工件，各階段染色體有n個實基因，故第一階段染色體具有n+v位基因，即1，2，…，L，L+1，L+2，…，2L，…，kL+1，kL+2，…，n+v，允許n+v不等於L的整數倍。在染色體中，1，L+1，…，kL+1位基因代表在第一條流水線（流水線A）上加工的工件號或“虛基因”。依此類推，可得到其他流水線上加工的工件號或“虛基因”，即每條階段染色體可以按交叉編碼規則分解成L條階段染色體片段。去除這些階段染色體片段中的“虛基因”後得到的實基因染色體片段集S1={s11，s12，…，s1L}，即為本階段各流水線上加工的工件號及其加工順序。後續階段染色體根據前一階段實基因染色體片段產生。設CFS中，第i-1段至第i段有Li條流水線交叉，則將與該Li條流水線對應的實基因染色體片段按交叉編碼規則組合，若組合前各染色體片段長度不等，則在短的片段後部添加“虛基因”，使所有片段等長。
對上述編碼方式舉例。設CFS對5個工件進行加工，第一段有3條流水線參與交叉。先隨機產生一實基因染色體13452，然後在實基因染色體的任意v個位置加入“虛基因”（此處v取3），得到第一階段染色體13040520，將其按交叉編碼規則分解成3條染色體片段為：142，300和05，其實基因片段集為｛142，3，5｝，表示工件1、4、2按序在流水線A加工等。CFS第一階段至第二階段有3條流水線參與交叉，第二階段染色體產生過程，先將第一階段實基因染色體片段等長化，即在實基因片段3，5後加“虛基因”0，使3條染色體片段均有3個基因。將上述3條染色體片段按交叉編碼規則整合為：135400200。