（一）問題描述
在含多功能機床的製造係統中，如果麵向一批工件將多功能機床確定為以一種功能工作，不能使各階段的機床利用率保持在較高水平，且機床在不同功能之間的變換調整時間較小。此時，應發揮多功能機床的通用性，使用多種功能用於同一批工件的加工。
本書的研究對象為MFM環境下非排列排序HFSP作業方式，即各階段工件的加工順序可以顛倒。工件在同一階段並行機上的加工時間可以不同。對問題約束條件如下：每個工件包含若幹個操作；每個操作必須在特定的階段進行；所有操作的加工時間確定；各階段工件在並行機上的加工時間可能不同；每個工件在每個階段最多加工一次；工件沒有優先級；每台機床同時隻能加工最多一個工件；在調度開始時刻所有工件均已準備就緒；在機床之間存在無限緩衝區。
HFSP.MFM問題可用2個工件3個階段建立多級非連接圖模型如圖4.16所示。假定該車間內有3台機床，加工2個零件，每台機床都有兩個功能，可用於兩個階段的加工，而相應地，每個階段也都有兩台機床可供使用。圖中，N代表起點，F代表終點，節點1、2代表設備號，設備號的下標表示該設備用於哪個階段，如數字12表示機床1用於階段2的加工；在模型的第一級內，由多功能機床構成的並行機用一個階段節點PN。當某一階段存在並行機時，該PN內將包含代表這些並行機的機床節點，如圖4.16中第一階段的11、21。
始於N點的起始弧連接第一階段對應所有工件的PN，所有最後階段的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=［a11f11a12f12…a1nf1n…ai1fi1ai2fi2…ainfin…aM1fM1aM2fM2…aMnfMn］。每條染色體共有2×n×M位基因。其中aij表示第i階段排序為j工件的工件號，fij表示第i階段排序為j工件的加工設備號。根據要求有
fij≤flii=（1，2，…，M），j=（1，2，…，n）（4.5）