臺灣博碩士論文加值系統

報表系統對於企業的日常營運而言，是不可或缺的。人們藉由報表與相關資訊，了解公司的營運狀況，進而協助其決策與執行。報表的產生過程通常需要進行大量的資料處理，整個執行過程相當冗長耗時。由於大部分的報表所需的參考資料具有相依性，所以報表產生必須考量相關資料的因果順序，才能確保資料的一致性。
本研究之目的在解決企業報表產生問題。我們發展了一套具智慧型代理人、分散式產生報表的系統架構，以有效利用分散在辦公室中的閒置個人電腦資源，執行並產生報表。每份報表係由個人電腦中的報表產生代理人(Reports Generating Agent, RGA)所產生，而報表協同代理人(Reports Coordinating Agent, RCA)則負責分配各報表至其所屬的報表產生代理人，並提出報表產生排程。報表排程的目標在協調報表間的產出順序，使整體報表產出時程達到最小。
此分散式報表產生問題的計算複雜度屬於非多項式困難的(NP-hard)問題。實務上，欲於限定時間內解得其最佳解是不可能的。因此，我們提出一個啟發式法則來求解決此分散式報表產生問題。此方法應用貪婪演算法的概念，將預估執行時間最長的可執行報表分派到處理速度最快的電腦上執行，一直到所有的報表產出為止。
我們應用五部電腦實作一分散式報表產生實驗平台，並設計多項實驗以驗證所提出的方法之可行性。為了探討所提出的啟發式報表排程方法之特性，我們應用窮舉法找出部份問題的最佳解，並比較兩者所需的計算時間及其效能表現。實驗結果顯示此分散式報表產生架構是可行且有效的，所提出的報表排程演算法能快速地解得接近最佳解的報表產生排程。

Reporting systems are indispensable to enterprise’s daily operations. People rely on reports to understand the business status quo as well as to make their decisions. The process of generating reports is usually data-intensive and thus tedious. This thesis deals with reports generating problems in an enterprise. As there are precedence relationships among the input and output data of reports, generating reports must follow the order of reports. We develop an agent-based, distributed reports generating framework that can effectively utilize enterprise’s computing power, especially for the lower-utilized personal computers (PCs) on clerks’ desktops. In the framework, each report generating job is done by a distributed report generating agent (RGA). The collaboration and coordination of reports generating jobs are executed by a report coordinating agent (RCA) which is responsible to schedule report generating jobs to distributed RGAs.
We adopt a heuristic approach to solve the distributed reports scheduling problem, which is NP-hard in computational complexity. Our report scheduling method schedules report generating jobs in a greedy way such that the overall report generating time is minimized.
We implement a distributed reports generating test environment with five personal computers. Some experiments are designed and conducted to validate our idea on the agent-based, distributed report generating framework. Numerical results indicate that our approach is feasible and effective. We conduct experiments to explore the computation times and the reports generating makespan of the proposed reports scheduling method, as compared to the optimal solutions obtained from exhaustive search. We find that our reports generating scheduling algorithm performs well in the scenarios whose capabilities of computers are almost equal to each other.

論文摘要 iii
Abstract v
List of Tables viii
List of Figures ix
CHAPTER 1 INTRODUCTION 1
1.1 Motivation 1
1.2 Literature Survey 2
1.3 Research Objective 8
1.4 Thesis Scope 8
1.5 Thesis Organization 9
CHAPTER 2 REPORTS GENERATING PROBLEM DESCRIPTION 10
CHAPTER 3 AGENT-BASED, DISTRIBUTED REPORTS GENERATING SYSTEM Framework 15
CHAPTER 4 18
DISTRIBUTED REPORTS SCHEDULING PROBLEMS SOLUTION METHODOLOGY 18
CHAPTER 5 NUMERICAL EXPERIMENTS 25
5.1 Feasibility Assessment 26
5.2 Experiment Design 30
5.3 Numerical Results 38
CHAPTER 6 System Implementation 59
CHAPTER 7 CONCLUSIONS AND FUTURE RESEARCH 64
7.1 Conclusions 64
7.2 Future Research 66
Bibliography 69
Appendix 72

[AuB90] N. Audsley and A. Burns, “Real-time System Scheduling,” Technical Report YOR134, 1990.
[Bru98]P. Brucker, Scheduling Algorithms, Second Edition, Springer-Verlag, New York, 1998.
[CaK88]T. L. Casavant and J. G. Kuhl, “A Taxonomy of Scheduling in General-Purpose Distributed Computing Systems,” IEEE Transactions on Software Engineering, Vol. 14, No. 2, pp. 141-154, February 1988.
[ChS90]T. Cheng and C. Sin, “A State-of-the-Art Review of Parallel-Machine Scheduling Research,” European Journal of Operational Research, Vol. 47, No. 3, pp. 271-292, January 1990.
[Cha96] S. J. Chapin, “Distributed and Multiprocessor Scheduling,” ACM Computing Surveys, Vol. 28, No. 1, pp. 233-235, March 1996.
[CDK01]G. Coulouris, J. Dollimore, and T. Kindberg, Distributed Systems Concepts and Design, Third Edition, Addison-Wesley, U.S.A., 2001.
[CLR02] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithm, Second Edition, McGraw Hill, U.S.A., 2002.
[EGG00] S. C. Esquivel, C. R. Gatica, and R. H. Gallard, “Evolutionary Approaches with Multirecombination for the Parallel Machine Scheduling Problem,” IEEE International Conference of the Chilean Computer Science Society , Santiago, pp. 1-6, November 2000.
[Gra69] R. L. Graham, “Bounds on Multiprocessing Time Anomalies,” SIAM Journal on Applied Mathematics, Vol. 17, No. 2, pp. 416-429, March 1969.
[Gra81] S. C. Graves, “A Review of Production Scheduling,” Operations Research, Vol. 29, No. 4, pp. 646-675, July-August 1981.
[HaS89] L. A. Hall and D. B. Shmoys, “Approximation Schemes for Constrained Scheduling Problems,” Foundations of Computer Science , Research Triangle Park, NC, United States of America, pp. 134-139, October 1989.
[HLM90] D. J. Hoitomt, P. B. Luh, E. Max, and K. R. Pattipati, “Scheduling Jobs with Simple Precedence Constraints on Parallel Machines,” IEEE Control Systems Magazine, pp. 34-40, February 1990.
[HoS76] E. Horowitz and S. Sahni, “Exact and Approximate Algorithms for Scheduling Nonidentical Processors,” Journal of the Association for Computing Machinery, Vol. 23, No. 2, pp. 317-327, April 1976.
[JoS97] J. Jonsson and K. G. Shin, “A Parametrized Branch-and-Bound Strategy for Scheduling Precedence-Constrained Tasks on A Multiprocessor System,” In proceedings of International Conference on Parallel Processing , Bloomington, pp. 158-165, August 1997.
[Jon99] J. Jonsson, “Effective Complexity Reduction for Optimal Scheduling of Distributed Real-Time Applications,” In Proceedings of the IEEE International Conference on Distributed Computing Systems, Austin, Texas, pp. 360–369, May – June 1999.
[LHM90] P. B. Luh, D. J. Hoitomt, E. Max, and K. R. Pattipati, “Schedule Generation and Reconfiguration for Parallel Machines,” IEEE Transactions on Robotics and Automation , Vol. 6, No. 6, pp. 687-696, December 1990.
[LTC05] R. Lee, S. Tseng, R. Chang, and Y. Tsai, Introduction to the Design and Analysis of Algorithms , McGraw Hill, Singapore, 2005.
[Mul94]S. Mullender, Distributed Systems, Second Edition, Addison-Wesley, United States of America, 1994.
[Nut92]G. J. Nutt, Centralized and Distributed Operating Systems, Prentice-Hall International (UK) Editions, London, 1992.
[PaI77] S. S. Panwalkar and W. Iskander, “A Survey of Scheduling Rules,” Operation Research, Vol. 25, No. 1, pp. 45-61, January-February 1977.
[Pin83] M. Pinedo, “Stochastic Scheduling with Release Dates and Due Dates,” Operations Research, Vol. 31, No. 3, pp. 559-572, January1983.
[PiW85] M. Pinedo and G. Weiss, “Scheduling Jobs with Exponentially Distributed Processing Times and Intree Precedence Constraints on two Parallel Machines,” Operations Research, Vol. 33, No. 6, pp. 1381-1388, 1985.
[RaS94] K. Ramamritham and J. S. Stankovic, “Scheduling Algorithms and Operating Systems Support for Real-Time Systems,” Proceedings of the IEEE, Vol. 82, No. 1, pp. 55-67, January 1994.
[Spr94]A. Sprecher, Resource-Constrained Project Scheduling, Springer-Verlag, Germany, 1994.
[WDY93] J. L. Wolf, D. M. Dias, and P. S. Yu, “A Parallel Sort Merge Join Algorithm for Managing Data Skew,” IEEE transactions on parallel and distributed systems, Vol. 4, No. 1, pp. 70-86, January 1993.