【正文】 順序 製令 交期 1 1 10 2 3 12 3 2 13 4 5 14 5 6 15 6 4 18 生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程 739 範(fàn)例 711─以 製令 為主的排程方法 3/3 生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程 740 範(fàn)例 (EDD)─以「工作中心」 為主的排程方法 1/8 製令 作業(yè)順序與時間 交期 1 A(3)→B(3) →C(2) 10 2 A(5)→C(2) 13 3 B(4)→A(4)→C(3) 12 4 B(3)→C(5)→A(2) 18 5 C(5)→B(4) 14 6 C(2)→A(5)→B(5) 15 生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程 741 範(fàn)例 (EDD)─以「工作中心」 為主的排程方法 2/8 若以 T來表示時間軸 。以等候線中工作的寬裕時間最短者為優(yōu)先。 最短作業(yè)時間派工法則 (Shortest Processing Time, SPT) 生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程 736 派工法則 2/2 以等候線中工作的仍剩餘的加工時間最短者為優(yōu)先。一般此法將作為與其他方法之比較基礎(chǔ)。 以「製令」為主的排程方法 (Jobbased Scheduling或 Orderbased Scheduling) 運(yùn)算邏輯是利用事件導(dǎo)向 (EventDriven)的模擬觀念來描述製造系統(tǒng)的實(shí)際運(yùn)作流程。 Step2 將已指派之工作刪除 ， 回至步驟 1， 直到所有工作排完為止 。 Step1 假使選出的最小時間在機(jī)臺 1(ti,1)， 則將所對應(yīng)的工作排在順序最早的下一可排空位 ， 繼續(xù)步驟 3。 M a c h i n e 1 M a c h i n e 2 M a c h i n e mn 件工作 m 部序列機(jī)臺生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程 727 流線型生產(chǎn)之排程問題 2/3 強(qiáng)生法則 (Johnson’s rule)－兩部序列機(jī)臺最小化總完工時間 。 步驟 2 檢查並找出在機(jī)臺 j前 i個順位中作業(yè)時間最長者，將它移至機(jī)臺 j的最後順位，修正更改後工作的完成時間並重複步驟 2。 利用方法 。 Identical parallel machine (等效平行機(jī)臺 )： ?所有的機(jī)臺對於某一個工件的加工速度均相同 。 Step4 生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程 720 平行機(jī)臺 (parallel machine) 排程問題 1/2 傳統(tǒng)平行機(jī)臺排程問題就是將 n個工作如何安排至 m部平行機(jī)臺的問題 。 若集合中沒有延遲作業(yè) ， 則停止 ， 集合的延遲個數(shù)即為最小解 。 Step1 在集合中從頭至尾找出第一個延遲作業(yè)，假設(shè)為 k Step2 檢視前個工作 (包含第個 )， 將最長作業(yè)時間之工作 移至另一集合中 (開始為空集合 )， 其中 。 假使結(jié)果出現(xiàn)沒有或者只有一個延遲工作 ， 則停止 ， 此時已達(dá) 為最小最佳解 。 加權(quán)平均流程時間的計(jì)算方式為 ,1,1ni i siws niiwFFw?????? ?? ?? ?? ?? ?? ?1212WS P T nnt t tw w w? ? ?法則：生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程 717 最短作業(yè)時間 (SPT) 法則 — 最小化平均延誤時間 ( ) 單機(jī)排程問題之目標(biāo)若為最小化平均延誤時間 ，SPT法則排序可得最佳解 ， 即 sL? ? ? ? ? ?12 nt t t? ? ?生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程 718 最早交期法則 (EDD Rule)— 最小化最大延誤時間 (Lmax) 1955年 Jackson提出 EDD (Early Due Date) 派工法則 ， 其應(yīng)用在最小化最大延誤時間和最大延遲時間 ， 但是會有增加延遲工作數(shù)目和增加平均延遲時間的傾向 。 ? ?1 ( 8 3 ) ( 7 4 ) ( 6 5 ) ( 5 6 ) ( 4 7 ) ( 3 8 ) ( 2 1 0 ) ( 1 1 2 ) 2 4 . 58sF ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ?1 2 11 ( 1 ) 2s nnF nt n t t tn ???? ? ? ? ? ???4 1 8 7 3 2 5 6 0 5 10 15 20 25 30 35 40 45 50 生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程 716 加權(quán)最短作業(yè)時間法則 (WSPT)— 最小化加權(quán)平均流程時間 當(dāng)工作附有重要性之屬性時 ， 排程人員可給予個別之權(quán)重 ， 權(quán)重值愈大表示重要性愈大 。 其流程時間計(jì)算和表 。 最短作業(yè)時間 (SPT)法則 — 最小化平均流程時間 ( ) sF? ? ? ? ? ?12 nt t t? ? ?生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程 713 範(fàn)例 1/3 給予一組工作集如表 ， 目標(biāo)為最小化平均流程時間 。 最早交期法則 (EDD) 最小化延遲工件數(shù)目。 加權(quán)最短作業(yè)時間法則 (WSPT) 最大延誤 (遲 )時間最小化。 最短作業(yè)時間法則 (SPT) 最小化平均加權(quán)流程時間。 最小化平均流程時間。 1nsiiMt?? ?延遲時間 (Tardiness)：工作 i完工時間超出交期的時間。 sisisi rCF , ??延誤時間 (Lateness)：工作 i完工時間與交期之差異 。 負(fù)荷安排 工作的處理優(yōu)先順序 生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程 76 作業(yè)排程的基本概念 2/2 因此 ， 所有工作的作業(yè)先後順序 、 先天的技術(shù)限制 、 各個作業(yè)的估計(jì)時間和各個作業(yè)所需之資源產(chǎn)能等 ， 都是構(gòu)建細(xì)部排程時需要考慮的因素 。 又稱派工 (Dispatching)，透過派工法則來決定線上執(zhí)行順序。 在一般工廠內(nèi)常見的排程問題中 ， 處理步驟主要可分為兩部份 。第七章 作業(yè)排程 前言 作業(yè)排程的基本概念 作業(yè)排程的特徵與限制 單機(jī)排程問題 平行機(jī)臺排程問題 流線型生產(chǎn)之排程問題 零工型生產(chǎn)之排程問題 前推與後推排程問題 人員排程問題 結(jié)語 生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程 73 前言 半導(dǎo)體製造工廠 汽車組裝生產(chǎn)線 汽車租賃保留 (reservation)系統(tǒng) 醫(yī)院中的護(hù)士排班問題 系統(tǒng)安裝設(shè)置 (installation)專案 生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程 74 作業(yè)排程的基本概念 排程是一種資源分配的決策活動 。 作業(yè)排程(Operations Scheduling)為廣義排程中的一種 ，若在製造業(yè)中特別是指製造現(xiàn)場機(jī)臺與工件間的安排 ， 以下簡稱排程 。 決定各工作站的工作負(fù)荷 (work loading) 決定工作之處理順序 (sequencing) 生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程 75 作業(yè)排程的基本概念 1/2 將各項(xiàng)工作分配至各工作站，它決定各工作站該負(fù)責(zé)之工作，讓管理者將製令單安排至各工作站，同時兼顧各工作站間目前的產(chǎn)能負(fù)荷情況以及生產(chǎn)線平衡問題，但並未排定各工作站內(nèi)的工作次序。排程可定義成一種短期計(jì)畫，此計(jì)畫關(guān)係著製造現(xiàn)場的製令單或擬作業(yè)之工作的作業(yè)順序和時間配置，此定義說明排程是一序列的排序步驟。 生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程 77 作業(yè)排程的特徵與限制 製造現(xiàn)場生產(chǎn)結(jié)構(gòu) (Shop Structure) 評估準(zhǔn)則 (Performance Criteria) 產(chǎn)品結(jié)構(gòu) (Product Structure) 工作中心之產(chǎn)能 (Work Center Capacities) 生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程 78 單機(jī) (single machine)排程問題 ? n個工作的開始時間均為零 ?作業(yè)時間 (tj)包含了準(zhǔn)備時間 (setup time)， 而 且不受排程順序的不同而有所影響 ?作業(yè)時間 (tj)事先已知 ?一旦機(jī)器有空馬上