制造業(yè)作業(yè)計劃與控制

2024/11/51作業(yè)計劃問題的基本概念流水作業(yè)排序問題單件作業(yè)排序問題生產(chǎn)作業(yè)控制制造業(yè)作業(yè)計劃與控制2024/11/52一、作業(yè)計劃問題的基本概念1、編制作業(yè)計劃（Scheduling）要解決的問題編制作業(yè)計劃實(shí)質(zhì)上是要將資源分配給不同的任務(wù)，按照既定的優(yōu)化目標(biāo)，確定各種資源利用的時間間隔。作業(yè)計劃與排序不是一回事，它不僅要確定工件的加工順序，而且還要確定每臺機(jī)器加工每個工件的開工時間和完工時間。如果按最早可能開（完）工時間來編排作業(yè)計劃，則排序完后，作業(yè)計劃也就確定了。任務(wù)分配排序2024/11/532、排序（Sequencing）概念排序：就是要將不同的工作任務(wù)安排一個執(zhí)行的順序，使預(yù)定的目標(biāo)最優(yōu)化。實(shí)際上就是要解決如何按時間的先后，將有限的人力、物力分配給不同工作任務(wù)，使預(yù)定目標(biāo)最優(yōu)化的問題。

派工：在作業(yè)計劃制定以后，按照作業(yè)計劃的要求，將具體生產(chǎn)任務(wù)通過工票或施工單的形式下達(dá)到具體的機(jī)床和工人。

趕工：是在實(shí)際季度已經(jīng)落后于計劃進(jìn)度時采取的行動。

調(diào)度：是作業(yè)計劃編制以后實(shí)施生產(chǎn)控制的一切行動。2024/11/54排序中常用的幾個概念工件（Job）：服務(wù)對象機(jī)器（Machine、Processor）：服務(wù)者如：n個零件在機(jī)器上加工，則零件是工件，設(shè)備是機(jī)器；工人維修設(shè)備，出故障的設(shè)備是工件，工人是機(jī)器2024/11/55所以，作業(yè)排序也就是要確定工件在機(jī)器上的加工順序，可用一組工件代號的一種排列來表示。如：可用（1，6，5，4，3，2）表示加工順序：J1－J6－J5－J4－J3－J22024/11/56表示方法

一般正規(guī)的表示方法為：n/m/A/Bn：工件數(shù)；m：機(jī)器數(shù)；A：車間類型（F、P、G）；B：目標(biāo)函數(shù)2024/11/573、排序問題的分類與表示按機(jī)器的種類和數(shù)量：單臺機(jī)器和多臺機(jī)器的排序問題按工件加工路線：單件作業(yè)（Job－shop）排序問題，流水作業(yè)（Flow－shop）排序問題。按工件到達(dá)車間情況：靜態(tài)排序問題、動態(tài)排序問題按目標(biāo)函數(shù)性質(zhì)、參數(shù)等，也可有其他的分類表示2024/11/58流水車間與單件作業(yè)排序問題流水車間排序問題的基本特征：每個工件的加工路線都一樣。如車－銑－磨。這里指的是工件的加工流向一致，并不要求每個工件必須在每臺機(jī)器上加工。如有的工件為車－銑，有的為銑－磨。不僅加工路線一致，而且所有工件在各臺機(jī)器上的加工順序也一樣，這種排序稱為排列排序（同順序排序）。如工件排序?yàn)椋篔1-J3-J2，則表示所有機(jī)器都是先加工J1，然后加工J3，最后加工J2。2024/11/59流水作業(yè)排序一般來說，排列排序問題的最優(yōu)解不一定是相應(yīng)流水車間排序問題的最優(yōu)解，但一般是比較好的解。而對于僅有2臺或3臺機(jī)器的情況，則排列排序問題的最優(yōu)解一定是相應(yīng)流水車間排序問題的最優(yōu)解。2024/11/510單件作業(yè)排序的基本特征每個工件都有獨(dú)特的加工路線，工件沒有一定的流向。2024/11/511二、流水車間作業(yè)計劃問題1、加工周期的計算最長流程時間Fmax（加工周期）：從第一個工件在在第一臺機(jī)器上加工起到最好一個工件在最好一臺機(jī)器上加工完畢為止所經(jīng)過的時間。假定所有工作的到達(dá)時間都為0，則Fmax等于排在末位加工的工件在車間的停留時間。2024/11/512計算Fmax的幾個假定條件：機(jī)器M1不會發(fā)生空閑；對其它機(jī)器，能對某一工件加工必須具備兩個條件：機(jī)器必須完成排前一位的工件的加工；要加工的工件的上道工序已經(jīng)完成。2024/11/513算例求按（6，1，5，2，4，3）加工時的加工周期2024/11/5142、兩臺機(jī)器排序問題（n/2/F/Fmax）的算法

采用約翰遜（Johnson）算法，這是S.M.Johnson在1954年提出的，其中的是極小化從第一個作業(yè)到最后一個作業(yè)為止的全部流程時間，以ai表示Ji在M1上的加工時間，以bi表示Ji在M2上的加工時間。每個工作都按M1－>M2的路線加工。Johnson的算法法則是：如果Min（ai，bj）<min（aj，bi），則Ji應(yīng)該排在Jj之前。約翰遜規(guī)則包含以下幾個步驟：1、列出每個作業(yè)在兩臺加工中心上的作業(yè)時間2、選擇最短的作業(yè)時間3、如果最短的作業(yè)時間來自第一臺工作中心，則首先進(jìn)行這個作業(yè)；如果最短的作業(yè)來自第二個工作中心，則該作業(yè)最后排序4、對剩余作業(yè)重復(fù)進(jìn)行上述步驟2、3，直到排序完成。2024/11/5152024/11/5163、一般n/m/p/Fmax問題的啟發(fā)式算法對于一般的n/m/P/Fmax問題，可以用分支定界法求得最優(yōu)解，但計算量很大。實(shí)際中，可以采用啟發(fā)式算法求得近優(yōu)解。

Palmer法關(guān)鍵工件法2024/11/517Palmer法Palmer于1965年對流水作業(yè)排序問題提出了按斜度指標(biāo)排列工件的啟發(fā)式算法，該算法先定義工件的斜度指標(biāo)然后將各工件按其斜度指標(biāo)不增進(jìn)行排序。2024/11/518關(guān)鍵工件法2024/11/519

三、單件車間作業(yè)計劃問題1、任務(wù)分配問題2024/11/5202024/11/521匈牙利算法2024/11/522第一步

使指派問題的系數(shù)矩陣經(jīng)變換，在各行各列中都出現(xiàn)零元素。①從系數(shù)矩陣的每行元素減去該行的最小元素；②從系數(shù)矩陣的每列元素減去該行的最小元素；2024/11/523第二步

進(jìn)行試指派，以尋求最優(yōu)解。①從只有一個零元素的行開始，給這個0元素加圈，記作◎；然后劃去◎所在列的其它0元素，記作Φ。②從只有一個零元素的列開始，給這個0元素加圈，記作◎；然后劃去◎所在行的其它0元素，記作Φ。③反復(fù)進(jìn)行①、②步，直到所有的0元素都被圈出和劃掉為止。2024/11/524第二步④若仍存在沒有劃圈的0元素，且同行（列）的0元素至少有兩個。從剩有0元素最少的行（列）開始，比較這行各0元素所在列中0元素的數(shù)目，選擇0元素少的那列的這個0元素加圈。然后劃掉同行同列的其他0元素。可反復(fù)進(jìn)行，直到所有0元素都已圈出和劃掉為止。⑤若◎元素的數(shù)目m等于矩陣的階數(shù)n，那么求得最優(yōu)解。若m<n，則轉(zhuǎn)入下一步。

2024/11/525第三步

作最少的直線覆蓋所有的0元素，以確定該系數(shù)矩陣中能找到最多的獨(dú)立元素，為此按以下步驟進(jìn)行：①對沒有◎的行打√；②對已打√的行中所有含Φ元素的列打√；③再對已打√的列中含◎元素的行打√；④重復(fù)②、③，直到得不出新的打√的行、列為止⑤對沒有打√的行畫橫線，打√的列畫縱線，這就得到覆蓋所有0元素的最少直線數(shù)。2024/11/526第三步這里令直線數(shù)為L。若L<n，說明需要對矩陣進(jìn)行變換，可轉(zhuǎn)入第四步；若L＝n，而m<n，則回到第二步④，另行試探。2024/11/527第四步

對矩陣變換的目的在于增加0元素。為此，在沒有被直線覆蓋的部分中找出最小元素，然后在打√行各元素中都減去這個最小元素，而在打√列的各元素上都加上這個最小元素，從而保證原有0元素不變。這樣得到新的矩陣（其與原問題有相同最優(yōu)解），若得到n個獨(dú)立0元素，則得到最優(yōu)解，否則轉(zhuǎn)回第三步重復(fù)進(jìn)行，直到得到最優(yōu)解。2024/11/5282）N個作業(yè)m臺工作中心排序2024/11/5292、單件作業(yè)排序問題的描述2024/11/5303、一般n/m/G/Fmax問題的啟發(fā)式算法1）兩種作業(yè)計劃的構(gòu)成能動作業(yè)計劃（ActiveSchedule）無延遲作業(yè)計劃（Non-DelaySchedule）2024/11/5332）啟發(fā)式算法－優(yōu)先調(diào)度法則2024/11/5342024/11/5352024/11/5362024/11/5372024/11/5382024/11/5392024/11/5402024/11/5412024/11/5422024/11/543四、生產(chǎn)作業(yè)控制2024/11/5442、車間作業(yè)計劃控制的內(nèi)容和意義20