臺灣博碩士論文加值系統

本論文研究在任意m個平行處理器上排程n個可展延任務之問題，其中n個可展延任務被一些優先順序條件所連接。當處理器的數量mgeq 2時，在優先順序條件下排程可展延任務是一個強NP-困難（strongly NP-hard）的問題。換言之，除非NP=P，否則此問題無法在多項式時間內得到最佳解。因此，本問題必須尋找一個有效率的近似值演算法來代替原本求最佳解的演算法。

在優先順序條件下排程可展延任務中，需經由一個合理的分配方法來發現最小的最大完成時間（makespan）。基於Blayo et al.所提出的假設，本論文定義二個假設：（１）隨著處理器數量的增加，可展延任務的處理時間具有非遞減的特性。（２）隨著處理器數量的增加，可展延任務的工作量具有非遞增的特性。此外，我們假設工作函數為一個凸函數（convex）。本論文提出一個新的多項式時間內之近似值演算法，此演算法使用線性方程式（linear programming formulation）與進位方法（rounding procedure）得到2+sqrt{2}approx 3.4142的近似比率。當處理時間隨著處理器數量的增加而嚴格遞減時，本論文進一步地證明此演算法能夠產生2.9549的近似比率。此結果改進了先前的最佳近似比率100/63+100(sqrt{6469}+137)/5481approx 3.2920[31]。

This thesis studies the problem of scheduling a set of n malleable tasks on an arbitrary number m of parallel processors where a set of n malleable tasks linked by some precedence constraints. The problem of scheduling malleable tasks with arbitrary precedence constraints is strongly NP-hard for all processor counts m geq 2. In other words, that no polynomial time algorithm exists for scheduling malleable tasks with precedence constraints unless NP=P. Therefore, efficient approximation heuristics, instead of exact algorithms, are sought.

Scheduling malleable tasks under general precedence constraints involves finding a minimum makespan (maximum completion time) by a feasible allotment. Based on the monotonous penalty assumptions of Blayo et al, this thesis defines two assumptions concerning malleable tasks: the processing time of a malleable task is non-increasing in the number of processors, while the work of a malleable task is non-decreasing in the number of processors. Additionally, the work function is assumed herein to be convex in the processing time. The proposed algorithm reformulates the linear program of [30], and this algorithm and associated proofs are inspired by the ones of [30]. This thesis describes a novel polynomial-time approximation algorithm that is capable of achieving an approximation ratio of 2+sqrt{2} approx 3.4142. This thesis further demonstrates that the proposed algorithm can yield an approximation ratio of 2.9549 when the processing time is strictly decreasing in the number of the processors allocated to the task. This finding represents an improvement upon the previous best approximation ratio of 100/63+100(sqrt{6469}+137)/5481 approx 3.2920[31] achieved under the same assumptions.

Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi
List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Our Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1 Non-Malleable Tasks . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Malleable Tasks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3 Assumptions and Notation . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4 Approximation Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 13
5 Analysis of Approximation Algorithm . . . . . . . . . . . . . . . . . . . 20
5.1 Analysis of Approximation Algorithm for General Assumption . . . . 21
5.1.1 Approximation Ratio of the Proposed Algorithm for General
Assumption . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
5.2 Analysis of Approximation Algorithm for a Special Assumption . . . . 44
5.2.1 Approximation Ratio of the Proposed Algorithm for Special
Assumption . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
6 Results and Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
7 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

[1] A. Amoura, E. Bampis, C. Kenyon, and Y. Manoussakis, ``Scheduling independent multiprocessor tasks,' Algorithmica, Vol. 32, pp. 247--261, 2002.
[2] J. Augustine, S. Banerjee, and S. Irani, ``Strip packing with precedence constraints and strip packing with release times,' Theoretical Computer Science, Vol. 410, No. 38-40, pp. 3792 -- 3803, 2009.
[3] B. S. Baker, coffman, and R. L. Rivest, ``Orthogonal packings in two dimensions,' in Sixteenth Annual Allerton Conference on Communication, Control and Computing. Urbana, IL: Univ. Illinois, 1978, pp. 626--635.
[4] K. P. Belkhale and P. Banerjee, ``An approximate algorithm for the partitionable independent task scheduling problem,' in International Conference on Parallel Processing, 1990.
[5] S. Bischof and E. W. Mayr, ``On-line scheduling of parallel jobs with runtime restrictions,' Theoretical Computer Science, Vol. 268, No. 1, pp. 67 -- 90, 2001.
[6] E. Blayo, L. Debreu, G. Mouni´e, and D. Trystram, ``Dynamic load balancing for ocean circulation model with adaptive meshing,' in In Proceedings of the 5th European Conference on parallel computing (Euro-Par 1999), volume 1685 of LNCS. SpringerVerlag, 1999, pp. 303--312.
[7] J. Blazewicz, W. Cellary, R. Slowinski, and J. Weglarz, ``Scheduling under Resource Constraints--Deterministic Models,' Annals of Operations Research, Vol. 7, 1986.
[8] J. Blazewicz, K. Ecker, E. Pesch, G. Schmidt, and J. Weglarz, Handbook on Scheduling: From Theory to Applications. Springer Berlin / Heidelberg, 2007.
[9] D. E. Culler, R. M. Karp, D. Patterson, A. Sahay, E. E. Santos, K. E. Schauser, R. Subramonian, and T. von Eicken, ``Logp: a practical model of parallel computation,' Commun. ACM, Vol. 39, No. 11, pp. 78--85, 1996.
[10] T. Decker, T. L¨ucking, and B. Monien, ``A 5/4-approximation algorithm for scheduling identical malleable tasks,' Theor. Comput. Sci., Vol. 361, No. 2, pp. 226--240, 2006.
[11] M. Drozdowski, ``Scheduling multiprocessor tasks ¡x an overview,' European Journal of Operational Research, Vol. 94, No. 2, pp. 215 -- 230, 1996.
[12] M. Drozdowski, Scheduling for Parallel Processing, 1st ed. Springer Publishing Company, Incorporated, 2009.
[13] J. Du and J. Y.-T. Leung, ``Complexity of scheduling parallel task systems,' SIAM Journal on Discrete Mathematics, Vol. 2, No. 4, pp. 473--487, 1989.
[14] P.-F. Dutot, G. Mouni´e, and D. Trystram, ``Scheduling Parallel Tasks: Approximation Algorithms,' in Handbook of Scheduling: Algorithms, Models, and Performance Analysis, ser. chapter 26, J. T. Leung, Ed. CRC Press, 2004, pp. 26--26.
[15] A. Feldmann, M.-Y. Kao, J. Sgall, and S.-H. Teng, ``Optimal on-line scheduling of parallel jobs with dependencies,' Journal of Combinatorial Optimization, Vol. 1, pp. 393--411, 1998.
[16] A. Feldmann, M.-Y. Kao, J. Sgall, and S.-H. Teng, ``Optimal online scheduling of parallel jobs with dependencies,' in Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, ser. STOC '93. New York, NY, USA: ACM, 1993, pp. 642--651.
[17] A. Feldmann, J. Sgall, and S.-H. Teng, ``Dynamic scheduling on parallel machines,' Theoretical Computer Science, Vol. 130, No. 1, pp. 49 -- 72, 1994.
[18] M. Garey and D. S. Johnson, ``Complexity results for multiprocessor scheduling under resource constraints,' SIAM Journal of Computing, Vol. 4, No. 4, pp. 397--411, 1975.
[19] M. R. Garey and R. L. Graham, ``Bounds for multiprocessor scheduling with resource constraints,' SIAM Journal on Computing, Vol. 4, No. 2, pp. 187--200, 1975.
[20] R. L. Graham, ``Bounds for certain multiprocessing anomalies,' Bell System Technical Journal, Vol. 45, No. 9, pp. 1563--1581, 1966.
[21] R. Graham, E. Lawler, J. Lenstra, and A. Kan, ``Optimization and approximation in deterministic sequencing and scheduling: a survey,' in Discrete Optimization II, ser. Annals of Discrete Mathematics, E. J. P.L. Hammer and B. Korte, Eds. Elsevier, 1979, Vol. 5, pp. 287 -- 326.
[22] E. G¨unther, F. K¨onig, and N. Megow, ``Scheduling and packing malleable tasks with precedence constraints of bounded width,' in Approximation and Online Algorithms, ser. Lecture Notes in Computer Science, E. Bampis and K. Jansen, Eds. Springer Berlin / Heidelberg, 2010, Vol. 5893, pp. 170--181.
[23] J.-J. Hwang, Y.-C. Chow, F. D. Anger, and C.-Y. Lee, ``Scheduling precedence graphs in systems with interprocessor communication times,' SIAM Journal on Computing, Vol. 18, No. 2, pp. 244--257, 1989.
[24] K. Jansen, ``Scheduling malleable parallel tasks: An asymptotic fully polynomial-time approximation scheme,' Algorithmica, Vol. 39, No. 1, pp. 59--81, 2004.
[25] K. Jansen, ``A(3/2+ϵ) approximation algorithm for scheduling moldable and non-moldable parallel tasks,' in Proceedinbgs of the 24th ACM symposium on Parallelism in algorithms and architectures, ser. SPAA '12. New York, NY, USA: ACM, 2012, pp. 224--235.
[26] K. Jansen and L. Porkolab, ``Linear-time approximation schemes for scheduling malleable parallel tasks,' Algorithmica, Vol. 32, No. 3, pp. 507--520, 2002.
[27] K. Jansen and L. Porkolab, ``Computing optimal preemptive schedules for parallel tasks: linear programming approaches,' Mathematical Programming, Vol. 95, pp. 617--630, 2003.
[28] K. Jansen and R. Solis-Oba, ``New approximability results for 2-dimensional packing problems,' in Mathematical Foundations of Computer Science 2007, ser. Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2007, Vol. 4708, pp. 103--114.
[29] K. Jansen and R. Th¨ole, ``Approximation algorithms for scheduling parallel jobs,' SIAM J. Comput., Vol. 39, No. 8, pp. 3571--3615, 2010.
[30] K. Jansen and H. Zhang, ``An approximation algorithm for scheduling malleable tasks under general precedence constraints,' ACM Trans. Algorithms, Vol. 2, No. 3, pp. 416--434, 2006.
[31] K. Jansen and H. Zhang, ``Scheduling malleable tasks with precedence constraints,' Journal of Computer and System Sciences, Vol. 78, No. 1, pp. 245--259, 2012.
[32] B. Johannes, ``Scheduling parallel jobs to minimize the makespan,' Journal of Scheduling, Vol. 9, pp. 433--452, 2006.
[33] E. G. C. Jr., M. R. Garey, D. S. Johnson, and R. E. Tarjan, ``Performance bounds for level-oriented two-dimensional packing algorithms,' Siam Journal on Computing, Vol. 9, pp. 808--826, 1980.
[34] C. Kenyon and E. Remila, ``Approximate strip packing,' in Foundations of Computer Science, 1996. Proceedings., 37th Annual Symposium on, oct 1996, pp. 31--36.
[35] C. Kenyon and E. R´emila, ``A near-optimal solution to a two-dimensional cutting stock problem,' Math. Oper. Res., Vol. 25, No. 4, pp. 645--656, nov 2000.
[36] Y. Kopidakis and V. Zissimopoulos, ``An approximation scheme for scheduling independent jobs into subcubes of a hypercube of fixed dimension,' Theoretical Computer Science, Vol. 178, No. 1-2, pp. 265 -- 273, 1997.
[37] J. K. Lenstra and A. H. G. Rinnooy Kan, ``Complexity of scheduling under precedence constraints,' OPERATIONS RESEARCH, Vol. 26, No. 1, pp. 22--35, 1978.
[38] R. Lep´ere, G. Mouni´e, and D. Trystram, ``An approximation algorithm for scheduling trees of malleable tasks,' European Journal of Operational Research, Vol. 142, No. 2, pp. 242 -- 249, 2002.
[39] R. Lep´ere, D. Trystram, and G. J. Woeginger, ``Approximation algorithms for scheduling malleable tasks under precedence constraints,' International Journal of Foundations of Computer Science, Vol. 13, No. 4, pp. 613 -- 627, 2002.
[40] W. Ludwig and P. Tiwari, ``Scheduling malleable and nonmalleable parallel tasks,' in SODA '94: Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms. Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, 1994, pp. 167--176.
[41] W. Ludwig, ``Algorithms for scheduling malleable and non-malleable parallel tasks,' Ph.D. dissertation, University if Wisconsin-Madison, 1995.
[42] G. Mouni´e, C. Rapine, and D. Trystram, ``A 3/2 -approximation algorithm for scheduling independent monotonic malleable tasks,' SIAM Journal on Computing, Vol. 37, No. 2, pp. 401--412, 2007.
[43] G. Mouni´e, C. Rapine, and D. Trystram, ``Efficient approximation algorithms for scheduling malleable tasks,' in SPAA '99: Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures. New York, NY, USA: ACM, 1999, pp. 23--32.
[44] E. Naroska and U. Schwiegelshohn, ``On an on-line scheduling problem for parallel jobs,' Information Processing Letters, Vol. 81, No. 6, pp. 297 -- 304, 2002.
[45] K. Pruhs, J. Sgall, and E. Torng, ``Online scheduling,' in Handbook of Scheduling: Algorithms, Models, and Performance Analysis, J. Y.-T. Leung, Ed. Chapman and Hall/CRC, 2004, ch. 15, pp. 15-1--15-43.
[46] U. Schwarz, ``Tightness results for malleable task scheduling algorithms,' in Parallel Processing and Applied Mathematics, ser. Lecture Notes in Computer Science, R. Wyrzykowski, J. Dongarra, K. Karczewski, and J. Wasniewski, Eds. Springer Berlin Heidelberg, 2008, Vol. 4967, pp. 1059--1067.
[47] J. Sgall, ``On-line scheduling,' in Online Algorithms, ser. Lecture Notes in Computer Science, A. Fiat and G. Woeginger, Eds. Springer Berlin Heidelberg, 1998, Vol. 1442, pp. 196--231.
[48] M. Skutella, ``Approximation algorithms for the discrete time-cost tradeoff problem,' MATHEMATICS OF OPERATIONS RESEARCH, Vol. 23, No. 4, pp. 909--929, 1998.
[49] G. N. Srinivasa Prasanna and B. R. Musicus, ``Generalised multiprocessor scheduling using optimal control,' in SPAA '91: Proceedings of the third annual ACM symposium on Parallel algorithms and architectures. New York, NY, USA: ACM, 1991, pp. 216--228.
[50] A. Steinberg, ``A strip-packing algorithm with absolute performance bound 2,' SIAM J. Comput., Vol. 26, No. 2, pp. 401--409, Apr. 1997.
[51] J. Turek, J. L. Wolf, and P. S. Yu, ``Approximate algorithms scheduling parallelizable tasks,' in SPAA '92: Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures. New York, NY, USA: ACM, 1992, pp. 323--332.
[52] D. Ye and G. Zhang, ``On-line scheduling mesh jobs with dependencies,' Theoretical Computer Science, Vol. 372, No. 1, pp. 94 -- 102, 2007.
[53] H. Zhang, ``Approximation algorithms for min-max resource sharing and malleable tasks scheduling,' Ph.D dissertation University of Kiel, Kiel Germany, 2004.