臺灣博碩士論文加值系統

本研究主要討論n個工作(Job)多次迴流至單一批次處理機台(Batch processing machine)上加工之排程問題。所謂批次處理機台，指機台每次可同時處理至多b個工作，b表示批次處理機台的容量(Capacity)。在機台開始操作後，工作就不可移出或加入。在本問題中具有批次處理的特性，意味著數個作業可同時於批次處理機台操作，有別於一般的機台一次只能操作一個作業的現象；加入迴流特性意味著作業在製程中會重複拜訪某一機台多次，亦表示作業會重複拜訪批次處理機台多次；迴流特性對問題中作業的影響，是使後續作業的下線時間隨著前置作業上批次處理機台的先後，與作業迴流時間的長短而定。
本論文簡化了零工式生產環境之排程問題，將作業從批次處理機台加工後，至其他機台加工的時間，以作業迴流的時間替代。在此問題中，我們假設批次操作時間為一常數，且批次作業的操作時間小於作業最小的迴流時間之限制。此一假設符合半導體製程中蝕刻流程生產的現象，即批次操作時間為一常數，作業至其他機台加工的時間，大於在蝕刻流程中批次處理機台加工的時間。
由批次處理與迴流二特性推導出相關之命題，並由其命題發展出一演算法，此演算法可同時解決具有二種特性之排程問題，且找出問題的最佳解。本研究將演算法得到的最佳解，與非線性數學模式求得之最佳解作一比較。

目錄
目錄I
圖目錄 II
表目錄 III
第一章 緒論1
1.1研究背景與動機1
1.2問題敘述3
1.3 研究目的3
1.4研究方法及進行步驟4
1.4.1研究方法4
1.4.2進行步驟4
第二章 文獻回顧6
2.1含批次作業特性的排程文獻6
2.1.1 具下線和交貨時間限制的排程文獻6
2.1.2批量大小和順序的排程文獻8
2.2 含迴流作業特性的排程文獻10
2.2.1含迴流作業特性中具有中心機台的排程文獻10
2.2.2含迴流作業特性中不具有中心機台的排程文獻12
2.3解決零工式生產環境問題之排程文獻14
第三章 單一批次處理機台環境中工作含迴流特性之排程演算法 15
3.1 符號定義16
3.2 問題之特性17
3.3 分枝原則19
3.3.1 下限值之計算22
3.3.2 各項分枝原則命題23
3.4 含批次與迴流特性之演算法25
3.5 複雜度分析26
3.6 釋例 27
3.6.1工作含有相同的迴流時間之釋例 27
3.6.2工作有不同的迴流時間之釋例 34
第四章 非線性規劃數學模式 45
4.1符號定義 45
4.2 數學模式 46
4.3 數學模式之應用與比較 47
第五章 結論 50
5.1 研究貢獻 50
5.2研究限制 51
5.3 未來研究方向 51
參考文獻 52
附錄A：在半導體製程中使用批次處理機台的流程 55
附錄B：在Lingo數學模式軟體中迴流時間皆相同之限制式58
附錄C：在Lingo數學模式軟體中迴流時間不同之限制式60

(1) 莊達人，VLSI製程技術，高立圖書有限公司，1994年出版
(2) 趙蕙珍，半導體製程中具批次作業特性之排程問題，中央大學碩士
論文，1998.
(3) Ahmadi J. H., Ahmadi R. H., Dasu S., Tang C.S “Batching
and Scheduling Jobs on Batch and Discrete Processors,”
Operations Research, Vol. 39,No. 40, pp.750-763, Jul-Aug,
1992.
(4) Adams J., Balas E., and Zawack D., “The Shifting
Bottleneck Procedure For Job-Shop Scheduling,” Management
Science, Vol. 34, No. 3,pp. 391-401, 1988.
(5) Balas E., “Machine Sequencing Via Disjunctive Graphs: An
Implicit Enumeration Algorithm,” Operations Research, Vol.
17, pp. 941-957, 1968.
(6) Brucker P., “An Efficient Algorithm for The Job-Shop
Problem with Two Jobs,” Computing, Vol. 40, pp. 353-359,
1988.
(7) Carlier J., and Pinson E., “An Algorithm for Solving The
Job-Shop Problem,” Management Sciences, Vol.35, pp. 164-
176, 1989.
(8) Coffman E.G, A. Nozari, M. Yannakakis, “Optimal scheduling
of products with two subassemblies on a single machine,”
Operations Research, Vol. 37, No. 3, pp. 426-436, 1989.
(9) Coffman E.G, M. Yannakakis, “Batching sizing and job
sequencing on a single machine,” Annals of Operations
Research, Vol. 26, pp.135-147, 1990.
(10) Dobson G., S. U Karmarkar, J. L.Rummel, “Batching to
minimize flow times on one machine,” Management Sciences,
Vol. 33, No. 6, pp.784-799, June, 1987.
(11) Graves S. C., Meal H. C., Stefek D., and Zeghmi A. H.,
“Scheduling of Reentrant Flow Shops,” Journal of
Operations Management, Vol. 3, No. 4, pp.197-207, 1983.
(12) Gurnani H., Anupindi R., and Akella R., “Control of Batch
Processing system in Semiconductor Wafer Fabricatuin
Facilities,” IEEE Transactions on Semiconductor
Manufacturing, Vol. 5, No. 4, Nov. 1992.
(13) Glassey C. R., and Weng W. W., “Dynamic Batching
Heuristic for Simultaneous Processing,” IEEE Transactions
on Semiconductor Manufacturing, Vol. 4, No. 2, pp.77-82,
May., 1991.
(14) Hung H. H., Barzin N., Lewis F. L., “A Matrix Framework
For Controller Design for Reentrant Flow Scheduling,”
IEEE Transactions on Semiconductor Manufacturing,, pp.
1552-1563, Dec. 1994.
(15) Hochabaum D.S., D. Landy, “Scheduling with batching:
minimizing the weight number of tardy jobs,” Operations
Research Letters, Vol. 16, pp. 79-86, 1994.
(16) Hochabaum D.S., D. Landy, “Scheduling semiconductor burn-
in operations to minimize total flowtime,” Operations
Research, Vol. 45, No. 6, pp. 874-885, 1997.
(17) Hoitomt D. J., and Luh P. B., “Scheduling a Batch
Processing Facility,” International Conference On
Robotics and Automation Nice, pp.1167-1172, May, 1992.
(18) Ikura Y., Gimple M., “Efficient Scheduling Algorithm for
Single Batch Processing Machine,” Operations Research
Letters, Vol. 5, No. 2, pp. 61-65, Jul., 1986.
(19) Kubiak, W., Lou S. C., and Wang, Y.-M. “Mean Flow Time
Minimization in Re-entrant Job-Shop With Hub” Facility of
Management, University of Toronto, 1990.
(20) Kubiak, W., S. C. Lou, and Y.-M.Wang, “Mean flow time
minimization in reentrant job shops with hub” Operation
Research, Vol. 44, No. 5, pp. 764-776, Sept-Oct, 1996.
(21) Kumar P. R., “Scheduling Semiconductor Manufacturing
Plants,” IEEE Control System, pp. 33-40, Dec., 1994.
(22) Kaskavelis C. A., and Caramanis M. C., “Application of a
Lagrangian Relaxation Based Scheduling Algorithm to a
Semiconductor Testing Facility,” IEEE Transactions on
Semiconductor Manufacturing,, pp. 106-112, 1994.
(23) Lee C. Y., Uzsoy R., Martin-Vega L. A., and Leonard, P.
A., “Production Scheduling Algorithm For A Semiconductor
Facility,” IEEE Transactions on Semiconductor
Manufacturing, Vol. 4, No. 4, pp. 270-280, 1991.
(24) Lee C. Y., Uzsoy R., and Martin-Vega L. A, “Efficient
Algorithm for Scheduling Semiconductor Burn-In
Operation,” Operations Research, Vol. 40, No. 4, pp. 764-
775, Jul-Aug, 1992.
(25) Liao D. Y., Chang S.C., Yen S.R., and Chien C.C., “Daily
Scheduling for R&D Semiconductor Fabrication,” IEEE
Transactions on Semiconductor Manufacturing,, pp. 77-82,
1993.
(26) Mcmahon G. B., and Florian M. “On Scheduling with Ready
Times and Due Dates to Minimize Maximum Lateness,”
Operations Research, Vol. 23, pp. 247-482, 1975.
(27) Shallcross D. F., “A polynomial algorithm for a one
machine batching problem,” Operations Research Letters,
Vol. 11, pp. 213-218, 1992.
(28) Uzsoy R., Lee C. Y., Matrin-Vega L. A., “A Review of
Production and Scheduling Models in The Semiconductor
Industry, Part Ι: System Characteristic, Performance
Evaluation and Production Planning,” IEEE Transactions on
Semiconductor Manufacturing, Vol. 24, No. 4, pp. 270-280,
Sep., 1992.
(29) Wang M. Y., S. P. Sethi, S.L.V.D. Velde, “Minimizing
Makespan in a class of reentrant shops,” Operations
Research, Vol. 45, No.5, pp. 702-712 , 1997.