（一）問題描述
本書的研究對象為非排列排序HFSP作業方式，即各階段工件的加工順序可以顛倒。工件在同一階段並行機上的加工時間相同。
HFSP問題可用2個工件、2個階段建立多級非連接圖模型，如圖4.7所示，其中第一階段存在2台並行機，第二階段隻有1台設備。圖中，N代表起點，F代表終點，節點1、2代表階段號，階段號的下標表示該階段的並行機號，如數字12表示階段1的並行機2；在模型的第一級內，包含並行機的階段用一個階段節點PN代表，該PN節點內將包含代表這些並行機的機床節點，如圖4.7中第一階段的11、12。
始於N點的起始弧連接第一階段對應所有工件的PN，所有最後階段的節點用結束弧指向終點F，起始弧與結束弧均為單向連接弧。同一PN（或設備節點）對於不同工件存在雙向連接弧，表示各個工件在該階段的可能順序關係。對工件排序時，需要將雙向連接弧明確為單向連接弧，即明確各工件在該階段的實際加工順序。前一階段對應所有工件的PN均有指向後一階段各PN（或設備節點）的單向連接弧。上述雙向連接弧與單向連接弧存在相互約束關係，具體反映在ACO算法的allowedk中。當某PN被選擇後，需進一步在第二級非連接圖中對其包含的並行機進行尋徑，即從並行機中選擇一個設備用於工件的加工。
（二）所用算法
本書分別應用GA算法、ACO算法、GA.ACO算法和HACO算法進行HFSP.MFM問題求解，並對比這些算法應用於該問題時的性能。隻要確定了GA算法的算子和ACO算法的allowedk，則GA.ACO算法以及HACO算法即可按第3章的方法構建。
由於本書考慮非排列排序加工方式，因此需在每個加工階段對工件進行排序和分配設備。反映在編碼方法上，即為對每個階段表示工件的所有基因進行一次排序，將全部階段的基因按順序連接起來，即可得到工件在各階段並行機上的分配及其加工順序。通過每階段工件加工順序的隨機性以及工件在並行機上分配的隨機性，達到在解空間內全局搜索的目的。
針對n個工件m道加工階段的流水作業，每條染色體可以向量形式表達，記為：A=［a11a12…a1n…ai1ai2…ain…am1am2…amn］。每條染色體共有n×m位采用實數與整數混合編碼的基因，當某階段存在並行機時，采用實數編碼；反之，若無並行機，則采用整數編碼。即aij表示第i階段排序為j工件的工件號，若第i階段存在並行機，則代表該階段排序為j工件的基因為實數aij，其整數部分為工件號，小數部分為並行機號。注意小數部分的數字不大於該階段的並行機數。具體編碼方法詳見IPM問題。
現以2階段3個工件的HFSP為例說明上述編碼方法：假定第一階段存在2台並行機，第二階段隻有一台設備。那麼由上述編碼方法得到的一條可行染色體為A=［112132312］，其表示：第一階段工件1，2按序在並行機1加工，工件3在並行機2加工；第二階段工件加工順序為3、1、2。其對應的作業計劃，該作業計劃又直接對應ACO算法的一種路徑。由此，即可建立GA算法染色體與ACO算法路徑之間的聯係。
以概率pc隨機選取偶數個父代染色體，將其兩兩配對後按單點交叉法進行交叉操作。由於染色體采用十進製整數編碼，交叉操作後可能出現非法染色體。對於染色體中第i段所有代表工件的基因aij（j=1，2，…，n）應遍曆加工的工件號（1，2，…，n）。但經過交叉操作後，交叉點所在階段的基因aij（j=1，2，…，n）可能出現重碼和缺碼。為避免產生非法染色體，對基因aij（j=1，2，…，n）的交叉操作可采用非常規碼常規交叉法［108］。
仍以2階段3個工件的HFSP為例進行說明：其染色體包括兩個階段共6個基因。假定選取的兩條可行染色體為A=［112132312］；B=［211231123］。設交叉位置為4，位於第二加工階段，即染色體的［4，6］基因區域內。交叉操作時，第二階段基因aij（j=1，2，…，n）采用非常規碼常規交叉法。交叉過程如下：
A=［112132312］
B=［211231123］A′=［112132312］
B′=［211231132］
3.變異操作
以概率pb隨機選取父代染色體，采用兩點內基因倒排的方式對每個父代染色體進行變異操作。先在父代染色體中隨機選取一點，第二點的位置為第一點所在階段全部基因之後。因變異操作在染色體同一階段內進行，可避免出現非法染色體。以上述染色體A為例，設隨機變異點為1，位於第一加工階段，即染色體的［1，3］基因區域內，則第二變異點為3，變異過程如下：
A=［112132312］A′=［113221312］
ACO算法流程參見第3章。對於本問題，確定螞蟻在各節點的allowedk如下：螞蟻k在某PN處的allowedk包含從本節點到所有可行PN的路徑。尋徑時，該螞蟻根據此節點allowedk中各路徑的選擇概率，通過輪盤賭方法確定一條路徑，到達下一個PN。
從起點N出發後，每隻螞蟻逐階段通過所有PN搜索路徑，即在完成前一階段的所有PN搜索後，再進行後一階段所有PN的搜索。當一隻螞蟻通過某個PN時，如果該PN中包含多個機床節點，按路徑選擇概率選取其中的一個機床節點，其表示相應工件在該節點指代的機床上加工。
圖4.7中，在起點N處的allowedk中包含對應2個工件的2條路徑，根據每條路徑的尋徑概率選擇其中一條路徑。螞蟻到達這條路徑上第一階段的PN，該PN對應的二級非連接圖中包含兩個機床節點，按路徑選擇概率選取其中一個機床節點，螞蟻便完成了該PN的尋徑。按同樣方法依次對本階段各PN進行尋徑，此時，本階段各PN指向下一階段各PN的單向弧被屏蔽。一隻螞蟻完成一個階段內所有PN尋徑後，最後一個PN的allowedk中將包含所有指向後一階段各PN的路徑。從中確定一條路徑，則螞蟻進入下一階段。重複以上過程，直至完成全部螞蟻對所有PN的尋徑。在滿足運算結束條件前，螞蟻將進行新一代尋徑，即h個螞蟻再次從起點N出發，同時，所有PN的allowedk需重新設置。
（三）算例研究
HFSP問題專門用於生產作業計劃的算例較少，文獻［133］提出了一個算例，其makespan的下界為29。研究中經常采用FSP典型算例的數據，然後假定每個階段各有若幹台並行機。此外，還采用設定階段數及各階段並行機數，隨機產生工件在各階段的加工時間的辦法。