具加權學習效應之單機排程問題

A Single Machine Scheduling Problem With Weighted Learning Effect

林雯涵(Wen-Han Lin)

指導教授 ： 楊達立

國立虎尾科技大學/管理學院/資訊管理研究所/碩士(2011年)

摘要

在這個快速變遷的時代裡，由於生產系統在越來越複雜的製造業環境中，與企業營運密切相關，能將生產時間控制得宜，使成本降低，是非常重要的。如何有效的運用學習效應(learning effect)來解決現今的排程工作問題，帶來更多的效益是我們所要探討的。在本研究中，我們介紹單一機台具有加權學習效應的問題。
在本研究中，我們探討具有加權學習效應之單一機台的生產排程問題，其目標函數分別為總加權完工時間(total weighted completion time)最小化與總延遲時間(total tardiness minimization)最小化的問題。首先，我們分別以加權最短作業時間 (weighted shortest processing time) 派工法則以及最早到期日(earlydue-date)派工法則來求解這兩個目標函數最小化的問題，並分析其最差情況誤差值(worst case error bound)。最後，我們再以電腦模擬數值分析驗證此兩種派工法則之排程績效。

關鍵字

學習效應 ； 排程 ； 總加權完工時間 ； 到期日法則 ； 單一機台

並列摘要

In this study, we investigate a single machine scheduling problem with weighted learning effect. The objectives are to minimize the total weighted completion time and the total tardiness, respectively. First, the weighted shortest processing time (WSPT) rule and the early due-date (EDD) rule are used as heuristics to solve the problem with the two objective functions, respectively. Besides, their worst-case error bounds are analyzed.
Finally, the computational results are also provided to evaluate the performances of the two heuristics.

並列關鍵字

Learning effect ； scheduling ； weighted completion time ； early due-date ； single machine

參考文獻

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

[2] Campbell, H.G, Dudek,R.A.,Smith, M.L. A heuristic algorithm for the n-job, M-machine sequencing problem. Management Science,16,630-637(1970).

[3] Dannenbring, D.G. An evaluation of flow-shop sequencing heuristics. Management Science 23,1174-1182(1977).

[5] Gupta,J. A functional heurisitic algorithm for for the flow-shop scheduling problem. Operational Research Quarterly 22,39-47(1971).

[6] Kim,Y,D. A new branch and bound algorithm for minimizing mean tardiness in two-machine flow shops. Computers and Operations Research, 4.391-401(1993).