Li ,s Ci ,s di ,s
延遲時間(Tardiness)：工作i完工時間超出交期的時間。 Ti , s max 0, C i , s d i , s 延遲作業數目(Number of tardy jobs)： n
生產計畫與管理 Chapter 7 作業排程
NT i
7-19
平行機台(parallel machine) 排程問題 1/2
傳統平行機台排程問題就是將n個工作如何安 排至m部平行機台的問題。
Machine 1
Machine 2
Machine 3
. . .
n 件工作
Machine i
Machine m
m 部平行機台
生產計畫與管理 Chapter 7 作業排程
當工作附有重要性之屬性時，排程人員可給予個別之 權重，權重值愈大表示重要性愈大。
WSPT法則即是將作業時間除以權重，所得之值愈小者 表示為愈重要之工作，而將它排至順序的第一位，依 此類推。加權平均流程時間的計算方式為
Fw , s
w F
i 1 i
n
i ,s
w
i 1
n
i
生產計畫與管理 Chapter 7
平均延遲時間(Average
Байду номын сангаас
最大延誤時間(Maximum lateness)：L max max {L i ,s } 1 i n
0 最大延遲時間(Maximum tardiness)：Tmax max{ , Lmax }
生產計畫與管理 Chapter 7 作業排程
7-10
單機(single machine)排程問題
生產計畫與管理 Chapter 7 作業排程
7-21
最小化平均流程時間
範例 7.6
工作 i 作業時間ti 1 5 2 6 3 3 4 8 5 7 6 2 7 3 8 5 9 4 10 2
Step1:SPT法則 : {6,10,3,7,9,1,8,2,5,4}
Step2:依序將工作指派至最早閒置之機台
7-14
範例 7.1 3/3
所以平均流程時間 1 Fs (8 3) (7 4) (6 5) (5 6) (4 7) (3 8) (2 10) (1 12) 24.5
8
由上例及圖7.3觀察，工作流程時間的計算方式為
1 Fs nt1 ( n 1)t 2 2t n1 t n n
決定各工作站的工作負荷(work loading) 決定工作之處理順序(sequencing)
生產計畫與管理 Chapter 7 作業排程
7-4
作業排程的基本概念
負荷安排
1/2
將各項工作分配至各工作站，它決定各工作站該負責 之工作，讓管理者將製令單安排至各工作站，同時兼 顧各工作站間目前的產能負荷情況以及生產線平衡問 題，但並未排定各工作站內的工作次序。
7-7
單機(single machine)排程問題
定 義 假 設
․
單機排程是最基本的排程問題，其定義為n件 獨立工作以何順序分派至一部機台上作業， 以使某一績效評估指標最佳
n個工作的開始時間均為零 ․作業時間(tj)包含了準備時間(setup time)，而 且不受排程順序的不同而有所影響 ․作業時間(tj)事先已知 ․一旦機器有空馬上處理下一等待的工作 ․上機的工作未處理完成前，不能中途停止
7-25
生產計畫與管理 Chapter 7 作業排程
流線型生產之排程問題
1/3
如何決定n件工作進入系統的處理順序： m部序列機台(m-1機台排在m機台前)，每件 工作都必頇依序通過此m部機台，當某工作 在一機台之作業完成後，便依序到下一機台 等待處理。
Machine 1 Machine 2 Machine m
機台3 機台2 機台1 2 5 4 1 8 9 6 3 7 10
機台3 機台2 機台1 6 10 7 9 3 8 4 1 5 2
2
4
6
8
10
12
14
16
18
2
4
6
8
10
12
14
16
18
7-23
生產計畫與管理 Chapter 7 作業排程
降低最大延遲時間
Step1:EDD法則 : {6,10,1,7,2,8,5,4,3,9} Step2:依序將工作指派至最早閒置之機台
生產計畫與管理 Chapter 7 作業排程
7-12
範例 7.1 1/3
給予一組工作集如表 7.6，目標為最小化平均流程時間。
表 7.6 工作作業時間表
工作 i 1 2 3 4 5 6 7 8
生產計畫與管理 Chapter 7 作業排程
作業時間 ti 4 8 7 3 10 12 6 5
7-13
範例 7.1 2/3
․
生產計畫與管理 Chapter 7 作業排程
7-8
排程之基本評估指標 1/2
總完工時間(Makespan)：所有工作處理完成之完工時間。 n
M s ti
i 1
作業流程時間(Flowtime)：工作在系統中停留之時間。
Fi ,s Ci ,s r ,s i
延誤時間(Lateness)：工作i完工時間與交期之差異。
機台3 機台2 機台1 10 6 7 3 9 8 1 2 4 5
生產計畫與管理 Chapter 7 作業排程
2
4
6
8
10
12
14
16
18
7-22
降低總完工時間
範例 7.7
工作 i 作業時間ti 1 5 2 6 3 3 4 8 5 7 6 2 7 3 8 5 9 4 10 2
Step1:LPT法則 : {4,5,2,1,8,9,3,7,6,10} Step2:依序將工作指派至最早閒置之機台 Step3:依SPT法則排序機台上工作
在探討單機排程時，我們發現Hodgson方法可 使延遲件數最小，現在依此方法應用到平行機 台排程上。
步驟1
步驟2 步驟3 利用方法7.5.3指派所有工作。 針對每部機台，找出第一個延遲工作，假設 發現在機台j的第i個順位。 檢查並找出在機台j前i個順位中作業時間最 長者，將它移至機台j的最後順位，修正更 改後工作的完成時間並重複步驟2。
d1 d 2 d n
生產計畫與管理 Chapter 7 作業排程
7-18
Hodgson法則：求NT最小， 即最小化延遲工件數目
Step 以EDD法則將所有工作排序為集合，並計算E集合中 1 所有工作的完工時間。假使結果出現沒有或者只有一
個延遲工作，則停止，此時已達 為最小最佳解。否 則進入第二步驟。
i 1
7-9
排程之基本評估指標 2/2
平均流程時間(Average 平均延誤時間(Average
1 n flowtime)： Fs n Fi ,s i 1
1 n lateness)：Ls n L i ,s i 1
1 n tardiness)：Ts n Ti ,s i 1
第七章 作業排程
前言 作業排程的基本概念 作業排程的特徵與限制 單機排程問題 平行機台排程問題 流線型生產之排程問題 零工型生產之排程問題 前推與後推排程問題 人員排程問題 結語
前言
系統安裝設置(installation)專案 半導體製造工廠 汽車組裝生產線 汽車租賃保留(reservation)系統 醫院中的護士排班問題
除了最小化平均流程時間以外，在單機排程問題中SPT法 則亦可以最小化平均延誤時間、最小化平均等候時間。
4 0 1 5 8 7 15 3 2 25 5 35 40 45 6 50
7-15
10
20
30
生產計畫與管理 Chapter 7 作業排程
加權最短作業時間法則 (WSPT)— 最小化加權平均流程時間
7-20
平行機台(parallel machine) 排程問題 2/2
一般平行機台主要可分為二種：
Identical parallel machine (等效平行機台)： ․所有的機台對於某一個工件的加工速度均相同。 Unrelated parallel machine (無關聯平行機台)： ․各機台的加工速度皆不同，且以同一機台來說， 不同的工件也會有不同的加工速度。
工作i 1 2 3 4 5 6 7 8 9 作業時間 5 6 3 8 7 2 3 5 4 交期 8 9 14 12 11 5 8 10 15
機台2 機台1 10 6 7 2 8 3 4 機台3 1 5 9
2
4
6
8
10
12
14
16
18
10
2
7
生產計畫與管理 Chapter 7 作業排程
7-24
降低延遲工件數目
生產計畫與管理 Chapter 7 作業排程
7-6
作業排程的特徵與限制
製造現場生產結構(Shop Structure) 評估準則(Performance Criteria) 產品結構(Product Structure) 工作中心之產能(Work Center Capacities)
生產計畫與管理 Chapter 7 作業排程
生產計畫與管理 Chapter 7 作業排程
7-17
最早交期法則 (EDD Rule)— 最小化最大延誤時間 (Lmax)
1955年Jackson提出EDD (Early Due Date) 派工法 則，其應用在最小化最大延誤時間和最大延遲時 間，但是會有增加延遲工作數目和增加平均延遲 時間的傾向。 EDD法則排序為交期愈早者排至愈前面，即