資源限制下比例式非等效平行機台排程問題之研究

Uniform Parallel-Machine Scheduling Problems with Constrained Resources

王苡宸(Yi-Chen Wang)

指導教授 ： 蔡啟揚

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

https://doi.org/10.6838/YZU.2008.00237

摘要

過去關於比例式非等效平行機台研究的限制與假設條件，都設定無限資源情況下進行，而實際業界中，各機台可使用資源是有限的情況並非完全相同。而這類問題在學術上是熟知困難度極高的組合最佳化問題，除了少數特例外，此類問題皆屬於NP-hard問題，需要花費相當多的時間與資源才能求得最佳解，因此，本研究期望能夠在有限的資源限制下，建構一個以總完工時間最小化的比例式非等效平行機台排程模式。
本研究提出分支界限法(branch and bound technique, BnB)求解資源限制下比例式非等效平行機台排程問題，其中提出有效的下限值(Lower Bound)，並利用模擬退火法所得近似最佳解做為上限值(Upper Bound)，以有效求取問題最佳解。同時，考量業界重視求解速度，另外依問題特性設計出以混合式鄰近搜尋法的模擬退火法以及改良式交配和突變法則的基因演算法，以其能有效的產生近似最佳解。最後依據問題大小及結構來設計不同規模測試資料，總合上述三種方法的實驗結果顯示，可以說明分支界限法於小、中型規模例題有不錯的求解品質及效率。

關鍵字

排程、比例式非等效平行機台 ； 資源限制 ； 分支界限法 ； 模擬退火法

並列摘要

The previous studies on uniform parallel-machine scheduling problems usually assume that the necessary resources for processes are unconstrained. However, it does not conform to condition that the resources in scheduling problems are usually limited in practice. It is well known that most of the uniform parallel-machine scheduling problems are NP-hard. It costs much time and a large number of resources to solve this kind of problems. Therefore, this research attempts to solve uniform parallel-machine scheduling problems with constrained resources. The objective considered in this research is minimizing the total completion time.
In this research, we propose the branch and bound technique on uniform parallel-machine scheduling problems with constrained resources. The branch and bound technique is proposed with an effective lower bound. The solutions obtained by applying simulated annealing algorithm, is used as the upper bound in the branch and bound technique to acquire the optimal solutions efficiently. In order to meet the requirement of solring problems efficiently in practice, we also propose two heuristics, simulated annealing algorithm with proposed hybrid neighborhood search and genetic algorithm with the improved crossover and mutation rules. Finally, a variety of numerical examples are designed with different sizes and resource strength to evaluate the performance of the proposed algorithms. By the result of our experiments, we can find that the branch and bound technique provides better solution quality and efficiency on examples of small-sized and medium-sized scale.

並列關鍵字

scheduling ； uniform parallel-machine ； constrained resources ； branch and bound technique ； simulated annealing ； genetic algorithm

參考文獻

7. 鄭志傑，2006，「基因演算法於有限資源下不相關平行機台排程問題之應用」，元智大學工業工程與工程管理研究所，碩士論文。

5. 陳柔君，2005，「蟻群演算法於等效平行機台排程問題之研究」，元智大學工業工程與工程管理研究所，碩士論文。

6. 吳思農，2005，「模擬退火法於有限資源下不相關平行機台排程問題之應用」，元智大學工業工程與工程管理研究所，碩士論文。

8. 賴佑華，2007，「應用分支界限法於資源限制下的不相關平行機台排程問題」，元智大學工業工程與工程管理研究所，碩士論文。

9. Armentano, V.A. & de França Filho, M.F. 2007, "Minimizing total tardiness in parallel machine scheduling with setup times: An adaptive memory-based GRASP approach", European Journal of Operational Research, vol. 183, no. 1, pp. 100-114.