過去的相關文獻探討不相關平行機台排程問題的限制與假設條件，大都將資源設定為無限的情況下，但在業界中，工件在機台上加工時，往往需要其他特定的資源去配合操作，且可用資源的數量通常是有限制的，因此在考量排程問題時，加入資源限制的考量才是符合業界真正的情況。這一類的問題大多都是複雜度極高的組合最佳化問題，計算此類問題時，除了少數的題型外，利用最佳化的方法，大部分都需要相當長的時間才能取得最佳解，因此欲發展一個有效率的方式去取得最佳解。
本研究是使用最佳化方法中的分支界限法，依照資源限制以及考量機台的相依整備時間，建構一個以加權完工時間最小化為目標的不相關平行機台排程模式。為了增加求解的效率，本研究針對此問題，發展出不同的分支方式，一般的分支方法大都以工件去發展分支，而本研究根據例題的特性，利用資源去發展分支，並配合動態排程去選擇工件，利用基因演算法的近似最佳解做為上界值，並且根據問題的特性去發展分支界限法。本研究根據例題的大小以及例題的結構來設計不同的測試例題，藉著測試例題的結果，可以說明以資源去發展出來的分支界限法的求解效率較佳。

When considering machine scheduling problems, it is usually assumed that only available machines are required for the processing of jobs. However, in many practical cases, additional resources such as operators, part holders, or tools, are needed when processing jobs and the amount of these resources are limited. Therefore, one needs to put resource constraints into consideration in order to form feasible job schedules. Parallel machine scheduling problems become more complicated when resource constraints are involved. The goal of this study is to develop effective algorithms that can find optimal solution to the problems with reasonable computation time.

This study applies branch and bound approach on unrelated parallel machine scheduling problem with constrained resources. Sequence-dependent setup time is also considered and the objective is to minimize weighted completion time. Two algorithms are developed. In the first algorithm, the search tree is formed according to the assignment of jobs on machines. The second algorithm, on the other hand, is resource oriented. That is, the branches are formed as resources are assigned to machines. The solutions obtained by applying genetic algorithm are used as the upper bounds in the branch and bound algorithms. A variety of numerical examples are designed with different sizes and resource strength. Numerical experiments are conducted to evaluate the performance of the proposed algorithms.

摘要 i
Abstract ii
致謝 iv
目錄 v
表目錄 vii
圖目錄 ix
第一章、緒論 1
1.1研究背景與動機 1
1.2 研究問題描述 2
1.3研究目的 3
1.4研究步驟與架構 4
第二章、文獻探討 6
2.1平行機台排程問題之探討 6
2.1.1平行機台的類型 6
2.1.2不相關平行機台之相關文獻整理 7
2.1.3 處理排程問題之技術 10
2.2數學規劃 11
2.3分支界限演算法 12
2.3.1 分支界限法的各項策略 13
2.3.2 分支界限法在不相關平行機台相關文獻 15
2.4 本章總結 17
第三章、研究方法 18
3.1問題描述 18
3.1.1問題描述 18
3.1.2限制與假設條件 20
3.2 不相關平行機台排程問題數學模型 21
3.2.1 有限資源下的不相關平行機台排程問題數學模型 21
3.2.2 目標式與限制式說明 23
3.3 以工件為考量的分支界限法 25
3.4 以資源為優先考量的分支界限法 35
3.5 最佳化驗證 39
3.6 本章總結 39
第四章、測試例題說明 40
4.1 測試例題說明 40
4.2 小型例題 43
4.2.1 JB法在小型例題下 44
4.2.2 RB法在小型例題下 46
4.2.3 上界值和最佳解的誤差率 49
4.2.4 JB法和RB法在小型例題下的比較 50
4.3 中型例題 51
4.3.1 JB法在中型例題下 51
4.3.2 RB法在中型例題下 54
4.3.3 上界值和最佳解的誤差率 56
4.3.4 JB法和RB法在中型例題下的比較 57
4.4 大型例題 57
4.4.1 JB法在大型例題下 58
4.4.2 RB法在大型例題下 60
4.4.3 上界值和最佳解的誤差率 62
4.4.4 JB法和RB法在大型例題下的比較 63
4.5 JB法與RB法的比較 64
4.6 其他比較與分析 66
4.6.2 分支界限法和數學規劃法比較 67
4.6.3 無權重的情形下上界值和最佳解的差異比 68
第五章、結論與未來研究建議 70
5.1 研究結論 70
5.2 未來研究建議 71
參考文獻 73
附錄 76

1.劉志宏，「不確定加工時間之平行機台排程」，清華大學工業工程與工程管理研究所，碩士論文 (1999)。
2.田國興，「有設置時間之流程型工廠多階段平行機台總排程時間最小化問題」，中原大學工業工程研究所，碩士論文 (1999)。
3.徐智遠，「DRAM模組廠SMT線排程問題之研究」，台灣科技大學工業管理研究所，碩士論文 (2006)。
4.張偉立，「利用分之界限法求解多資源零工事生產排程」，清華大學工業工程與工程管理研究所，碩士論文 (2004)。
5.林淳菁，「應用遺傳基因演算法求解不相關平行機台之排程問題」，朝陽科技大學工業工程與管理研究所，碩士論文 (2000)。
6.吳思農，「模擬退火法於有限資源下不相關平行機台排程問題之應用」，元智大學工業工程與管理研究所，碩士論文 (2005)。
7.蕭陳鴻，「基因演算法於非等效平行機台排程之應用」，元智大學工業工程研究所，碩士論文 (2000)。
8.葉麗芬，「雙目標非等效平行機台排程問題之探討」，元智大學工業工程與管理研究所，碩士論文 (2001)。
9.鄭志傑，「基因演算法於有限資源下不相關平行機台排程問題之應用」，元智大學工業工程與管理研究所，碩士論文 (2006)。
10.Allahverdi, A. and J. Mittenthal, “Scheduling on M parallel machines subject to random breakdowns to minimize expected mean flow time,” Naval Research Logistics, 41, 677-682 (1994).
11.Anagnostopoulos, G. C. and G. Rabadi, “A simulated annealing algorithm for the unrelated parallel machine scheduling problem,” Proceeding of the world automation congress, Orlando, Florida, June 9-13 (2002).
12.Azizoglu, M. and O. Kirca, “Tardiness minimization on parallel machines ,” International Journal of production Economics, 55, 163-168(1998)
13.Azizoglu, M. and O. Kirca, “Scheduling jobs on unrelated parallel machines to minimize regular total cost functions,” IIE Transactions, 31, 153-159 (1999).
14.Azizoglu, M. and S. Webster, “Scheduling parallel machines to minimize weighted flowtime with family set-up times,” International Journal of Production Research, 41, 1199-1215(2003).
15.Baker, K. R., Introduction to Sequence and Scheduling (John Wiley & Sons, New York, NY 1974).
16.Bank, F., “Heuristic algorithms for unrelated parallel machine scheduling with a common due date, release dates, and linear earliness and tardiness penalties,” Mathematical and Computer Modeling, 33, 363-383 (2001).
17.Barker, J. R., and G. B. McMahon, “Scheduling the general job-shop,” Management Science, 31, 594-598(1985).
18.Dastidar, S. G. and R. Nagi, “Scheduling injection molding operations with multiple resource constraints and sequence dependent setup times and costs,” Computers & Operations Research, 32, 2987-3005 (2005).
19.Davis, E. and J. M. Jaffe, “Algorithms for scheduling tasks on unrelated processors,” Journal of Association for Computing Machinery, 28, 721-736 (1981).
20.Dessouky, M. M., “Scheduling identical jobs with unequal ready times on uniform parallel machines to minimize the maximum lateness,” Computers & Industrial Engineering, 34, 793-803, (1998).
21.Dunstall, S. and A. Wirth, “A comparaisoms for a family scheduling problem with identical parallel machinesn of branch-and bound algorith,” European Journal of Operational Research, 167, 283-296 (2005).
22.Ghedjati, F., “Genetic algorithms for the job-shop scheduling problem with parallel constraints: heuristic mixing method machines and precedence,” Computers & Industrial Engineering, 37, 39-42 (1999).
23.Graham, R. L., E. L. Lawler, J. K. Lenstra and A. H. K. Rinnooy Kan, “Optimization and approximation in deterministic sequence and scheduling theory: a survey,” Annals of Discrete Mathematics, 5, 287-326 (1979).
24.Kim, D., K. Kim, W. Jang and F. Chen, “Unrelated parallel machine scheduling with setup times using simulated annealing,” Robotics and Computer Integrated Manufacturing, 18, 223-231 (2002).
25.Kim, D., D. Na and F. Chen, “Unrelated parallel machines scheduling with setup times and a total weighted tardiness objective,” Robotics and Computer Integrated Manufacturing, 19, 173-181 (2003).
26.Lageweg, B. J., J. K. Lenstra, and A. H. G. Rinnooy Kan, “Job-shop scheduling by implicit enumeration,” Management Science, 24 , 441-450(1977).
27.Lee, H. and M. Guignard, “A hybrid bounding procedure for the workload allocation problem on parallel unrelated machines with setups,” Journal of the Operational Research Society, 47, 1247-1261 (1996).
28.Liaw, C., Y. Lin, C. Cheng and C. Minchin, “Scheduling unrelated parallel machines to minimize total weight tardiness,” Computers & Operations Research, 30, 1777-1789 (2003).
29.Martello, S., F. Soumis and P. Toth, “Exact and approximation algorithms for makespan minimization on unrelated parallel machines,” Discrete Applied Mathematics, 75, 169-188 (1997).
30.Piersma, N. and W. Dijk, “A local search heuristic for unrelated parallel machine scheduling with efficient neighborhood search,” Mathematical and Computer Modeling, 24, 11-19 (1996).
31.Shim, S. –O. and Y. –D. Kim, “Minimizing total tardiness in an unrelated parallel-machine scheduling problem,” Journal of the Operational Research Society, 58 (3), 346-354 (2006).
32.Srivastava, B., “An effective heuristic for minimizing makespan on unrelated parallel machines,” The Journal of the Operational Research Society, 49, 886-894 (1998).
33.Schutten, J. M. J. and R.A.M. Leussink, “Parallel machines scheduling with release date, due dates and family setup times,” International journal of Production Economics, 46-47, 119-125 (1996).
34.Yalaoui, F. and C. Chu, “New exact method to solve the Pm/rj/∑Cj schedule problem ,” International Journal of Production Economics, 100, 168-179 (2006).