臺灣博碩士論文加值系統

排程理論之研究是希望將生產線上的工作透過數理分析，幫助規劃出最適當之排程決策，有效地提升生產效能。本篇研究主題是以「雙機流線型批次排程」做為探討之方向，假設生產線上之工作是以批次的型式進入機器中處理，並且所有工作都需依序經過兩種不同的處理程序才可完成。我們將工作的完成時間定義為其被包含批次之完成時間，並且每一批次進行處理前都需花費一段批次的前置設定時間。針對這樣的排程問題找出最佳的批次組合及批次處理順序，而使得所有工作的總完工時間最短。研究中我們提出了一些最佳解的排程性質，並設計動態規劃演算法及分支與界定法求解最佳排程。由於考量大批工作進行處理時不易在短時間內求得最佳解，我們應用了模擬退火及禁制搜尋法求解排程近似解。根據實驗結果，我們發現此兩種經驗法則都能在合理的時間範圍內，產生高品質的排程近似解。

In this thesis we study a batch scheduling problem in a two-machine flowshop that consists of two batch processors arranged in a pipelined way. There is a set of independent jobs to be grouped for processing, and the completion time of a job is defined as the completion time of the batch containing it. A constant setup time is incurred whenever a batch is formed on the batch processors. This problem seeks to find a batch composition and the sequence of the batches so that the total completion time of the jobs is minimized. We first demonstrate some optimality properties, and then present a dynamic programming algorithm and a branch-and-bound scheme to solve this problem. Two well-known heuristics, tabu search and
simulated annealing, are adopted for deriving approximate solutions. Our computational experiments evince that the structural properties are very effective in finding optimal solutions. Furthermore, the proposed heuristic algorithms can produce quality approximate solutions in a reasonable time.

Chapter 1 Introduction
Chapter 2 Literature Review and Problem Formulation
Chapter 3 Efficient Algorithm for a Special Case
Chapter 4 Finding an Optimal Solution
Chapter 5 Heuristic Algorithms
Chapter 6 Experiments and Analysis
Chapter 7 Conclusions
Bibliography

[1] J.H. Ahmadi, R.H. Ahmadi, S. Dasu and C.S. Tang, Batching and scheduling jobs on batch and discrete processors, Operations Research, Vol. 39, No. 4, July-August 1992, pp. 750-763.
[2] S. Albers and P. Brucker, The complexity of one-machine batching problems, Discrete Applied Mathematics, Vol. 47, 1993, pp. 87-107.
[3] A. Allahverdi, J.N.D. Gupta and T. Aldowaisan, A review of scheduling research involving setup considerations, Omega, Vol. 27, 1999, pp. 219-239.
[4] R.A. Armentano and D.P. Ronconi, Tabu search for total tardiness minimization in flowshop scheduling problems, Computers & Operations Research, Vol. 26, 1999, pp. 219-235.
[5] K.R. Baker, Lot streaming in the two-machine flow shop with setup times, Annals of Operations Research, Vol. 57, 1995, pp. 1-11.
[6] P. Brucker, A. Gladky, H. Hoogeveen, M.Y. Kovalyov, C.N. Potts, T. Tautenhahn and S.L. Van De Delde, Scheduling a batching machine, Journal of Scheduling, Vol. 1, 1998, pp. 31-54.
[7] T.C.E. Cheng, Z.-L. Chen, M.Y. Kovalyov and B.M.T. Lin, Parallel-machine batching and scheduling to minimize total completion time, IIE Transactions, Vol. 28, 1996, pp. 953-956.
[8] T.C.E. Cheng, J.N.D. Gupta and G. Wang, A review of flowshop scheduling research with setup times, to appear in Production and Operations Management, 1999.
[9] T.C.E. Cheng, B.M.T. Lin and A. Toker, Makespan minimization in the two-machine flowshop batch scheduling problem, Technical Report No. 04/95-96, Department of Management, The Hong Kong Polytechnic University, 1996.
[10] E.G.Jr. Coffman, A. Nozari and M. Yannakakis, Optimal scheduling of products with two subassemblies on a single machine, Operations Research, Vol. 37, No. 3, May-June 1989, pp. 426-436.
[11] E.G.Jr. Coffman, M. Yannakakis, M.J. Magazine and C. Santos, Batch sizing and job sequencing on a single machine,
Annals of Operations Research, Vol. 26, 1990, pp. 135-147.
[12] R.W. Conway, W.L. Maxwell and L.W. Miller, Theory of Scheduling, Addison Wesley, Reading, MA., 1967.
[13] M.R. Garey, D.S. Johnson and R. Sethi, The complexity of flowshop and jobshop scheduling, Mathematics of Operations Research, Vol. 1, 1976, pp. 117-129.
[14] F. Glover, Tabu search: a tutorial, Interfaces, Vol. 20, No. 4, 1990, pp. 74-94.
[15] S.M. Johnson, Optimal two- and three-stage production schedules with setup times included, Naval Research Logistics Quarterly, Vol. 1, 1954, pp. 61-67.
[16] S. Kirkpatrick, C.D. Gelatt and M.P. Vecchi, Optimization by simulated annealing, Science, Vol. 220, 1983, pp. 671-680.
[17] C.Y. Lee, L. Lei and M. Pinedo, Current trends in deterministic scheduling, Annals of Operations Research, Vol. 70, 1997, pp. 1-41.
[18] C.Y. Lee, R. Uzsoy and L.A. Martin-Vega, Efficient algorithms for scheduling semiconductor burn-in operations, Operations Research, Vol. 40, 1992, pp. 764-775.
[19] B.M.T. Lin and T.C.E. Cheng, Two-machine flowshop batching and scheduling, Technical Report No. 18/97-98, Department of Management, The Hong Kong Polytechnic University, 1998.
[20] M. Pinedo, Scheduling Theory, Algorithms, and Systems, Prentice Hall, New Jersey, 1995.
[21] S. Webster and K.R. Baker, Scheduling groups of jobs on a single machine, Operations Research, Vol. 43, No. 4, July-August 1995, pp. 692-703.