（一）問題描述
設FS由包括m個加工階段，每個加工階段都隻有1台設備，共加工n個工件，所有工件的加工工藝相同。要求確定工件在各台設備上的分配以及排序情況，使這批工件的加工流程時間Cmax最少。
流水作業計劃問題FSP（flowshopschedulingproblem）可用2個工件、2台設備建立非連接圖模型。圖中N代表非連接圖的起點，F代表終點，節點1，2代表設備號。始於N點的起始弧連接對應所有工件的節點1，對應所有工件的節點2又有結束弧指向終點F，起始弧與結束弧均為單向連接弧。尋徑時，這些單向連接弧中將隻有一條被選擇，被選擇的起始弧指向的節點1對應的工件即為第一個被加工的工件，被選擇的結束弧指向的節點2對應的工件即為最後一個被加工的工件。
同一節點對於不同工件存在雙向連接弧，表示各個工件在該階段的可能順序關係。對工件排序時，需要將雙向連接弧明確為單向連接弧，即明確各工件在該階段的實際加工順序。上述雙向連接弧與單向連接弧存在相互約束關係，具體反映在ACO算法的allowedk中。
（二）所用算法
Makespan指標下的3階段以上FSP問題已被證明為NP完全問題。對於FSP問題，本書將給出GA算法和ACO算法。隻要確定了GA算法的算子和ACO算法的allowedk，則GA.CO算法以及HACO算法即可按第3章的方法構建。
染色體按基於工件編碼方法采用自然數編碼，自然數範圍為［1，n］。一條染色體具有m×n位基因，記為：
A=［a11a12…a1na21a22…a2n…am1am2…amn］。
從第一位開始，每n位基因相互不重複，代表各階段n個工件在設備上的排列情況。
上述編碼方法舉例如下：對於包含兩台設備加工4個工件的FSP問題，其GA算法的一條染色體為A=［24313421］，其表示在第一階段工件加工順序為4，2，3，1；在第二階段工件加工順序為3，4，2，1。其對應的作業計劃，該作業計劃又直接對應ACO算法的一種路徑。由此，即可建立GA算法染色體與ACO算法路徑之間的聯係。
交叉操作采用多段交叉法進行。對選定的一對父代染色體，在1～n範圍內按升序產生偶數個整數，將其兩兩配對，將每對數字在兩個父代染色體上對應的基因位之間的基因進行交叉。同時應使染色體合法，即代表一個階段內加工工件的基因不能重複。對於一個具有2個階段用於加工4個工件的FSP問題，染色體交叉操作的一個例子如下：兩個父代染色體為A，B，在其中任選對應的兩組基因進行交叉後得到兩個子代染色體a，b。
變異操作采用單親染色體代表同一階段的任意兩對自然數基因互換的方法進行。按一定變異概率選取父代染色體，任意選定兩個基因交換，即得到子代染色體。例如，父代染色體A=［24313421］，將其任意兩個實數基因進行互換，得到子代染色體a=［34213421］。
對於所研究的FSP問題，應用ACO算法時螞蟻在各節點的allowedk確定如下：在起點N，每個螞蟻的allowedk中有對應工件數的n條路徑。按輪盤賭方法選擇其中一條路徑，那麼該螞蟻對應工件首先進入第一階段設備進行加工。
螞蟻尋徑過程中需將節點之間的雙向連接弧明確為指入連接弧和指出連接弧，指入連接弧表示螞蟻從其他節點尋徑至該節點；指出連接弧則反之。當螞蟻尋徑至上述節點中的某一個時，該節點處的allowedk將包含指向這些節點中該螞蟻未經曆節點的路徑。當螞蟻完成對某節點尋徑後，該節點將隻存在指入連接弧和指出連接弧各一個。在滿足運算結束條件前，螞蟻將進行新一代尋徑，即n個螞蟻再次從起點N出發時，所有節點的allowedk清零。