【正文】 A. 列出每個(gè)作業(yè)在兩臺(tái)工作中心上的作業(yè)時(shí)間 B. 選擇最短的作業(yè)時(shí)間 C. 如果最短的作業(yè)時(shí)間來(lái)自第一臺(tái)工作中心，則首先進(jìn)行這個(gè)作業(yè)；如果最短的作業(yè)時(shí)間來(lái)自第二個(gè)工作中心，則該作業(yè)最后排序 D. 對(duì)剩余作業(yè)重復(fù)進(jìn)行步驟 2和 3，直到排序完成。每個(gè)工件都按 M1→M2 的路線加工。另外，從數(shù)學(xué)上可以證明，在 n/1情況下，用其他的評(píng)價(jià)準(zhǔn)則，如等待時(shí)間均值和完成時(shí)間均值最小， SOT規(guī)則也是最優(yōu)方案。 2023/2/9 42 加工順序 加工時(shí)間 交貨日期 流程時(shí)間 E A B C D 1 3 4 2 6 2 5 6 7 9 0+1=1 1+3=4 4+4=8 8+2=10 10+6=16 總流程時(shí)間 =1+4+8+10+16=39（天） 平均流程時(shí)間 =39/5= 在這種情況下，訂單 B， C和 D將會(huì)延期，平均延期時(shí)間為（ 0+0+2++7） /5=。另外，訂單E和 C將在交貨日期前完成，訂單 A僅延期 1天。每個(gè)訂單平均延期（ 1+1+2+6+14） /5=。原始數(shù)據(jù)為： 訂單（以到達(dá)的順序） 加工時(shí)間 /天 交貨期 /天 A B C D E 3 4 2 6 1 5 6 7 9 2 2023/2/9 40 方案一 利用 FCFS規(guī)則，其流程時(shí)間的結(jié)果如下： 加工順序 加工時(shí)間 交貨日期 流程時(shí)間 A B C D E 3 4 2 6 1 5 6 7 9 2 0+3=3 3+4=7 7+2=9 9+6=15 15+1=16 總流程時(shí)間 =3+7+9+15+16=50（天） 平均流程時(shí)間 =50/5=10天 將每個(gè)訂單的交貨日期與其流程時(shí)間相比較，發(fā)現(xiàn)只有 A訂單能按時(shí)交貨。 下列作業(yè)排序標(biāo)準(zhǔn)可用于評(píng)價(jià)優(yōu)先規(guī)則 滿足顧客或下一道工序作業(yè)的交貨期 極小化流程時(shí)間（作業(yè)在工序中所耗費(fèi)的時(shí)間） 極小化在制品庫(kù)存 極小化設(shè)備和工人的閑置時(shí)間 2023/2/9 38 排序問(wèn)題的分類與表示法 按機(jī)器的種類和數(shù)量分：?jiǎn)闻_(tái)機(jī)器排序問(wèn)題和多臺(tái)機(jī)器排序問(wèn)題按加工路線的特征分：?jiǎn)渭囬g排序問(wèn)題和流水車間排序問(wèn)題按工件達(dá)到車間的情況不同分：靜態(tài)排序問(wèn)題和動(dòng)態(tài)排序問(wèn)題按目標(biāo)函數(shù)分：平均流程時(shí)間最短或誤期完工的工件數(shù)最少按參數(shù)的性質(zhì)分：確定型排序問(wèn)題與隨機(jī)型排序問(wèn)題 Conway等人提出的排序法： n/m/A/B 其中： n — 工件數(shù) m— 機(jī)器數(shù) A— 車間類型（ F表示流水車間排序， P流水車間排列排序問(wèn)題 ， G表示單件車間） B— 目標(biāo)函數(shù) 2023/2/9 39 N個(gè)作業(yè)單臺(tái)工作中心的排序 這類問(wèn)題被稱作“ n個(gè)作業(yè) —— 單臺(tái)工作中心的問(wèn)題”或“ n/1”，理論上，排序問(wèn)題的難度隨著工作中心數(shù)量的增加而增大，而不是隨著作業(yè)數(shù)量的增加而增大，對(duì) n的約束是其必須是確定的有限的數(shù) 例： n個(gè)作業(yè)單臺(tái)工作中心排序問(wèn)題。這些規(guī)則可能很簡(jiǎn)單，僅需根據(jù)一種數(shù)據(jù)信息對(duì)作業(yè)進(jìn)行排序。 ? 隨機(jī)規(guī)則 2023/2/9 37 作業(yè)排序的評(píng)價(jià) 在某機(jī)器上或某工作中心決定哪個(gè)作業(yè)首先開始工作的過(guò)程稱為排序或優(yōu)先調(diào)度排序。 ? LCFS（后到先服務(wù)）： 該規(guī)則經(jīng)常作為缺省規(guī)則使用。 STR/OP = 交貨提前期所剩的時(shí)間 剩余的加工時(shí)間 剩余的作業(yè)數(shù) 緊迫系數(shù)（ CR） = 需用日期 今日日期 剩余的計(jì)劃提前期 2023/2/9 36 CR=負(fù)值 說(shuō)明已經(jīng)脫期 CR=1 說(shuō)明剩余時(shí)間剛好夠用 CR1 剩余時(shí)間有富裕 CR1 剩余時(shí)間不夠 CR值小者優(yōu)先級(jí)高。 STR/OP的計(jì)算方法為： ? CR緊迫系數(shù)： 緊迫系數(shù)是用交貨期減去當(dāng)前日期的差值除以剩余的工作日數(shù)。 STR最短的任務(wù)最先進(jìn)行。 ? 開始日期： 交貨期減去正常的提前期（最早開始的作業(yè)第一個(gè)進(jìn)行）。 ? DDate交貨期： 最早交貨期最早加工。 ? SOT（最短作業(yè)時(shí)間）： 所需加工時(shí)間最短的作業(yè)首先進(jìn)行，然后是加工時(shí)間第二最短的，如此等等。所以，人們常常不加區(qū)別地使用“排序”與“編作業(yè)計(jì)劃”。 由于編制作業(yè)計(jì)劃的主要問(wèn)題是確定各臺(tái)機(jī)器上工件的加工順序，而且，在通常情況下都是按最早可能開（ 完）工時(shí)間來(lái)編排作業(yè)計(jì)劃。而編制作業(yè)計(jì)劃，則不僅包括確定工件的加工順序，而且包括確定機(jī)器加工每個(gè)工件的開始時(shí)間和完成時(shí)間。排序只是確定工件在機(jī)器上的加工順序。在前向排序和后向排序中，最常用的是前向排序。后向排序告訴我們?yōu)榱税匆?guī)定日期完成，一個(gè)作業(yè)必須開始的最晚時(shí)間。 2023/2/9 30 前向排序和后向排序 前向排序 —— 指的是系統(tǒng)接受一個(gè)訂單后對(duì)訂單所需作業(yè)按從前向后的順序進(jìn)行排序，前向排序系統(tǒng)能力告訴我們訂單能完成的最早日期。提前期由期望作業(yè)時(shí)間（調(diào)整和運(yùn)行時(shí)間）加上由于材料運(yùn)輸和等待訂單執(zhí)行而引起的期望排隊(duì)延期時(shí)間而估算出?？梢愿鶕?jù)各種作業(yè)順序下的調(diào)整和加工時(shí)間標(biāo)準(zhǔn)來(lái)計(jì)算出一段時(shí)間內(nèi)所需的工作量來(lái)判定。 2023/2/9 29 有限負(fù)荷方法和無(wú)限負(fù)荷方法 無(wú)限負(fù)荷 指的是當(dāng)將工作分配給一個(gè)工作中心時(shí)，只考慮它需要多少時(shí)間，而不直接考慮完成這項(xiàng)工作所需的資源是否有足夠的能力，也不考慮在該工作中，每個(gè)資源完成這項(xiàng)工作時(shí)的實(shí)際順序。作業(yè)排序涉及決定工件加工順序以及分配相應(yīng)的機(jī)器來(lái)對(duì)這些工件加工。工作中心可以是一臺(tái)機(jī)器、一一組機(jī)器或完成某一類型工作的一個(gè)區(qū)域，這些工作中心可以按工藝專業(yè)化的一般作業(yè)車間組織，或者按產(chǎn)品流程、裝配線、成組技術(shù)單元結(jié)構(gòu)進(jìn)行組織。 根據(jù)派工單，車間調(diào)度員、工作中心操作員對(duì)目前和即將到達(dá)的任務(wù)一目了然。 說(shuō)明哪些工作已經(jīng)達(dá)到，正在排隊(duì)，應(yīng)當(dāng)什么時(shí)間開始加工，什么時(shí)間完成，加工單的需用日期是哪天，計(jì)劃加工時(shí)數(shù)是多少，完成后又應(yīng)傳給哪道工序。加工單的格式同工藝路線報(bào)表相似。 ? 順序 （ SA， C， SB） 即為近優(yōu)解 。 ? 對(duì)其余工件 ， 若 Pi1≤ Pim ， 則按 Pi1不減的順序排成序列 SA。 實(shí)際中 ， 可以用啟發(fā)式算法求近優(yōu)解 。 2023/2/9 14 三、 n/2/F/Fmax問(wèn)題的算法 Johnson算法： ? 假定： ai為工件 Ji在機(jī)器 M1上的加工時(shí)間， bi為工件 Ji在機(jī)器 M2上的加工時(shí)間，每個(gè)工件按 M1— M2的路線加工。 ? 假定所有工件的到達(dá)時(shí)間都為 0，則 Fmax等于排在末位加工的工件在車間的停留時(shí)間。 而對(duì)于僅有 2臺(tái)或 3臺(tái)機(jī)器的情況 ， 則排列排序問(wèn)題的最優(yōu)解一定是相應(yīng)流水車間排序問(wèn)題的最優(yōu)解 。 2023/2/9 9 單件車間排序問(wèn)題的基本特征： ? 每個(gè)工件都有其獨(dú)特的加工路線 ， 工件沒有一定的流向。 ? 不僅加工路線一致 ， 而且所有工件在各臺(tái)機(jī)器上的加工順序也一樣 ， 這種排序稱為排列排序 （ 同順序排序 ） 。 這里指的是工件的加工流向一致 ， 并不要求每個(gè)工件必須在每臺(tái)機(jī)器上加工 。 2023/2/9 8 流水車間排序問(wèn)題的基本特征： ? 每個(gè)工件的加工路線都一樣 。 2023/2/9 7 排序問(wèn)題的分類與表示 1） 單臺(tái)機(jī)器與多臺(tái)機(jī)器的排序問(wèn)題 。 2023/2/9 6 作業(yè)計(jì)劃 （ Scheduling） ? 作業(yè)計(jì)劃與排序不是一回事 ， 它不僅要確定工件的加工順序 ， 而且還要確定每臺(tái)機(jī)器加工每個(gè)工件的開工時(shí)間和完工時(shí)間 。 2023/2/9 5 所以，作業(yè)排序也就是要確定工件在機(jī)器上的加工順序，可用一組工件代號(hào)的一種排列來(lái)表示。 2023/2/9 4 排序中常用的幾個(gè)概念 ? 工件 （ Job） ：服務(wù)對(duì)象； ? 機(jī)器 （ Machine、 Processor） ：服務(wù)者 。生產(chǎn)與運(yùn)作管理