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

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

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

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

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

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

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

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

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

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

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

2024/11/525第三步

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

對(duì)矩陣變換的目的在于增加0元素。為此，在沒(méi)有被直線覆蓋的部分中找出最小元素，然后在打√行各元素中都減去這個(gè)最小元素，而在打√列的各元素上都加上這個(gè)最小元素，從而保證原有0元素不變。這樣得到新的矩陣（其與原問(wèn)題有相同最優(yōu)解），若得到n個(gè)獨(dú)立0元素，則得到最優(yōu)解，否則轉(zhuǎn)回第三步重復(fù)進(jìn)行，直到得到最優(yōu)解。2024/11/5282）N個(gè)作業(yè)m臺(tái)工作中心排序2024/11/5292、單件作業(yè)排序問(wèn)題的描述2024/11/5303、一般n/m/G/Fmax問(wèn)題的啟發(fā)式算法1）兩種作業(yè)計(jì)劃的構(gòu)成能動(dòng)作業(yè)計(jì)劃（ActiveSchedule）無(wú)延遲作業(yè)計(jì)劃（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、車(chē)間作業(yè)計(jì)劃控制的內(nèi)容和意義20