19七月2023生產作業計劃與排序一、基本概念1、排序排序就是要將不同的工作任務安排一個執行的順序，使預定的目標最優化。實際上就是要解決如何按時間的先后，將有限的人力、物力資源分配給不同工作任務，使預定目標最優化的問題。排序的作用實例1：油漆生產順序某企業生產白、灰、紅、藍四種油漆，每次生產前都有清洗容器的調整準備時間。按怎樣的順序，總的調整準備時間最少？實例2：復印排序問題有四人同時到達復印室，每人的復印量不同，如何安排順序，使得他們的平均等待時間和平均流程時間最小？方案1：白-灰-紅-藍T-setup=12

方案2：藍-紅-灰-白T-setup=20

按最短工時優先原則（SPT）,結果最優。一、基本概念排序中常用的幾個概念工件（Job）：服務對象；機器（Machine、Processor）：服務者。如：n個零件在機器上加工，則零件是工件，設備是機器；工人維修設備，出故障的設備是工件，工人是機器。一、基本概念

作業排序也就是要確定工件在機器上的加工順序，可用一組工件代號的一種排列來表示。如，用（1，6，5，4，3，2）表示加工順序：J1—J6—J5—J4—J3—J2。一、基本概念2、作業計劃（Scheduling）作業計劃與排序不是一回事，它不僅要確定工件的加工順序，而且還要確定每臺機器加工每個工件的開工時間和完工時間。如果按最早可能開（完）工時間來編排作業計劃，則排序完后，作業計劃也就確定了。一、基本概念3、排序問題的分類與表示1）單臺機器與多臺機器的排序問題。2）流水車間與單件車間排序問題。排序問題的分類單機排序和多機排序：按設備的種類和數量：單目標排序和多目標排序：按目標函數的性質流水型與非流水型排序：按工件加工路線的特征（加工路線是否相同）

同順序排列（P）

一般流水型(F):流水車間(Flow-shop)

非流水型(G):單件車間(Job-shop)一、基本概念流水車間排序問題的基本特征：每個工件的加工路線都一樣。如車—銑—磨。這里指的是工件的加工流向一致，并不要求每個工件必須在每臺機器上加工。如有的工件為車—磨，有的為銑—磨。不僅加工路線一致，而且所有工件在各臺機器上的加工順序也一樣，這種排序稱為排列排序（同順序排序）。如工件排序為：J1—J3—J2，則表示所有機器都是先加工J1，然后加工J3，最后加工J2。一、基本概念單件車間排序問題的基本特征：每個工件都有其獨特的加工路線，工件沒有一定的流向。一、基本概念3）表示方法一般正規的表示方法為：n/m/A/Bn：工件數；m：機器數；A：車間類型（F、P、G）；

同順序排列（P）一般流水型(F):流水車間(Flow-shop)非流水型(G):單件車間(Job-shop)B：目標函數加工周期交貨期總費用一、基本概念

4）一般來說，排列排序問題的最優解不一定是相應流水車間排序問題的最優解，但一般是比較好的解。而對于僅有2臺或3臺機器的情況，則排列排序問題的最優解一定是相應流水車間排序問題的最優解。符號說明Ji------工件iMj------機器jpij------工件i在機器j上的加工時間,Pi------工件i總的加工時間Pi=pijri------工件i的到達時間di------工件i的完工期限

wij-----工件i在第j道工序的等待時間Wi------工件i總的等待時間Wi=wijCi------工件i的完工時間Ci=ri+Wi+PiFi------工件i的流程時間Fi=Ci－ri=Wi+PiLi------工件i的延遲時間Li=Ci－di

一、基本概念4、排序問題的假設條件一個工件不能同時在幾臺不同的機器上加工。工件在加工過程中采取平行移動方式。不允許中斷。每道工序只在一臺機器上完成。每臺機器同時只能加工一個工件。工件數、機器數和加工時間已知，加工時間與加工順序無關。二、最長流程時間最長流程時間（加工周期）：從第一個工件在第一臺機器上加工起到最后一個工件在最后一臺機器上加工完畢為止所經過的時間。假定所有工件的到達時間都為0，則Fmax等于排在末位加工的工件在車間的停留時間。二、最長流程時間計算Fmax的幾個假定條件：機器M1不會發生空閑；對其它機器，能對某一工件加工必須具備2個條件：機器必須完成排前一位的工件的加工；要加工的工件的上道工序已經完工。二、最長流程時間二、最長流程時間ipi1pi2pi3pi4615243255144544453258217533674261012131671115202733121722303542132125323846三、n/2/F/Fmax問題的算法Johnson算法：假定：ai為工件Ji在機器M1上的加工時間，bi為工件Ji在機器M2上的加工時間，每個工件按M1—M2的路線加工。三、n/2/F/Fmax問題的算法Johnson算法的步驟：從加工時間矩陣中找出最短的加工時間。若最短時間出現在M1上，則對應的工件盡可能往前排。若最短時間出現在M2上，則對應的工件盡可能往后排。若最短時間有多個，則任選一個。劃去已排序的工件。若所有工件都已排序，則停止，否則重復上述步驟。n/2/F/Fmax流水型排序

（1）按約翰遜-貝爾曼規則排序，得到2--6--3--5--4--1（2）列表計算流程時間四、一般n/m/P/Fmax問題的啟發式算法

對于一般的n/m/P/Fmax問題，可以用分支定界法求得最優解，但計算量很大。實際中，可以用啟發式算法求近優解。四、一般n/m/P/Fmax問題的啟發式算法1、Palmer法計算工件斜度指標i：m:機器數pik：工件i在機器k上的加工時間。M=3i=-pi1+pi3

M=4i=-1.5pi1-0.5pi2+0.5pi3+1.5pi4排序方法:按i從大到小的順序排列。按排序的順序計算Fmax四、一般n/m/P/Fmax問題的啟發式算法2、關鍵工件法：計算Pi=Pij，找出Pi最長的工件，將之作為關鍵工件C。對其余工件，若Pi1≤Pim，則按Pi1由小到大排成序列SA。若Pi1>Pim，則按Pim由大到小排成序列SB。順序（SA，C，SB）即為近優解。四、一般n/m/P/Fmax問題的啟發式算法得到的加工順序為(1，2，3，4)四、一般n/m/P/Fmax問題的啟發式算法3、CDS法：CDS法是Johnson算法的擴展方法，從M-1個排序中找出近優解。四、一般n/m/P/Fmax問題的啟發式算法L＝1，按Johnson算法得到加工順序(1，2，3，4)，Fmax＝28L＝2，按Johnson算法得到加工順序(2，3，1，4)，Fmax＝29取順序(1，2，3，4為最優順序。問題描述流水(i,j)(工件，工序)單件(i,j,k)(工件，工序，機器)加工描述矩陣和加工時間矩陣

五、單件車間排序問題（n/m/G/Fmax）五、單件車間排序問題（n/m/G/Fmax）1、問題描述(i，j，k)：表示工件i的第j道工序是在機器k上進行。加工描述矩陣D：每一行描述一個工件的加工，每一列的工序序號相同。D=1,1,11,2,31,3,22,1,32,2,12,3,2五、單件車間排序問題（n/m/G/Fmax）加工時間矩陣T：與D相對應。D=1,1,11,2,31,3,22,1,32,2,12,3,2T=463574五、單件車間排序問題（n/m/G/Fmax）加工順序矩陣S：每一行與機器相對應，每一列與工件相對應。D=1,1,11,2,31,3,22,1,32,2,12,3,2S=1,1,12,2,11,3,22,3,22,1,31,2,3五、單件車間排序問題（n/m/G/Fmax）用方塊圖表示：D=1,1,11,2,31,3,22,1,32,2,12,3,2S=1,1,12,2,11,3,22,3,22,1,31,2,3T=4635741,1,12,1,31,2,32,2,11,3,22,3,2M1M2M3五、單件車間排序問題（n/m/G/Fmax）2、能動作業計劃的構成各工序都按最早可能開(完)工時間安排且任何一臺機器的每段空閑時間都不足以加工一道可加工工序。符號說明：{Ot}第t步可以排序的工序的集合{St}t步之前已排序的工序構成的部分作業計劃Tk{Ot}中工序Ok的最早可能開工時間T’k{Ot}中工序Ok的最早可能完工時間五、單件車間排序問題（n/m/G/Fmax）能動作業計劃的構成步驟：①設t＝1，{St}為空，{Ot}為各工件第一道工序的集合。②求最小的最早完工時間T*=min{T’k},并找到出現T*的機器M*，若有多臺，任選一臺。③從{Ot}中跳出滿足以下兩條件的工序Oj需要機器M*加工；Tj<T*④將確定的Oj放入{St}，從{Ot}中消去Oj并將Oj的緊后工序放入{Ot}中，使t=t+1。⑤若還有未安排的工序，轉步驟②；否則，停止。一個實例：D=1,1,11,2,31,3,22,1,32,2,12,3,2T=241345i1{Ot}TkT’kT*M*Oj1,1,1022M11,1,12,1,30321,2,3263M32,1,32,1,30331,2,3377M31,2,32,2,13741,3,2787M12,2,12,2,13751,3,2788M21,3,22,3,2712613M22,3,22,3,2813得到加工順序矩陣：S=1,1,12,2,11,3,22,3,22,1,31,2,31,1,12,1,31,2,32,2,11,3,22,3,2M1M2M323773813五、單件車間排序問題（n/m/G/Fmax）3、無延遲作業計劃的構成沒有任何延遲出現的能動作業計劃。所謂“延遲”，指有工件等待加工時，機器出現空閑，即使這段空閑時間不足以完成一道工序。構成步驟：五、單件車間排序問題（n/m/G/Fmax）無延遲作業計劃的構成步驟：①設t＝1，{St}為空，{Ot}為各工件第一道工序的集合。②求最小的最早完工時間T*=min{Tk},并找到出現T*的機器M*，若有多臺，任選一臺。③從{Ot}中跳出滿足以下兩條件的工序Oj需要機器M*加工；Tj=T*④將確定的Oj放入{St}，從{Ot}中消去Oj并將Oj的緊后工序放入{Ot}中，使t=t+1。⑤若還有未安排的工序，轉步驟②；否則，停止。一個實例：D=1,1,11,2,31,3,22,1,32,2,12,3,2T=241345i1{Ot}TkT’kT*M*Oj1,1,1020M11,1,12,1,30321,2