一个启发性弹性流程排程演算法.PDF

洪㊪貝、王姿婷：㆒個啟發性彈性流程排程演算法 149 技術㈻刊 第㈩㈥卷 第㆒期 民國㈨㈩年 Journal of Technology, Vol. 16, No. 1, pp. 149-154 (2001) ㆒個啟發性彈性流程排程演算法 洪宗貝 王姿婷 義守大學資訊工程研究所 摘 要 排程被廣泛地應用在各個領域，如製造、生產管理、資訊工程等等。在簡 單流程問題上，每個製程中心只有一部機器。若每個製程中心有一部以上的機 器，則這排程問題就稱為是一個彈性流程作業。所以彈性流程排程是簡單流程 排程的更一般化型式，而彈性流程排程是屬於相當困難及複雜的 NP-complete 問題。在過去，Sriskandarajah 及 Sethi 提出一種啟發性演算法來解決在兩個 製程中心的彈性流程問題。在本論文中，我們擴展他們的演算法來解決多個製 程中心的彈性流程問題，我們運用啟發性 Palmer 演算法為中心，以解決我們 所要解決的問題。由於在多製程中心的彈性流程問題是屬相當因難且複雜的 NP-complete 的問題，所以當在工作數量相當多的時候，似乎無需達到最佳排 程，只需達到近似最佳排程即可。因此我們所提的方法可達到此一目的。 關鍵詞：排程、彈性流程、LPT 排程、Palmer 排程。 A HEURISTIC ALGORITHM FOR FLEXIBLE FLOW-SHOP SCHEDULING Tzung-Pei Hong and Tzu-Ting Wang Institute of Information Engineering I-Shou University Kaohsiung, Taiwan 840, R.O.C. Key Words: scheduling, flexible flow shop, LPT scheduling, Palmer sche- duling. ABSTRACT Scheduling is an important process widely used in manufacturing, production, management, computer science, and so on. In simple flow shop problems, each machine operation center includes just one machine. If at least one machine center includes more than one machine, t