應用啟發式演算法求解等效率平行機台排程問題

Applying Heuristic Algorithms for Solving Uniform Parallel Machine Scheduling Problems

莊美琪(Mei-Chi Chuang)

指導教授 ： 葉維彰

國立清華大學/工學院/工業工程與工程管理學系/博士(2014年)

https://doi.org/10.6843/NTHU.2014.00606

摘要

近十年來，平行機台排程問題得到相當多的注意。在本論文中，我們將根據不同的性質，探討三個平行機台排程問題，目標是找到一個排程，使得總完工時間最小化。

(1) 由於全球暖化的影響，如何有效的管理自然資源以及減少碳排放量，已變成重要的議題。我們考量一資源消耗限制式，且總資源消耗不得超過一確定的數量。對於這個NP-hard問題，三個啟發式演算法被提出來，以用來產生近似最佳解。

(2) 在過去十年來，具有學習效應的排程問題已變成受歡迎的主題。在典型的排程中，處理時間是被假設成固定且已知的 。然而，由於工作者的個人經驗，每個人的技能可能是不同的。在此問題，除了找到一最佳的排程外，並包含最佳人員的指派，且目標是最小化總完工時間。

(3) 傳統上，在整個製程中，工作的處理時間是被假設成固定且已知的。實際上，大部分的情形中，工作的處理時間無法預先知道的。因此，模糊集合理論提供一方便的相對架構，數學地模組化出真實世界的系統。我們研究一具有模糊處理時間及學習效應的平行機台排程問題。目標是最小化總完工時間且以機率測量為基底。最後，我們提出兩種演算法來求解此排程問題。

關鍵字

排程 ； 等效率平行機台 ； 資源消耗 ； 總完工時間 ； 學習效應 ； 啟發式演算法 ； 模糊集合理論 ； 機率測量

並列摘要

The parallel machine scheduling has been given considerable attention in the past decades. In our dissertation, we study three uniform parallel machine problems with different properties in which the objective is to find a schedule that minimizes the makespan.
(1) Due to the global warming effect, how to manage natural resource efficiently and reduce carbon emissions have become important issues. We consider a resource consumption constraint that the total resource consumption cannot exceed a certain amount. For this NP-hard problem, three heuristic algorithms are proposed to generate approximate solutions. Computational results are also provided to demonstrate the performance of the proposed heuristic algorithms

(2) Scheduling with learning effects has become a popular topic in the past decade. In classical scheduling, the processing times of jobs are assumed to be fixed and known. However, the skills of workers might be different due to their individual experience. In this problem, the objective is to find not only an optimal schedule but also an optimal assignment of operators to minimize the makespan. Two heuristic algorithms are proposed and the computational experiments are conducted to evaluate their performance.

(3) Traditionally, job processing times are assumed to be fixed and known over the entire process. In reality, the job processing times in many situations are not fully known in advance. As a result, fuzzy set theory provides a convenient alternative framework for modeling real-world systems mathematically. We study the parallel machine scheduling problem with fuzzy processing times and learning effects. The objective is to minimize the fuzzy makespan based on the possibility measure. Finally, we proposed two algorithms to solve the scheduling problem.

並列關鍵字

scheduling ； uniform parallel machines ； resource consumption ； makespan ； learning effect ； heuristic algorithms ； fuzzy set theory ； possibility measure

參考文獻

[1] Anglani, A., Grieco, A., Guerriero, E., Musmanno, R. (2005). Robust scheduling of parallel machines with sequence-dependent set-up costs. European Journal of Operational Research, 161(3), 704–720.

[2] Azadeh, A., Sangari, M. S., Amiri, A. S. (2012). A particle swarm algorithm for inspection optimization in serial multi-stage processes. Applied Mathematical Modelling, 36(4), 1455–1464.

[3] Balasubramanian, J., & Grossmann, I. E. (2003). Scheduling optimization under uncertainty—an alternative approach. Computers and Chemical Engineering, 27(4), 469–490.

[4] Balin, S. (2011). Non-identical parallel machine scheduling using genetic algorithm. Expert Systems with Applications, 38(6), 6814-6821.

[5] Balin, S. (2011). Parallel machine scheduling with fuzzy processing times using a robust genetic algorithm and simulation. Information Sciences, 181(17), 3351–3569.