Please use this identifier to cite or link to this item:
DC FieldValueLanguage
dc.contributor.authorWang, Jen-Yaen_US
dc.identifier.citation[1] G. Aggarwal, T. Feder, R. Motwani, R. Panigrahy, and A. Zhu, "Algorithms for the Database Layout Problem," in Proceedings of International Conference on Database Theory, 2005, pp. 619-625. [2] E. Ardizzoni, A.A. Bertossi, M.C. Pinotti, S. Ramaprasad, R. Rizzi, and M.V.S. Shashanka, "Optimal Skewed Data Allocation on Multiple Channels with Flat Broadcast per Channel," IEEE Transactions on Computers, Vol. 54, No. 5, pp. 558-572, 2005. [3] C. Blum and A. Roli, "Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison," ACM Computing Surveys, Vol. 35, No. 3, pp. 268-308, 2003. [4] B. Boeckmann, A. Bairoch, R. Apweiler, M.-C. Blatter, A. Estreicher, E. Gasteiger, K. M. Martin, Michoud, C. O'Donovan, I. Phan, S. Pilbout, and M. Schneider, "The SWISS-PROT Protein Knowledgebase and its Supplement TrEMBL in 2003," Nucleic Acids Research, Vol. 31, pp. 365-370, 2003. [5] P.M. Broadwell, "Response Time as a Performability Metric for Online Services," Technical Report, UCB CSD-04-1324, Electrical Engineering and Computer Science Department, University of California at Berkeley, USA, 2004. [6] J. Broberg, P. Zecephongsekul, and Z. Tari, "Approximating Bounded General Service Distributions," in Proceedings of the 12th IEEE Symposium on Computers and Communications (ISCC), 2007, pp. 817-823. [7] P. Bucher and A. Bairoch, "A Generalized Profile Syntax for Biomolecular Sequences Motifs and its Function in Automatic Sequence Interpretation," in Proceedings 2nd International Conference on Intelligent Systems for Molecular Biology, 1994, pp. 53-61. [8] F.S. Budnick, D. McLeavey, and R. Mojena, Principles of Operations Research for Management, 2 ed.: IRWIN, 1988. [9] R.L. Burden and J.D. Faires, Numerical Analysis: PWS-KENT, 1988. [10] T. Cakar, R. Koker, and H.I. Demir, "Parallel Robot Scheduling to Minimize Mean Tardiness with Precedence Constraints Using a Genetic Algorithm," Advances in Engineering Software, Vol. 39, pp. 47-54, 2008. [11] J. Carretero, F. Xhafa, and A. Abraham, "Genetic Algorithm Based Schedulers for Grid Computing Systems," International Journal of Innovative Computing, Information and Control Vol. 3, No. 6, pp. 1-19, 2007. [12] V. Cerny, "A thermodynamical approach to the travelling salesman problem: An efficient simulation algorithm," Journal of Optimization Theory and Applications, Vol. 40, pp. 41-51, 1985. [13] W.W. Chu, "Optimal File Allocation in a Multiple Computer System," IEEE Transactions on Computers, Vol. C-18, No. 10, pp. 885-889, 1969. [14] T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, Introduction to Algorithms: McGraw-Hill, 2001. [15] Y.S. Dai, G. Levitin, and X. Wang, "Optimal Task Partition and Distribution in Grid Service System with Common Cause Failures," Future Generation Computer Systems, Vol. 23, No. 2, pp. 209-218, 2007. [16] F. Desprez and A. Vernois, "Simultaneous Scheduling of Replication and Computation for Data-Intensive Applications on the Grid," Journal of Grid Computing, Vol. 4, No. 1, pp. 19-31, 2006. [17] M. Dorigo and G.D. Caro, The ant colony optimization meta-heuristic, New ideas in optimization: McGraw-Hill, 1999 [18] J.W. Fowler, P. Wirojanagud, and E.S. Gel, "Heuristics for Workforce Planning with Worker Differences," European Journal of Operational Research, Vol. 190, pp. 724-740, 2008. [19] F. Glover, "Future Paths for Integer Programming and Links to Artificial Intelligence," Computers and Operations Research, Vol. 13, pp. 533-549, 1986. [20] M. Harchol-Balter, "Job Placement with Unknown Duration and No Preemption Performance Evaluation," ACM SIGMETRICS Performance Evaluation Review, Vol. 28, No. 4, pp. 3-5, 2001. [21] M. Harchol-Balter and A.B. Downey, "Exploiting Process Lifetime Distributions for Dynamic Load Balancing," ACM Transactions Computer Systems, Vol. 15, pp. 253-285, 1997. [22] J.L. Huang and M.S. Chen, "Dependent Data Broadcasting for Unordered Queries in a Multiple Channel Mobile Environment," IEEE Transactions on Knowledge and Data Engineering, Vol. 16, No. 9, pp. 1143-1156, 2004. [23] Y.F. Huang and J.M. Huang, "Disk Scheduling on Multimedia Storage Servers," IEEE Transaction on Computers, Vol. 53, No. 1, pp. 77-82, 2004. [24] R. Ito and K. Suyama, "A Heuristic Approach to SP2 Term Allocation for Fir Filter Based on Least Mean Square Criteria," International Journal of Innovative Computing, Information and Control Vol. 1, No. 1, pp. 65-71, 2005. [25] S.A. Jarvis, L. He, D.P. Spooner, and G.R. Nudd, "The Impact of Predictive Inaccuracies on Execution Scheduling," Performance Evaluation, Vol. 60, pp. 127-139, 2005. [26] K.F. Jea, J.Y. Wang, and S.Y. Chen, "A Linearly Convergent Method for Broadcast Data Allocation," Computers and Mathematics with Applications, Vol. 56, No. 2, pp. 324-338, 2008. [27] H. Kameda, J. Li, C. Kim, and Y. Zhang, Optimal Load Balancing in Distributed Computer Systems: Springer, 1997. [28] H. Kellerer, U. Pferschy, and D. Pisinger, Knapsack Problems: Springer, 2004. [29] S. Lee and H. Bahn, "Data Allocation in MEMS-based Mobile Storage Devices," IEEE Transactions on Consumer Electronics, Vol. 52, No. 2, pp. 472-476, 2006. [30] M. Lei, S.V. Vrbsky, and X. Hong, "An On-line Replication Strategy to Increase Availability in Data Grids," Future Generation Computer Systems, Vol. 24, No. 2, 2008. [31] C.J. Liao, C.W. Chao, and C.H. Lin, "Minimizing the Sum of Job Completion Times on Capacitated Two-parallel Machines," European Journal of Operational Research, In Press, Corrected Proof, 2008. [32] H.C. Lin and C.S. Raghavendra, "A Dynamic Load-Balancing Policy with a Central Job Dispatcher (LBC)," IEEE Transactions on Software Engineering, Vol. 18, No. 2, pp. 148-158, 1992. [33] L. Lu, L. Zhang, and J. Yuan, "The Unbounded Parallel Batch Machine Scheduling with Release Dates and Rejection to Minimize Makespan," Theoretical Computer Science, Vol. 396, pp. 283-289, 2008. [34] D. Martin, A.v. Moorsel, and G. Morgan, "Efficient Resource Management for Game Server Hosting," in Proceedings of the 2008 11th IEEE Symposium on Object Oriented Real-Time Distributed Computing (ISORC), 2008, pp. 593-596. [35] Z. Michalewicz and D.B. Fogel, How to Solve It: Modern Heuristics, 3 ed.: Springer, 2002. [36] D. Nurmi, J. Brevik, and R. Wolski, "Modeling Machine Availability in Enterprise and Wide-Area Distributed Computing Environments," Lecture Notes in Computer Science, Vol. 3648, pp. 432-441, 2005. [37] J.M. Ortega and W.C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables: SIAM, 2000. [38] W.C. Peng and M.S. Chen, "Efficient Channel Allocation Tree Generation for Data Broadcasting in a Mobile Computing Environment," Wireless Networks, Vol. 9, No. 2, pp. 117-129, 2003. [39] W.C. Peng, J.L. Huang, and M.S. Chen, "Dynamic Leveling: Adaptive Data Broadcasting in a Mobile Computing Environment," Mobile Networks and Applications, Vol. 8, No. 4, pp. 355-364, 2003. [40] L. Qi, H. Jin, I. Foster, and J. Gawor, "Provisioning for Dynamic Instantiation of Community Services," IEEE Internet Computing, Vol. 12, No. 2, pp. 29-36, 2008. [41] X. Qin, "Design and Analysis of a Load Balancing Straegy in Data Grids, "Future Generation Computer Systems, Vol. 23, pp. 132-137, 2007. [42] R.L. Rardin, Optimization in Operations Research: Prentice Hall, 1998. [43] A. Ravindran, D.T. Phillips, and J.J. Solberg, Operations Research Principles and Practice: Wiley, 1987. [44] P. Sanders, "Asynchronous Scheduling of Redundant Disk Arrays," IEEE Transactions on Computers, Vol. 52, pp. 1170-1184, 2003. [45] A. Silberschatz, H.F. Korth, and S. Sudarshan, Database System Concepts: McGraw Hill, 2002. [46] R. Subrata, A.Y. Zomaya, and B. Landfeldt, "Game-Theoretic Approach for Load Balancing in Computational Grids," IEEE Transactions on Parallel and Distributed Systems, Vol. 19, No. 1, pp. 66-76, 2008. [47] H.A. Taha, Operations Research An Introduction, 6 ed.: Prentice Hall, 1997. [48] P. Tsirimpas, A. Tatarakis, I. Minis, and E.G. Kyriakidis, "Single Vehicle Routing with a Predefined Customer Sequence and Multiple Depot Returns," European Journal of Operational Research, Vol. 187, No. 2, pp. 483-495, 2008. [49] C. Voudouris and E. Tsang, "Guided local search," European Journal of Operational Research, Vol. 113, No. 2, pp. 469-499, 1999. [50] J.Y. Wang and K.F. Jea, "A Near-Optimal Database Allocation for Reducing the Average Waiting Time in the Grid Computing Environment," Information Sciences, Vol. 179, No. 21, pp. 3772-3790, 2009. [51] J. Wingstrom and H. Casanova, "Probabilistic Allocation of Tasks on Desktop Grids," in Proceedings of the IEEE International Symposium on Parallel and Distributed Processing (IPDPS), 2008, pp. 1-8. [52] C. Wu, L. Yeh, H. Huang, L. Arminski, J. Castro-Alvear, Y. Chen, Z. Hu, P. Kourtesis, R. Ledley, and B. Suzek, "The Protein Information Resource," Nucleic Acids Research, Vol. 31, pp. 345-347, 2003. [53] W.G. Yee, S.B. Navathe, E. Omiecinski, and C. Jermaine, "Efficient Data Allocation over Multiple Channels at Broadcast Servers," IEEE Transactions on Computers, Vol. 51, No. 10, pp. 1231-1236, 2002. [54] B. Zheng, X. Wu, X. Jin, and D.L. Lee, "Broadcast Scheduling: TOSA: A Near-optimal Scheduling Algorithm for Multi-channel Data Broadcast," in Proceedings of the 6th International Conference on Mobile Data Management, 2005, pp. 29-37. [55] Globus Alliance, "Globus Toolkit, ", 2009.en_US
dc.description.abstractIn this dissertation, we propose a gradient-based technique that properly partitions and allocates resources in order to minimize the average waiting time for users in several computing environments. It is motivated by that there are many large-scale scientific projects (e.g., protein structure matching) and commercial applications (e.g., online game) and their waiting time needs to be lowered down for sustaining customer satisfaction. First, such a partition/allocation problem is mapped from the integer space Z^n to the Euclidean space R^n. Then, the optimal solution to the mapped problem in R^n is discovered by the proposed technique which optimally divides the resources and distributes them to multiple sites/nodes/locations. Finally, a near-optimal solution to the original problem is obtained by mapping the optimal solution to the mapped problem from R^n back to Z^n. The theoretical analyses show that the proposed technique converges linearly and generates a near-optimal average waiting time. We also present experimental results that confirm the convergence speed and solution quality of the proposed technique. Using the proposed technique, a system designer spends only a little execution time for deploying his/her resources and provides users with a near-optimal average waiting time. Importantly, the proposed technique can be extended to other similar optimization problems (e.g., vehicle routing problem) and can promisingly achieve the same near-optimal results.en_US
dc.description.tableofcontentsChapter 1 Introduction 1 1.1 Background 1 1.1.1 Average Waiting Time 3 1.1.2 Mobile Computing Environment 4 1.1.3 Grid/Parallel Computing Environment 5 1.2 Problem Outline 6 1.3 Contributions 7 1.4 Organization of Dissertation 8 Chapter 2 Related Work 9 2.1 Global Search vs. Local Search 9 2.2 Random Search vs. Deterministic Search 11 2.3 Memory Usage vs. Memoryless 13 2.4 Space Unchanged vs. Space Transformed 14 Chapter 3 Problem Definition 17 3.1 Problem Perspectives 17 3.1.1 Access Probability 17 3.1.2 Processing Complexity and Processing Capability 18 3.1.3 Processing Complexity and Access Probability 19 3.2 Problem Definition 20 3.2.1 Data Allocation Problem (DAP) 21 3.2.2 DataBase Allocation Problem (DBAP) 22 3.2.3 Service Partition Problem (SPP) 25 3.3 Simple Observations 26 Chapter 4 Proposed Heuristic 29 Chapter 5 DAP Problem 32 5.1 Mapping DAP from Z^n to R^n 32 5.2 Optimal Solution x* to DAP'' in R^n 36 5.3 Near-Optimal Solution v^+ to DAP in Z^n 41 5.4 Algorithm ADAP 45 Chapter 6 DBAP and SPP Problems 48 6.1 DBAP 49 6.1.1 Transforming DBAP in Z^n into DBAP'' in R^n 49 6.1.2 Optimal Solution x* to DBAP'' in R^n 51 6.1.3 Near-Optimal Solution v^+ to DBAP in Z^n 59 6.1.4 Algorithm ADBAP 59 6.2 SPP 60 6.2.1 Transforming SPP in Z^n into SPP'' in R^n 60 6.2.2 Optimal Solution x* to SPP'' in R^n 62 6.2.3 Near-Optimal Solution v^+ to SPP in Z^n 66 6.2.4 Compensation for Overloaded Machines 67 6.2.5 Algorithm ASPP 70 Chapter 7 Experimental Results 71 7.1 Experimental Results of Algorithm ADAP 71 7.1.1 Parameter Setting 71 7.1.2 Performance Evaluation 72 7.1.3 Comparison with VFK 76 7.2 Experimental Results of Algorithm ADBAP 79 7.2.1 Parameter Setting 79 7.2.2 Uniform Distribution 81 7.2.3 Bounded Pareto Distribution 83 7.2.4 Comparison with Optimal Results 87 7.2.5 Real Test Case 88 7.3 Experimental Results of Algorithm ASPP 90 7.3.1 Parameter Setting 90 7.3.2 Performance Evaluation 91 Chapter 8 Conclusion and Future Work 97 8.1 Conclusion 97 8.2 Future Work 99 References 101en_US
dc.subjectLinearly convergenten_US
dc.subjectGrid computingen_US
dc.subjectParallel computingen_US
dc.subjectMobile computingen_US
dc.subjectAverage waiting timeen_US
dc.titleA Gradient-Based Technique for Near-Optimal Waiting Time in Resource Allocationen_US
dc.typeThesis and Dissertationzh_TW
item.openairetypeThesis and Dissertation-
item.fulltextno fulltext-
Appears in Collections:資訊科學與工程學系所
Show simple item record

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.