由於造船企業IS.SIP問題中包含各種基本作業方式，為了更加清晰地描述IS.SIP問題，本書先介紹對應並行機作業IPM（identicalparallelmachine）、流水作業FS（flowshop）、異順序作業JS（jobshop）、混雜流水作業HFS（hybridflowshop）和開放作業OS（openshop）等基本作業方式的作業計劃方法。本書給出這些基本作業方式的非連接圖模型以及GA算法、ACO算法設計方法，以便於為後續IS.SIP問題的研究打好基礎。由於上述基本作業方式已有很多算例研究，本書隻對這些算例研究做一總體介紹，而不再進行新的算例研究。
並行機作業計劃方法
（一）問題描述
設IPM由M台相同的並行機構成，共加工n個工件，每個工件在並行機上的加工時間相同。要求確定工件在各台設備上的分配以及排序情況，使這批工件的加工流程時間Cmax最少。
並行機作業計劃問題IPMP（identicalparallelmachineschedulingproblem）可用2個工件2台設備建立多級非連接圖模型，如圖4.1所示。非連接圖模型是以簡潔的圖示形式表達製造係統作業計劃的工件、設備、時間等約束。圖中N代表非連接圖的起點，F代表終點，節點1、2代表設備號。在模型的第一級內，並行機用一階段節點PN（phasenode）代表。始於N點的起始弧連接對應所有工件的PN，對應所有工件的PN又有結束弧指向終點F，起始弧與結束弧均為單向連接弧。尋徑時，這些單向連接弧中將隻有一條被選擇。被選擇的起始弧指向的PN對應的工件即為第一個被加工的工件，被選擇的結束弧指向的PN對應的工件即為最後一個被加工的工件。
同一PN對於不同工件存在雙向連接弧，表示各個工件在該階段的可能順序關係。對工件排序時，需要將雙向連接弧明確為單向連接弧，即明確各工件在該階段的實際加工順序。上述雙向連接弧與單向連接弧存在相互約束關係，具體反映在ACO算法的allowedk中。當某PN被選擇後，需進一步在第二級非連接圖中對其代表的並行機進行尋徑，即從並行機中選擇一台用於工件的加工。
（二）所用算法
Makespan指標下的並行機作業計劃問題已被證明為NP完全問題。對於IPM問題，本書將給出GA算法和ACO算法。隻要確定了GA算法的算子和ACO算法的allowedk，則GA.ACO算法以及HACO算法即可按第3章的方法構建。
GA算法
染色體按基於工件編碼方法采用實數編碼，實數範圍為（1，M＋1）。一條染色體具有n位基因，記為：A=［a1a2…an］。第i（i∈{1，2，…，n}）位基因代表第i個工件在並行機上的分配及加工排列順序，各基因的整數部分Int（ai）表示該基因所代表工件進入的設備號，具有相同整數部分基因代表的工件進入同一台設備，這些工件在該生產線第一階段的加工順序按其基因小數部分的升序排列。若代表在同一台設備上加工兩個工件的基因值相等，則按輪盤賭方法確定上述兩個工件的加工順序，並相應減小先加工工件對應的基因值，或增大後加工工件對應的基因值，但這些基因值的變化不應改變原定的工件加工順序。上述編碼方法使工件在所有並行機上的分配都有隨機性，可望實現全局尋優。