多階平行機之排程問題探討

The Scheduling Problem for Multiple-Stage with Parallel Machine

董定鑫(Ding-Shin Dong)

指導教授 ： 張百棧

元智大學/工程學院/工業工程與管理學系/碩士(1994年)

摘要

本研究主要是探討工件在多階平行機情境下之總完工時間最小的排程問題
，由於平行機的導入可以避免單機當機造成系統的停擺且降低頩頸站的發
生，並且可以縮短工件加工之總完工時間，所以此一問題已為學者及工程
研究人員所重視。本研究之基本假設為系統為一個流程型生產型態，而且
工件不可中斷處理，再配合平行機的定義，構建出多階平行機的情境。因
為多階平行的複雜度高，為了縮短總完工時間，所研究導入最早可利用機
器優先指派法則（EAMF）的觀念。在少工件數時，以二個下限值配合分枝
界限法方式求取一最佳解。而在多工件數時，因分枝界限法無法迅速求得
一最佳解，故有傳統的FCFS法則、SPT法則、LPT法則來求取近似最佳解，
而本研究將發展一有效率的啟發式演算法來求取較大型的問題，且經由實
驗結果的比較，可得知本研究發展出的演算法確有其績效。

關鍵字

平行機 ； 總完工時間 ； 最早可利用機器優先指派法則 ； 啟發式

並列摘要

This research focuses on minimizing the makespan of the flow
shop scheduling problems with multiple-stage parallel machines.
Because the setup of parallel machines can avoid single ma-
chine to breakdown , systems to stop , and reducing the situa-
tions of bottleneck and the completion time of parts. Thus ,
this problem has been intensively studied by scholars and
engineering-researchers. Basic hypothesis of our research are :
First , systems are a production type of flow shop. Second ,
parts processing can't be preempted . Third , follow the
definitions of parallel ma- chine.From above, we can construct
the environments of multiple -stage parallel machine.As the
complexity of multiple-stage parallel machine is very highly
,we introduce the concept of Early Available Machine First rule
in order to shorter the make -span .We develop two lower bounds
to find a optimal solution of min-makespan problem with branch
and bound method.We develop also a efficient heuristic method
to deal with the large scale problems .We compare our heuristic
method with the traditional rules of scheduling problems such
as FCFS, SPT, LPT etc,...,with some experiments , We discover
that our algorithm has a much better performance.

並列關鍵字

Parallel Machine ； Makespan ； Early Available Machine First Rule ； Heuristic