臺灣博碩士論文加值系統

在傳統之工業排程研究，皆偏重於探討工作件之處理時間為一固定值。但很多實際的情況中，預定工作件的加工時間會隨著其等待安排上機的作業時間拉長，而使得其加工時間變長。另外，在從事工作加工時，生產者經常會遇到機器發生故障的情形。因此，機器之維修也是一個很重要的課題之ㄧ。所以本篇論文主要探討在具有維修的單機情況，而且每個工作件具有退化性質下，如何尋找一排序使得總完工時間(total completion time)達到最小化。本文發展出一些凌越性質與定理，並建立一分枝界限法(branch-and-bound method)尋找最佳解，同時也提供一啟始演算法（heuristic algorithm）以尋找近似解。本文之模擬結果發現對於工作件數較少之排程問題，分枝界限法無論在執行時間與節點數方面，都有很好的成效。對大工作件數之排程問題，啟始演算法將會是一個具有經濟效益的方法，因為啟始演算法求解的時間相當省時，且其解之品質亦不錯。

This paper studies a scheduling problem with deteriorating jobs to minimize the total completion time on a single machine where the machine is not always available during the period of planning time. We assume the unavailable time period is fixed and known in advance. In this paper, a branch-and-bound method and a heuristic algorithm are applied to search for an optimal solution and a near-optimal solution. The experiments show that the branch-and-bound method is a very good effect for small job-size problems. In addition, a heuristic algorithm is proposed to overcome the inefficiency of the branch-and-bound algorithm for large job-size problems. The computation results also show the heuristic algorithm is very accurate.

第一章 緒論 1
1.1 研究動機與背景 1
1.2 研究目的 3
1.3 研究範圍與假設 4
1.4 研究架構 6
第二章 文獻探討 8
第三章 理論性質與解題方法 11
3.1 問題之描述 11
3.2 分枝界限法 12
3.2.1 分枝界限法之定理與準則 13
3.2.2分枝界限法下界值之計算方式 17
3.2.3 分枝界限法及其程序 18
3.3 啟始演算法 19
第四章 模擬與分析 23
4.1 資料模擬 23
4.2 模擬結果 24
第五章 結論與未來研究方向 40
5.1 結論 40
5.2 未來研究方向 41
參考文獻 42

1.Adiri, I., Bruno, J., Forstig, E., Rinnooy, Kan, A.H.G., Single machine flow- time scheduling with a single breakdown, Acta Informatica 26 (1989) 679–696.
2.Aggoune, R., Minimizing the makespan for the flow shop scheduling problem
with availability constraints, European Journal of Operational Research 153
(2004) 534–543.
3.Alidaee, B., Womer, N.K., Scheduling with time dependent processing times:
Review and extensions, Journal of the Operational Research Society 50 (1999)
711-720.
4.Browne, S., Yechiali, U., Scheduling deteriorating jobs on a
singleprocessor, Operations Research 38 (1990) 495-498.
5.Della, Croce, F., Narayan, V., Tadei, R., The two-machine total completion
time flow shop problem, European Journal of Operational Research 90 (1996)
227-237.
6.Fisher, M. L., A dual algorithm for the one-machine scheduling problem,
Mathematical Programming 11 (1971) 229-251.
7.Graves, G.H., Lee, C.Y., Scheduling maintenance and semi-resumable jobs on a
single machine, Naval Research Logistics 46 (1999) 845-863.
8.Gupta, J.N.D., Gupta, S.K., Single facility scheduling with nonlear
processing times, Computers and Industrial Engineering 14 (1998) 387-393.
9.Hsieh, Y.C., Bricker, D.L., Scheduling linearly deteriorating jobs on
multiple machines, Computers and Industrial Engineering 32 (1997) 727-734.
10.Kunnathur, A.S., Gupta, S.K., Minimizing the makespan with late
startpenalties added to processing times in a single facility scheduling
problem, European Journal of Operational Research 47 (1990) 56-64.
11.Lee, C.Y., Two-machine flowshop scheduling with availability constraints,
European Journal of Operational Research 114 (1999) 420-429.
12.Lee, C.Y., Liman, S.D., Single machine flowtime scheduling with scheduled
maintenance, Acta Informatica 29 (1992) 375–382.
13.Lee, C.Y., Machine scheduling with an availability constraint, Journal of
Global Optimization (1996) 395-419.
14.Liao, C.J., Shyur, D.L., Lin, C.H., Makespan minimization for two parallel
machines with an availability constraint, European Journal of Operational
Research January 16 (2005) 445-456.
15.Mosheiov, G., Scheduling deteriorating jobs under simple linear
deterioration, Computers and Operations Research 21 (1994) 653-659.
16.Mosheiov, G., Scheduling jobs with step-deterioration: minimizing makespan
on single and multi-machine, Computers and Industrial Engineering 28 (1995)
869-879.
17.Mosheiov, G., shaped policies for schedule deteriorating jobs, Journal of
the Operational Research Society 47 (1996) 1184-1191.
18.Mosheiov, G., Multi-machine scheduling with linear deterioration,
Information 36 (1998) 205-214.
19.Mosheiov, G., Scheduling problems with a learning effect, European
Journal of Operational Research 132 (2001) 687-693.
20.Pinedo, M., Scheduling: Theory, Algorithms, and Systems, (2002) Prentice
Hall, Upper Saddle River, New Jersey.
21.Wu, C.C., Lee, W.C., Scheduling linear deteriorating jobs to minimize
makespan with an availability constraint on a single machine, Information
Processing Letters 87 (2003) 89-93.