運用基因演算法解決流程式人力分配排程問題

The Application of Genetic Algorithm for the Flowshop Worker Assignment Scheduling Problem

陳奕帆(Yi-Fan Chen)

指導教授 ： 胡伯潛

國立虎尾科技大學/管理學院/工業工程與管理研究所/碩士(2009年)

摘要

許多各種不同性質的排程作業被廣泛運用於各種生產製造及服務業的領域中，其共同的目的都是想藉由有限可用的資源(機器、設備及工作人員等)的適當分配，使加工或服務作業的進行及資源使用的效率極大化。
流程式生產問題而言，已屬於NP-hard問題，當工作數目與機器數增大時，求解已經變為非常複雜。本研究中，為使流程式排程問題更貼近實務，因此加入人工數目的分配，使得每一工作站上都具有人員於工作站上操作。人力分配排程問題與傳統排程問題之間的差異，就是工件於工作站上的處理時間不再是一個固定的常數，而與被分配至處理該工作的人數有關，亦即工件的處理時間為人工變數的某種函數關係。
於這份研究中，焦點將放在流程式生產排程問題的解決上，目的則是要探討如何在流程式的生產排程問題中，將待處理工件及可用的人力適當的指派到各工作站上，使總完工時間的衡量指標極小化。本研究將運用基因演算法作為解決此問題的主要工具，並以NEH(Nawaz, Enscore and Ham)法所得到的結果為比較的對象。
經研究結果發現，NEH法於較大型題目求解過於消耗時間，於實務上會產生工作效率低落的問題；本研究提出之演算法，在解決流程式人力分配排程問題，不僅可以獲得較佳的求解效果，並且可有效控制求解運算時間，較符合實務之需求，因此顯現本研究所提出的基因演算法於此排程問題的優越性。

關鍵字

排程 ； 流程式生產排程 ； 基因演算法 ； NEH法 ； 人力分配排程問題

並列摘要

Many different kinds of scheduling work are widely used both in the manufacturing and service field, the common purpose is how to effectively assign those available sources (machine, equipment, worker, etc.) to maximize the efficiency of related operations and the utilization of those resources.
In this research, the focus will be put at the flowshop worker assignment scheduling problem and the purpose is to investigate how to assign the jobs that are waited for processing and those available workers to workstations to minimize the performance measure of makespan.
Genetic algorithm is the main tool for solving this specific problem, besides, the result obtained from NEH(Nawaz, Enscore and Ham) method will be used to compare to the result solved by the GA method and demonstrate the superiority of the latter method.

並列關鍵字

Scheduling ； Flowshop ； Genetic Algorithm ； NEH ； Worker Assignment Scheduling Problem

參考文獻

1. 柯慧雯，2001，結合模擬退火法與禁忌搜尋法在流程式生產排程之應用，大葉大學工業工程研究所，碩士論文。

2. 葉柏慶，2007，運用系統模擬與基因演算法於解決相同機台之人力分配排程問題，國立虎尾科技大學工業工程與管理研究所，碩士論文。

3. 盧研伯，2003，混合式模擬退火法應用於迴流特性流程工廠之研究，國立台灣科技大學，碩士論文。

4. Brown, E.C., Sumichrast, R.T. (2001). “A grouping genetic algorithm for the cell formation problem”, International Journal of Production Research, vol. 39, no.16, pp. 3651-3669.

5. Campbell, H. G. , Dudek, R. A. and Smith, M. L. (1970). ”A Heuristic Algorithm for The n Job, m Machine Sequencing Problem”, Management Science, vol.16, no.10, pp630-667.