開放工廠(Open shop)排程是學術上熟知困難度極高的組合最佳化問題(Combinatorial optimization problem)，除了少數特例外，此類問題皆屬於NP-hard問題。總完工時間( Total Completion Time )是指當所有工件皆排入機器加工後，所有工件完工時間的總合。而本研究的目標就是要使總完工時間能越小越好。
排程問題在求取最佳解的時候，通常會利用分枝界限法( Branch and Bound )作為求解的方法。但在求取最佳解時，由於求解過程相當地繁雜且會耗去相當多的時間。因此，在分枝界限演算法中一個設計良好的下限值( Lower Bound )是非常重要的，因為下限值的品質越好，則可以刪除的無用分枝節點將越多，進而加快求解的速度。依本研究之結困顯示，品質越好的下限值可能會在每一分枝節點所需花費的時間也越多；而一品質較差的下限值在每一分枝節點所需的時間可能會較少，但其分枝節點卻相對地較多。本研究目的即是要探討下限值品質對於求解問題時效率的影響。
本研究也將發展對於利用分枝界限法求解此類問題的刪除法則( Dominance Rule )。由於過去的文獻中，尚無一可用且績效良好的刪除法則，使得在利用分枝界限法求解此類問題的最佳解時，必須要浪費釵h時間在無用的分枝節點上，也因而嚴重地影響求解的效率，而無法求解較大規模之問題。針對此點，本研究將發展一可用且績效良好的刪除法則，希望籍由刪除法則的幫助能加快求解的速度，進而提高解題的規模。

The open shop scheduling problem is a hard combinational optimization problem. Most variations of open shop scheduling problems are known to be NP-hard. Polynomial time algorithms only exist for a few special cases. In this research we study the non-preemptive open shop scheduling problem with the objective of minimizing total completion time, which is a strongly NP-hard problem.
An open shop can be defined as follows：a set of jobs must be processed by a set of machines where the order of jobs processed on each machine and the order of machines to which each job visits can be chosen arbitrary. Each machine can process at most one job at a time and each job can be processed on one machine at a time. We consider only the non-preemptive case; that is, the processing of each job on each machine cannot be interrupted.
In our research, we develop an upper bound based on a heuristic algorithm, and six lower bounds for the problem under consideration. We compare the performances of these six lower bounds using a branch and bound algorithm. We also discuss how these six lower bounds influence the performance of the branch and bound algorithm. A new dominance rule is also developed to help pruning unpromising nodes in the branch-and-bound search tree. Finally, computational experiments are conducted to evaluate the performances of the upper bound, lower bounds, and dominance rule.

中文摘要…………………………………………………………………I
英文摘要………………………………………………………………...II
誌謝……………………………………………………………………..III
目錄…………………………………………………………………..... IV
圖目錄……………………………………………………………………V
表目錄…………………………………………………………………..VI
第一章 緒論……………………………………………………………..1
1.1 研究背景與動機……………………………………………….....1
1.2 研究問題描述…………………………………………………….3
1.3 研究目的………………………………………………………….4
1.4 研究問題之定義………………………………………………….5
第二章 文獻探討…………………………………………………..……6
2.1 總完工時間……………………………………………………….6
2.2 開放工廠………………………………………………………….7
2.3 文獻整理………………………………………………………….9
第三章 研究方法與步驟…………………………………………...….11
3.1 符號定義………………………………………………………...12
3.2 下限值演算法……..………………………………………….…13
3.2.1下限值演算法(1)…………………………………………..14
3.2.2下限值演算法(2)…………………………………………..16
3.2.3下限值演算法(3)…………………………………………..17
3.2.4下限值演算法(4)…………………………………………..20
3.2.5下限值演算法(5)…………………………………………..22
3.2.6下限值演算法(6)…………………………………………..25
3.3 上限值演算法.………………………………………………..…26
3.4 分枝界限演算法……………………………………………...…30
3.4.1 分枝策略…………………………………………………..30
3.4.2 搜尋策略…………………………………………………..31
3.4.3不相關鄰近點法則….……………………………………..33
3.4.4新刪除法則……………………………………….………..34
第四章 實例驗證………………………………………………………37
4.1 二部機器之實例驗證…………………………………………...37
4-1-1 二部機器上下限值實例驗證…………………………….37
4-1-2 二部機器最佳解實例驗證……………………………….40
4.2 多部機器之實例驗證………………………………………...…43
4-2-1 工件數目等於機器數目上下限值實例驗證….……..…..43
4-2-2 工件數目大於機器數目上下限值實例驗證…………….44
4-2-3多部機器最佳解實例驗證………………………………..45
第五章　結論與建議………………………………………………….48
5-1結論………………………………………………………….48
5-2未來研究方向……………………………………………….49
參考文獻………………………………………………………………..50

參考文獻
[1] Emmons,H., “One Machine Sequencing To Minimize Mean Flow Time With Number Tardy,” Naval Research Logistics,Vol. 22,No.3, pp. 585-592. (1975).
[2] Koksalan, M., Azizoglu, M., Kondakci, and Koksalan,S., “Minimizing Flowtime And Maximum Earliness On A Single Machine,” IIE Transactions,Vol. 30,No.2,pp.192-200.(1998).
[3] Sung, C.S.A; Choung, Y.I.A, “Minimizing makespan on a single burn-in oven in semiconductor manufacturing.” European Journal of Operational Research, Vol. 120, Issue: 3 pp. 559-574.(2000).
[4] Garey, M. R., Johnson, D. S.and Sethi, R., “Complexity Of Flowshop And Jobshop Scheduling,” Mathematics Of Operations Research, Vol. 1, No.2, pp. 117-129(1976).
[5] Elever, D. A. and Tabue, L. R., “Time Completion For Various Dipatching Rules In Job Shops,”Omega, Vol. 11, No. 1, pp. 81-89.(1983).
[6] Sun, D. and Batta, R., “Scheduling Large Job Shops: A Decomposition Approach,” International Journal Of Production Economics, Vol. 34, No.7, pp. 2019-2033.(1996).
[7] Holthaus, O. and Rajendran, C., “Efficient Dispatching Rules For Scheduling In A Job Shop,” International Journal Of Production Economics, Vol. 48, No.1, pp. 87-105.(1997).
[8] Mocky, D.H.C. and Egbelu, P. J., “Minimizing Production Flow Time In A Process And Assembly Job Shop,” International Journal Of Production Economics, Vol. 36, No.8, pp. 2315-2332.(1998).
[9] Cheng, T.C.E, “Analysis Of Job Flow-Time In A Job Shop,” Journal Of The Optimal Research Society, Vol. 36, No.3, pp. 225-230(1983).
[10] Zaloom, V.and Vatz, D.,”Note On The Optimal Scheduling Of Two Parallel Processors,” Naval Research Logistics Quarterly, Vol.2,No.4,pp.823-827(1975).
[11] Sethi, R., “ On The Complexity Of Mean Flow Time Scheduling,” Mathematics Of Operations Research, Vol.2,No.4,pp.320-330(1977).
[12] Webster, S., “Weighted Flow Time For Scheduling Identical Processors,” European Journal of Operational Research, Vol.80, No.1, pp.103-111(1995).
[13] Azizoglu, M.and Kirku, O.,”On The Minimization Of Total Weighted Flow Time With Identical And Uniform Parallel Machines,” European Journal of Operational Research, Vol.113, No.1, pp.91-100(1999).
[14] Deman, V., John, M. and Baker, K. R., “Minimizing Mean Flow Time In The Flow Shop With No Intermediate Queues,” AIIE (American Institute Of Industrial Engineerings),Vol. 6, No. 1, pp. 28-34(1974).
[15] Croce, F.D., Narayan, V., and Tadei, R., “Two-machine Total Completion Time Flow Shop Problem”, European Journal Of Operational Research, Vol.90, No.2, pp.227-237 (1996).
[16] Ahmadi, R. H. and, Bagchi, U., “Improved Lower Bound For Minimizing The Sum Of Completion Time Of N Jobs Over M Machines In A Flow Shop,” European Journal Of Operational Research, Vol.44, No.3, pp.331-336 (1990).
[17] Szwarc, W., “Flow Shop Problem With Mean Completion Time Criterion”, IIE Transactions (Institute Of Industrial Engineerings), Vol.15, No.2, pp.172-176 (1983).
[18] Ho, J.C., and Chang, Y.L., “New Heuristic For N-Job, M-Machine Flow Shop Problem”, European Journal Of Operational Research, Vol.52, No.2, pp.194-202 (1991).
[19]Rajendran, C., “Heuristic Algorithm For Scheduling In A Flow Shop To Minimize Total Flowtime,” International Journal Of Production Economics,”Vol.29, No.1, pp.65-73(1993).
[20] Rajendran, C., and Ziegler, H., “Efficient Heuristic For Scheduling In A Flow Shop To Minimize Total Weight Flowtime Of Jobs,” European Journal Of Operational Research, Vol.103, No.1, pp.129-138 (1997).
[21] Woo, H.S., and Yeh, D.S., “Heuristic Algorithm For Mean Flowtime Objective In Flow Shop Scheduling”, Computers & Operations Research, Vol.25, No.3, pp.175-182 (1998).
[22] Gonzalez, T., and Sahni, S., “Open Shop Scheduling To Minimize Finish Time”, JACM, Vol.23, No.4, pp.665-679 (1976).
[23] Du, J. O. and Leung Y-T,” Minimizing Mean Flow Time In Two-Machine Open Shops And Flow Shops,” Journal Of Algorithms, Vol.14, pp.24-44(1993).
[24] Lawler, E. L., Lenstra, L. K., and Rinnooy Kan, A.H.G.,”Minimizing Maximum Lateness In A Two-Machine Open Shop,” Mathematics Of Operations Research, Vol.6, No.1, pp. 153-158.(1981).
[25] Achugbue, J. O. and Chin F. Y., “Scheduling The Open Shop To Minimize Mean Flow Time,” SIAM J. COMPUT., Vol.11, pp.709-720(1982).
[26] Brasel, T., Tautenhahn, T. and Werner, F.,”Constructive Heuristic Algorithms For The Open Shop Problem,” Computing, Vol.51, pp.95-110(1993).
[27] Gueret, C. and Prins, C., “Classical and New Heuristics For The Open-Shop Problem：A Computational Evaluation,” European Journal of Operational Research, Vol.107, pp.306-314.(1998).
[28] Liu Chang-Yung, “A Branch And Bound Algorithm For The Preemptive Open Shop Scheduling Problem”, Journal Of The Chinese InstituteOf Industrial Engineers, Vol.12, No.1, pp.25-31 (1995).
[29] Liaw, C.-F, “An Iterative Improvement Approach For The Non-preemptive Open Shop Scheduling Problem”, European Journal Of Operational Research, Vol.111, No.3, pp.509-517 (1998).
[30] Liaw, C.-F, “A Tabu Search Algorithm For The Open Shop Scheduling Problem”, European Journal Of Operational Research, Vol.26, No.2, pp.109-126 (1999).
[31] Liaw, C.-F, “Multi-machine Scheduling Problems”, Master thesis, Dept. of Industrial Management, National Cheng-Kung Univ., Taiwan (1987).
[32] Giffler B., Thompson G. L. “Algorithm for Solving Production Scheduling Problems,” Operation Research, Vol. 8, pp. 487-503. (1960).
[33] 林安祥,”開放工廠總加權延遲最小化排程問題之研究”,朝陽科技大學工業工程與管理碩士班碩士學位論文,1999.