運用系統模擬與基因演算法於解決相同機台之人力分配排程問題

The Applications of Simulation－GA method to the Identical, Parallel Machine Worker Assignment Scheduling Problem

葉柏慶(Bo-Ching Yeh)

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

摘要

排程(Scheduling)在生產管理是一個十分重要的領域，它的意義為在某一段時間內，分配有限的資源及決定一群工作進行的順序，以達成一定的目標或效率。因此排程往往被視為一個有限資源最佳化的分配工具。
本研究的主題在於探討人力分配排程問題中的一個領域，即如何在相同機台平行處理的情形下，指派各項工作(訂單)以及分配現有的人力到機台(工作站、工作單位等)，以達將工作的最大總完工時間極小化的目的。
人力分配排程問題與傳統排程問題唯一的差異在於前者多了人力分配的問題，亦即工作的處理時間不再是固定的常數而與被分配至處理該工作的人數有關。
在本研究中，首先利用系統模擬軟體來建構相同機台排程模式，再使用軟體之GA模組來尋找最佳排程及人力配置的問題。模擬之結果會與窮舉法及啟發式(LPT-A/LPA)之結果比較，期望找出符合實務排程需求之較佳建議。
經結果分析顯示，窮舉法雖然能保證求得最佳解，卻極耗時間；本研究提出的啟發式演算法(LPT-A/LPA)所花的時間非常少，卻能得到不錯的結果；至於系統模擬－基因演算法，其所花費的時間介於另兩者之間，得到的解也大都為最佳解。因此，本研究建議可針對不同的需求選擇適當的解決方法。

並列摘要

Scheduling is a very important in the production management area. Basically, scheduling is an act of defining priorities or arranging activities to meet certain requirements, constraints, or objectives.
In this study, the identical, parallel machine model in the worker assignment scheduling problem is investigated with the performance measure of makespan. That is, how to assign the jobs and the available workers to machines to minimize the makespan in the model of identical, parallel machines for the worker assignment scheduling problem.
The difference between the classic scheduling problem and the worker assignment scheduling problem is the latter has an extra worker assignment problem needs to be solved. Therefore, the processing times of jobs are no longer fixed but related to the number of workers assigned to work on it.
In this research, system simulation with genetic algorithm is applied to solve the simulated problem. Its result is then compared with exhaustive search and heuristic algorithms. As the results shown, exhaustive search can always get the optimal solutions but very time consuming; the heuristic needs the least amount of time and gets very good solutions; as the simulation－GA, most of the time it can get the optimal solutions with the time less than the exhaustive search method.

參考文獻

[5] 沈育安，2004，以模擬為基礎之啟發式演算法求解平行機台排程問題，成功大學製造工程研究所，碩士論文。

[6] 吳政俊，2006，具平行機台與迴流特性之零工式工廠排程研究，中原大學工業工程研究所，碩士論文。

[25] 蕭陳鴻，2001，基因演算法於非等效平行機台排程之應用，元智大學工業工程與管理研究所，碩士論文。

[16] 徐烈照，2002，應用塔步搜尋法於非等效平行機台之研究-以 PCB 鑽孔作業為例，元智大學工業工程與管理研究所，碩士論文。

[19] 趙文涼，2001，基因演算法於單機交期絕對偏差及整備成本總和最小化排程問題之應用，元智大學工業工程與管理研究所，碩士論文。