Please use this identifier to cite or link to this item:
A Gradient-Based Technique for Near-Optimal Waiting Time in Resource Allocation
|關鍵字:||Gradient;梯度;Linearly convergent;Optimization;Grid computing;Parallel computing;Mobile computing;Average waiting time;線性收斂;最佳化;網格計算;平行計算;行動計算;平均等待時間||出版社:||資訊科學與工程學系所||引用:|| 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.  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.  C. Blum and A. Roli, "Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison," ACM Computing Surveys, Vol. 35, No. 3, pp. 268-308, 2003.  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.  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.  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.  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.  F.S. Budnick, D. McLeavey, and R. Mojena, Principles of Operations Research for Management, 2 ed.: IRWIN, 1988.  R.L. Burden and J.D. Faires, Numerical Analysis: PWS-KENT, 1988.  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.  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.  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.  W.W. Chu, "Optimal File Allocation in a Multiple Computer System," IEEE Transactions on Computers, Vol. C-18, No. 10, pp. 885-889, 1969.  T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, Introduction to Algorithms: McGraw-Hill, 2001.  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.  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.  M. Dorigo and G.D. Caro, The ant colony optimization meta-heuristic, New ideas in optimization: McGraw-Hill, 1999  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.  F. Glover, "Future Paths for Integer Programming and Links to Artificial Intelligence," Computers and Operations Research, Vol. 13, pp. 533-549, 1986.  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.  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.  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.  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.  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.  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.  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.  H. Kameda, J. Li, C. Kim, and Y. Zhang, Optimal Load Balancing in Distributed Computer Systems: Springer, 1997.  H. Kellerer, U. Pferschy, and D. Pisinger, Knapsack Problems: Springer, 2004.  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.  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.  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.  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.  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.  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.  Z. Michalewicz and D.B. Fogel, How to Solve It: Modern Heuristics, 3 ed.: Springer, 2002.  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.  J.M. Ortega and W.C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables: SIAM, 2000.  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.  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.  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.  X. Qin, "Design and Analysis of a Load Balancing Straegy in Data Grids, "Future Generation Computer Systems, Vol. 23, pp. 132-137, 2007.  R.L. Rardin, Optimization in Operations Research: Prentice Hall, 1998.  A. Ravindran, D.T. Phillips, and J.J. Solberg, Operations Research Principles and Practice: Wiley, 1987.  P. Sanders, "Asynchronous Scheduling of Redundant Disk Arrays," IEEE Transactions on Computers, Vol. 52, pp. 1170-1184, 2003.  A. Silberschatz, H.F. Korth, and S. Sudarshan, Database System Concepts: McGraw Hill, 2002.  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.  H.A. Taha, Operations Research An Introduction, 6 ed.: Prentice Hall, 1997.  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.  C. Voudouris and E. Tsang, "Guided local search," European Journal of Operational Research, Vol. 113, No. 2, pp. 469-499, 1999.  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.  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.  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.  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.  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.  Globus Alliance, "Globus Toolkit, "http://www.globus.org/, 2009.||摘要:||
In 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.
|Appears in Collections:||資訊科學與工程學系所|
Show full item record
TAIR Related Article
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.