臺灣博碩士論文加值系統

本文旨在討論平行機上最大完工時間極小化的問題。我們討論三種不同的平行機情況，分別是機器具有不同的加工速率，在加工過程有受限時段 (availability constraint) 的考慮，以及所有可行解具有最小流程時間的限制。以字典搜尋法 (lexicographic search) 與這些問題的特性為基礎，本文發展出所有討論問題的最佳解演算法。雖然這些演算法具有指數性的計算複雜度，但求解大工件數的問題是相當有效率的，在很短的時間內，可求解1000個工件的題目。
以下針對這三種不同的平行機問題加以說明。首先，本文討論兩部等比率平行機 (uniform parallel machines) 最大完工時間的問題。當討論觀點由完工時間轉移到機器上的工作負荷 (workload) 時，本問題可視為一種特殊情況的雙平行機問題。所以，在我們提出特殊雙平行機問題的演算法，這等比率平行機問題的演算法也就可以得到。
其次，我們考慮雙平行機最大完工時間的問題，每部機器上都有個固定且已知的受限時段，在這些時段中機器是無法加工的。在分析過程中，先設定三個假設，提出一個共同的最佳解演算法，緊接著逐一將假設移除，進而討論其他的各種情況。在大多數情況的最佳解演算法，都可以直接修改共同演算法而獲得。
最後，本文討論多部平行機在最小流程時間限制下，最大完工時間極小化的問題。我們先提出一個多平行機最大完工時間的最佳解演算法，在最小流程時間限制下，再以這演算法與最大完工時間的新下界限，發展出本問題的演算法。上述所得到的結果，也可以處理加權平均流程時間與最大完工時間的多平行機問題。

We study the makespan minimization problems on parallel machines. Three particular problems are under consideration: machines with different processing speeds, availability constraints on processing plan, and feasible solutions under minimum flowtime. Base on lexicographic search and the associated properties, we propose the optimal algorithms to the considered problems. Although all the developed algorithms have exponential time complexities, they are quite efficient in solving large-sized problems. Computational results for problems with up to 1000 jobs are reported.
The three considered problems are described as follows. First, we consider the two uniform parallel machine problem with makespan minimization. The problem can be transformed into a special problem of two identical parallel machines from the viewpoint of workload instead of completion time. An optimal algorithm is developed for the transformed special problem.
Second, we consider a two identical parallel machine problem with the objective of minimizing makespan, where each machine has an unavailable period. The unavailable time periods are fixed and known in advance. We first develop a main algorithm for the problem under certain assumptions. Then, we discuss the various cases of the problem by relaxing the assumptions. The corresponding optimal algorithms reduced from the main algorithm are proposed.
Finally, we consider the identical parallel machine problem with makespan minimization subject to minimum total flowtime. We first develop an optimal algorithm to the identical parallel machine problem with the objective of minimizing makespan. Based on the algorithm, an optimal algorithm, using new lower bounds, to the considered problem is developed. The result of this study can also be used to solve the bicriteria problem of minimizing the weighted sum of makespan and mean flowtime.

中文摘要 i
英文摘要 ii
誌謝 iv
目錄 v
表目錄 viii
圖目錄 ix
第一章 導論 1
1.1. 研究動機與目的 1
1.2. 研究限制條件 3
1.3. 論文架構 4
第二章 文獻探討 6
2.1. 相同平行機 6
2.2. 等比率平行機 10
2.3. 受限時段考量的平行機 11
2.4. 雙準則排程的平行機 13
第三章 等比率雙平行機最大完工時間之問題 15
3.1. 前言 15
3.2. 一個特殊的平行機問題 16
3.2.1. P(s) 問題 16
3.2.2. P(s) 演算法 17
3.2.3. P(s) 演算法計算範例 20
3.3. 等比率雙平行機問題 21
3.3.1. TUMO演算法 23
3.3.2. TUMO演算法計算範例 26
3.4. 計算結果 26
第四章 雙平行機在受限時段限制下的最大完工時間問題 35
4.1. 前言 35
4.2. 雙平行機最大完工時間的問題 36
4.3. 平行機在受限時段下最大完工時間 37
4.3.1 TIMAC演算法 40
4.4. 其他情況的討論 41
4.4.1. 移除第一項假設 ( ) 42
4.4.2. 再移除第二項假設 ( ) 47
4.4.3. 再移除第三項假設 ( ) 52
4.5. 計算結果 52
第五章 多平行機在最小流程時間下最大完工時間的問題 55
5.1. 前言 55
5.2. 多平行機最大完工時間的問題 56
5.2.1. m-IMO演算法 57
5.2.2. m-IMO演算法計算範例 60
5.3. 在最小流程時間下最大完工時間的極小化問題 63
5.3.1. 最大完成時間下界限的討論 65
5.3.2. m-MHO演算法 67
5.3.3. m-MHO演算法計算範例 68
5.4. 計算結果 71
第六章 結論與後續研究 79
6.1 結論 79
6.2 後續研究 80
參考文獻 83
附錄 92

1. Abdekhodaee, A.H. and Wirth, A. (2002) Scheduling parallel machines with a single server: Some solvable cases and heuristics. Computers & Operations Research, 29, 295-315.
2. Adamopoulos, G.I. and Pappis, C.P. (1998) Scheduling under a common due-date on parallel unrelated machines. European Journal of Operational Research, 105, 494-501.
3. Alidaee, B. and Rosa, D. (1997) Scheduling parallel machines to minimize total weighted and unweighted tardiness. Computers & Operations Research, 24, 775-788.
4. Azizoglu, M. and Kirca, O. (1998) Tardiness minimization on parallel machines. International Journal of Production Economics, 55, 163-168.
5. Azizoglu, M. and Kirca, O. (1999a) On the minimization of total weighted flow time with identical and uniform parallel machines. European Journal of Operational Research, 113, 91-100.
6. Azizoglu, M. and Kirca, O. (1999b) Scheduling jobs on unrelated parallel machines to minimize regular total cost functions. IIE Transactions, 31, 153-159.
7. Balakrishnan, N., Kanet, J.J., and Sridharan S.V. (1999) Early/tardy scheduling with sequence dependent setups on uniform parallel machines. Computers & Operations Research, 26, 127-141.
8. Blazewica, J., Finke, G., Haupt, R., and Schmidt, G. (1988) New tends in Machine Scheduling. European Journal of Operational Research, 37, 303-317.
9. Bruno, J.L., Coffman, E.G., and Sethi, R. (1974) Algorithms for minimizing mean flow time. Proceedings of the International Federation for Information Processing Congress 74, Amsterdam: North-Holland, p. 504-10.
10. Chen, B. (1991) Parametric bounds for LPT scheduling on uniform processors. Acta Mathematicae Applicatae Sinicia, 7, 67-73.
11. Chen, Z.L. and Lee, C.Y. (2002) Parallel machine scheduling with a common due window. European Journal of Operational Research, 136, 512-527.
12. Chen, Z.L. and Powll W.B. (1999) A column generation based decomposition algorithm for a parallel machine just-in-time scheduling problem. European Journal of Operational Research, 116, 220-232.
13. Cheng, R. and Gen M. (1997) Parallel machine scheduling problems using memetic algorithms. Computers & Industrial Engineering, 33, 761-764.
14. Cheng, T.C.E., Chen, Z.L., Kovalyov, M.Y. and Lin, B.M.T. (1996) Parallel-machine batching and scheduling to minimize total completion time. IIE Transactions, 28, 953-956.
15. Cheng, T.C.E. and Diamond J.E. (1995) Scheduling two job classes on parallel machines. IIE Transactions, 27, 689-693.
16. Cheng, T.C.E., and Sin, C.C.S. (1990) A state-of-the-art review of parallel-machine scheduling research. European Journal of Operational Research, 47, 271-292.
17. Coffman, E.G., Garey, M.R., and Johnson, D.S. (1978) An application of bin-packing to multiprocessor scheduling. SIAM Journal of Computing, 7, 1-17.
18. Coffman, E.G. and Sethi, R. (1976) Algorithms minimizing mean flow time: schedule length properties. Acta Informatica, 6, 1-14.
19. Conway, R.W., Maxwell, W.L., and Miller, L.W. (1967) Theory of Scheduling. Reading. MA: Addison-Wesley.
20. Dell’Amico, M. and Martello, S. (1995) Optimal scheduling of tasks on identical parallel processors. ORSA Journal of Computing, 7, 191-200.
21. Diamond, J.E. and Cheng, T.C.E. (2000) Error bound for common due date assignment and job scheduling on parallel machines. IIE Transactions, 32, 445-448.
22. Dileepan, P. and Sen, T. (1988) Bicriteria static scheduling research for a single machine. Omega, 16, 53-59.
23. Dobson, G. (1984) Scheduling independent tasks on uniform processors. SIAM Journal of Computing, 13, 705-716.
24. Eck, B.T. and Pinedo, M. (1993) On the minimization of the makespan subject to flowtime optimality. Operations Research 41, 797-801.
25. Friesen, D.K. (1987) Tighter bounds for LPT scheduling on uniform processors. SIAM Journal of Computing, 16, 554-560.
26. Friesen, D.K. and Langston, M.A. (1983) Bounds for Multifit scheduling on uniform processors. SIAM Journal of Computing, 12, 60-70.
27. Fry, T., Armstrong, R., and Lewis, H. (1989) A framework for single machine multiple objective sequencing research. Omega, 17, 595-607.
28. Gabrel, V. (1995) Scheduling jobs within time windows on identical parallel machines: New model and algorithms. European Journal of Operational Research, 83, 320-329.
29. Garey, M.R. and Johnson, D.S. (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco.
30. Graham, R.L. (1969) Boundaries on multiprocessing timing anomalies. SIAM Journal of Applied Mathematics, 17, 416-429.
31. Gupta, J.N.D. and Ho, J.C. (2001) Minimizing makespan subject to minimum flowtime on two identical parallel machines. Computers & Operations Research, 28, 705-717.
32. Gupta, J.N.D., Ho, J.C., and Webster, S. (2000) Bicriteria optimisation of the makespan and mean flowtime on two identical parallel machines. Journal of the Operational Research Society, 51, 1330-1339.
33. Gupta, J.N.D. and Ruiz-Torres, A.J. (2000) Minimizing makespan subject to minimum total flow-time on identical parallel machines. European Journal of Operational Research, 125, 370-80.
34. Gupta, J.N.D., Neppalli, V.R., and Werner, F. (2001) Minimizing total flow time in a two-machine flowshop problem with minimum makespan. International Journal of Production Economics, 69, 323-338.
35. He, Y. (1998) Parametric LPT-bound on parallel machine scheduling with nonsimultaneous machine available time. Asia-Pacific Journal of Operational Research, 15, 29-36.
36. Herrmann, J., Proth, J.M., and Sauer, N. (1997) Heuristics for unrelated machine scheduling with precedence constraints. European Journal of Operational Research, 102, 528-537.
37. Ho, J.C. and Chang, Y.L. (1995) Minimizing the number of tardy jobs for m parallel machines. European Journal of Operational Research, 84, 343-355.
38. Ho, J.C. and Wong, J.S. (1995) Makespan minimization for m parallel identical processors. Naval Research Logistics, 42, 935-948.
39. Hochbaum, D.S. and Shmoys, D.B. (1988) A polynomial approximation scheme for scheduling on uniform processors: using the dual approximation approach. SIAM Journal of Computing, 17, 539-551.
40. Horowitz, E. and Sahni, S. (1976) Exact and approximate algorithms for scheduling Nonidentical processors. Journal of the Association for Computing Machinery, 23, 317-327.
41. Kellerer, H. (1998) Algorithms for multiprocessor scheduling with machine release times. IIE Transactions, 30, 991-999.
42. Kovalyov, M.Y., Shafransky, Y.M. (1997) Batch scheduling with deadlines on parallel machines: An NP-hard case. Information Processing Letters, 64, 69-74.
43. Kravchenko, S.A. and Werner, F. (2001) A heuristic algorithm for minimizing mean flow time with unit setups. Information Processing Letters, 79, 291-296.
44. Kurz, M.E. and Askin, R.G. (2001) Heuristic scheduling of parallel machines with sequence-dependent set-up time. International Journal of Production Research, 39, 3747-3769.
45. Lancia, G. (2000) Scheduling jobs with release dates and tails on two unrelated parallel machines to minimize the makespan. European Journal of Operational Research, 120, 277-288.
46. Lee, C.Y. (1991) Parallel machines scheduling with nonsimultaneous machine available time. Discrete Applied Mathematics, 30, 53-61.
47. Lee, C.Y. (1996) Machine scheduling with an availability constraint. Journal of Global Optimization, 9, 395-416.
48. Lee, C.Y. (1999) Two-machine flowshop scheduling with availability constraints. European Journal of Operational Research, 114, 420-429.
49. Lee, C.Y. and Chen, Z.L. (2000) Scheduling jobs and maintenance activities on parallel machines. Naval Research Logistics, 47, 145-165.
50. Lee, C.Y., He, Y. and Tang, G. (2000) A note on “parallel machine scheduling with non-simultaneous machine available time”. Discrete Applied Mathematics, 100, 133-135.
51. Lee, C.Y. and Massey, J.D. (1988) Multiprocessor scheduling: an extension of the MULTIFIT algorithm. Journal of Manuf. Systems, 7, 25-32.
52. Lee, C.Y., Lei, L., and Pinedo, M. (1997) Current trends in deterministic scheduling. Annals of Operations Research, 70, 1-41.
53. Lee, C.Y. and Liman, S.D. (1993) Capacitated two-parallel machines scheduling to minimize sum of job completion times. Discrete Applied Mathematics, 41, 211-22.
54. Lee, Y.H. and Pinedo, M. (1997) Scheduling jobs on parallel machines with sequence-dependent setup times. European Journal of Operational Research, 100, 464-474.
55. Lenstra, J.K., Rinnooy, K. A.H.G., and Brucker, P. (1977) Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1, 342-362.
56. Leung, J.Y-T. and Young, G.H. (1989) Minimizing schedule length subject to minimum flow time. SIAM Journal of Computing, 18, 314-326.
57. Li, C.L. (1995) A heuristic for parallel machine scheduling with agreeable due dates to minimize the number of late jobs. Computers & Operations Research, 22, 277-283.
58. Liao, C.J., Shyur, D.L., and Lin, C.H. (2001) Makespan minimization for two parallel machines with an availability constraint. Working paper, Department of Industrial Management, National Taiwan University of Science and Technology, Taiwan.
59. Liu, Z., Yu, W., and Cheng T.C.E. (1999) Scheduling groups of unit length jobs on two identical parallel machines. Information Processing Letters, 69, 275-281.
60. Mireault, P., Orlin, J.B., and Vohra, R.V. (1997) A parametric worst case analysis of the LPT heuristic for two uniform machines. Operations Research, 45, 116-125.
61. Mohri, S., Masuda, T., and Ishii, H. (1999) Bi-criteria scheduling problem on three identical parallel machines. International Journal of Production Economics, 60-61, 529-536.
62. Mokotoff, E. (2001) Parallel machine scheduling problems: a survey. Asia-Pacific Journal of Operational Research, 18, 193-242.
63. Mokotoff, E. and Chretienne, P. (2002) A cutting plane algorithm for the unrelated parallel machine scheduling problem. European Journal of Operational Research, 141, 515-525.
64. Mosheiov, G. (1994) Minimizing the sum of job completion times on capacitated parallel machines. Mathematical of Computer Modelling, 20, 91-99.
65. Nagar, A., Haddock, J. and Heragu, S. (1995) Multiple and bicriteria scheduling: a literature survey. European Journal of Operational Research, 81, 88-104.
66. Park, M.W. and Kim, Y.D. (1997) Search heuristics for a parallel machine scheduling problem with ready times and due dates. Computers & Industrial Engineering, 33, 793-796.
67. Park, Y., Kim, S. and Lee, Y.H. (2000) Scheduling jobs on parallel machines applying neural network and heuristic rules. Computers & Industrial Engineering, 38, 189-202.
68. Pinedo, M. (2002) Scheduling: Theory, Algorithms, and System. Second edition, Prentice-Hall, Englewood Cliffs, NJ.
69. Ruiz-Torres, A.J., Enscore, E.E., and Barton, R.R. (1997) Simulated annealing heuristics for the average flow-time and the number of tardy jobs bi-criteria identical parallel machine problem. Computers & Industrial Engineering, 33, 257-260.
70. Sanlaville, E. and Schmidt, G. (1998) Machine scheduling with availability constraints. Acta Informatica, 35, 795-811.
71. Sarin, S.C. and Hariharan, R. (2000) A two machine bicriteria scheduling problem. International Journal of Production Economics, 65, 125-139.
72. Schmidt, G. (1984) Scheduling on semi-identical processors. Zeitschrift für Operations Research, 28, 153-162.
73. Schmidt, G. (1988) Scheduling independent tasks with deadlines on semi-identical processors. Journal of the Operational Research Society, 39, 271-277.
74. Schmidt, G. (2000) Scheduling with limited machine availability. European Journal of Operational Research, 121, 1-15.
75. Schutten, J.M.J. and Leussink R.A.M. (1996) Parallel machine scheduling with release dates, due dates and family setup times. International Journal of Production Economics, 46-47, 119-125.
76. Sivrikaya-Serifoglu, F. and Ulusoy, G. (1999) Parallel machine scheduling with earliness and tardiness penalties. Computers & Operations Research, 26, 773-787.
77. Suer, G.A., Pico, F., and Santiago, A. (1997) Identical machine scheduling to minimize the number of tardy jobs when lot-splitting is allowed. Computers & Industrial Engineering, 33, 277-280.
78. Suresh, V. and Chaudhuri, D. (1996) Bicriteria scheduling problem for unrelated parallel machines. Computers & Industrial Engineering, 30, 77-82.
79. Sun, H. and Wang, G. (2003) Parallel machine earliness and tardiness scheduling with proportional weights. Computers & Operations Research, 30, 801-808.
80. T’kindt, V. and Billaut, J.C. (2001) Multicriteria scheduling problem: a survey. RAIRO Operations Research, 35, 143-63.
81. Webster, S. and Azizoglu, M. (2001) Dynamic programming algorithm for scheduling parallel machines with family setup times. Computers & Operations Research, 28, 127-137.
82. Wang, G. and Cheng, T.C.E. (2000) Parallel machine scheduling with batch delivery costs. International Journal of Production Economics, 68, 177-183.
83. Weng, M.X., Lu, J., and Ren, H. (2001) Unrelated parallel machine scheduling with setup consideration and a total weighted completion time objective. International Journal of Production Economics, 70, 215-226.
84. Xiao, W.Q. and Li, C.L. (2002) Approximation algorithms for common due date assignment and job scheduling on parallel machines. IIE Transactions, 34, 467-477.
85. Yalaoui, F. and Chu, C. (2002) Parallel machine scheduling to minimize total tardiness. International Journal of Production Economics, 76, 265-279.
86. Yu, L., Shih, H.M., Pfund, M., Carlyle, W.M., and Fowler, J.W. (2002) Scheduling of unrelated parallel machines: An application to PWB manufacturing. IIE Transactions, 34, 921-931.