具有學習效果的流程式生產排程之最大完工時間與總完工時間最小化之研究

Scheduling Problems to Minimize Makespan and Total Completion Time in Flowshop Environment with Learning Effects

鐘愉翔(Yu-Hsiang Chung)

指導教授 ： 唐麗英 ； 洪瑞雲

國立交通大學/管理學院/工業工程與管理系所/博士(2011年)

https://doi.org/10.6842/NCTU.2011.01084

摘要

在傳統的排程問題中，工作件的加工時間皆設定為固定常數，且不會因工作件在機台上的加工順序而改變，然而當執行加工的人員因重複處理類似工作件而獲得經驗時，工作件的加工時間會因此縮減，此現象為近年來在排程領域被廣泛討論的「學習效果(Learning effect)」。學習效果可分類為兩種型式，分別為「依加工順序改變之學習效果(Position-based learning effect)」與「依已加工時間改變之學習效果(Sum-of-processing-time-based learning effect)」，在一個排程問題中，此兩種型式之學習效果可以單獨考慮或同時考慮，由於依加工順序改變之學習效果模型為理論上的理想學習模型，因此本論文將探討依加工順序改變之學習效果。再者，目前關於具有學習效果的排程問題大多針對單機做探討，然而在實際製程上，許多生產環境的排程屬於多機流程式生產排程，其問題之求解的複雜性亦高於單機生產排程問題。此外，大多數排程問題之目的是求得最佳的工作件排序使其目標函數最小化，而最常被探討的目標函數為最大完工時間與總完工時間。因此本論文針對依加工順序改變之學習效果探討兩個多機流程式生產排程問題，第一個問題設定所有機台有相同的學習效果，其目標為最大完工時間最小化；第二個問題則是依不同機台有不同的學習效果，其目標為加權整合之總完工時間與最大完工時間最小化。
本論文對於工作件數少的問題，使用分枝界限演算法求得最佳排序，接著推導凌越性質與下界值以增進分枝界限演算法的求解效率；對於工作件數多的問題，本論文將利用兩個知名的啟發式演算法、模擬退火法與基因演算法來求得近似解。最後，本論文將針對所有提出的演算法進行電腦模擬，以探討學習效果對於分枝界限演算法的求解效率與啟發式演算法的精準性之影響。針對本論文探討之問題的電腦模擬結果，我們發現將傳統環境中求得之最佳排序應用在具有學習效果的環境中，得到的目標函數值將比實際的最佳目標函數值大，此現象指出學習效果對本論文提出的排程問題有顯著的影響。而在求最佳排序時，分枝界限演算法求解的效率與學習效果的強度成正比。此外，基因演算法為本論文提出之求近似解的演算法中最精準的。基於分枝界限演算法求解時間的分佈變異大且呈右偏，因此本論文建議在求解時先施以分枝界限演算法，若在合理的時間內無法求得最佳排序，則施以基因演算法求近似排序。最後，若流程式生產環境中的機台上能指派不同的操作員，則將學習能力強的操作員指派至工作量較大的機台上能得到較佳的目標函數值。

關鍵字

流程式生產排程 ； 學習效果 ； 最大完工時間 ； 總完工時間

並列摘要

In traditional scheduling problems, the processing time for a given job is assumed to be a fixed constant no matter the scheduling order of the job. However, it is noticeable that the job processing time declines as workers gain more experience. This phenomenon is called the “learning effect”. The learning effect is extensively studied in scheduling field recently, and it can be classified into two types: “the position-based learning” and “the sum-of-processing- time-based learning”. The two types of learning effect can be considered alone or simultaneously in a scheduling problem. The position-based learning is studied in this dissertation because of its model is the pure learning model in theory. In addition, most of the studies on the learning effect are focused only on single-machine setting. However, numerous real-world industrial problems belong to flowshop scheduling problems, and dealing with the flowshop scheduling problems is more complex than dealing with the single-machine problems. Most scheduling problems aim at determining an optimal sequence to minimize the objective function. The makespan and total completion time are the objective functions that are often studied. As a result, this dissertation discusses two flowshop scheduling problems with position-based learning effect. The learning effects are identical on all machines, and the purpose is to minimize the makespan in the first problem. The learning effects are distinct for different machines, and the purpose is to minimize the weighted sum of total completion time and makespan in the second problem.
In this dissertation, the branch-and-bound algorithm is proposed to seek the optimal sequence for the small job-sized problem. Then the dominance properties and lower bounds are proposed to accelerate the procedure of the branch-and-bound algorithm. For the large job-sized problem, two well-known heuristic algorithms, simulated annealing and genetic algorithm are utilized to yield the near-optimal sequence. In the end, the simulated experiments are examined to assess the performance of the algorithms proposed in this dissertation. The computational results of the proposed problems reveal that the objective value calculated from the optimal sequence under the traditional environment is larger than the optimal objective value in the environment with learning considerations. It implies the influence of the learning effect is notable for the problems proposed in this dissertation. Furthermore, the efficiency of the branch-and-bound algorithm ascends as the learning effect enhances while seeking the optimal sequence. The proposed genetic algorithm has the best performance among all heuristic and meta-heuristic algorithms in terms of the accuracy. In addition, due to the large variance and the right skewness for the distribution of the execution time, the branch-and-bound algorithm is recommended to obtain the optimal sequence in a reasonable amount of time, or to derive the near-optimal sequence from the proposed genetic algorithm. Eventually, assigning the operator with stronger learning effect to the machine with heavier workload might derive smaller objective value while the operators are allocated in the flowshop environment.

並列關鍵字

Flowshop scheduling ； Learning effect ； Makespan ； Total completion time

參考文獻

[1] Biskup, D., “Single-machine scheduling with learning considerations”, European Journal of Operational Research, 115, 173-178, 1999.

[2] Biskup, D., “A state-of-the-art review on scheduling with learning effect”, European Journal of Operational Research, 188, 315-329, 2008.

[3] Chen, P., Wu, C.C., and Lee, W.C., “A bi-criteria two-machine flowshop scheduling problem with a learning effect”, The Journal of Operational Research Society, 57, 1113-1125, 2006.

[4] Cheng, T.C.E., Cheng, S.R., Wu, W.H., Hsu, P.H., and Wu, C.C., “A two-agent single-machine scheduling problem with truncated sum-of-processing-times-based learning consideration”, Computers & Industrial Engineering, 60, 534-541, 2011.

[5] Cheng, T.C.E., Lai, P.J., Wu, C.C., and Lee, W.C., “Single-machine scheduling with sum-of-logarithm-processing-times-based learning considerations”, Information Sciences, 179, 3127-3135, 2009.