none

Due to the advancement and popularity of computers and networks, people start using them to improve their working environment. Distributed computing systems (DCSs) that combine computers and networks is one example with characteristics of high reliability and flexibility. In a DCS, tasks can be executed simultaneously on different computers; when a computer in the DCS breaks down, the task assigned to it can be transferred to another computer and task execution resumes. In practice, there are many applications of DCSs such as network database management systems, automatic teller machine (ATM) systems, power control systems, etc. Task allocation strategies are essential in the context of distributed computing systems. Previous studies have proposed various task allocation
strategies in a DCS from reliability or efficiency perspective. However, how to obtain a reliable and efficient task allocation strategy remains unanswered. This thesis therefore formulates the task allocation problem as a fuzzy goal programming that aims to maximize the degree of two fuzzy goals-system reliability and task completion
time-subject to the capacity constraints for processing nodes in a DCS and the desirable achievement degrees for fuzzy goals, and develops a heuristic based on reactive tabu search to solve the task allocation problem. The thesis will test the developed method on various simulated DCSs with heterogenous combination of component reliabilities and execution speeds.

Arikan, F. and Gungor, Z. An application of fuzzy goal programming to a multiobjec-
tive project network problem. Fuzzy Sets and Systems, 119(1), 49-58, 2001.

Battiti, R. and Tecchiolli, G. The reactive tabu search. ORSA Journal on Computing, 6(2), 126-140, 1994.

Bhattacharjee, S., Ramesh, R. and Zionts, S. A design framework for e-business infrastructure integration and resource management. IEEE Transactions on Systems Man and Cybernetics Part C-Application and Reviews, 31(3), 304-319, 2001.

Carlton, W. and Barnes, J. Solving the traveling-salesman problem with time windows
using tabu search. IIE Transactions, 28(8), 617-629, 1996.

Chen, L. and Tsai, F. Fuzzy programming with di®erent importance and priorities.
European Journal of Operational Research, 133(3), 548-556, 2001.

Chen, M., Chen, G. and Liu, P. An LC branch and bound algorithm for module assignment problem. Information Processing Letters, 32, 61-71, 1989.

Chiu, C., Yeh, Y. and Chen, R. Reduction of the total execution time to achieve the optimal k-node reliability of distributed computing systems using a novel heuristic algorithm. Computer Communications, 23, 84-91, 2000.

Chiu, C., Yeh, Y. and Chou, J. A fast algorithm for reliability-oriented task assignment in a distributed system. Computer Communications, 25(17), 1622-1630, 2002.

Chu, W., Holloway, L., Lan, M. and Efe, K. Task allocation in distributed data
processing. Computer communications, 41, 57-69, 1980.

Chu, W., Lan, M. and Hellerstein, J. Estimation of intermodule communiation (IMC)
and its applications in distributed processing systems. IEEE Transactions on
Computers, C-33, 691-699, 1984.

Csondes, T., Kotnyek, B. and Szabo, J. Application of heuristic methods for conformance test selection. European Journal of Operational Research, 142(1), 203-218, 2002.

Fudo, H., Toune, S., Genji, T., Fukuyama, Y. and Nakanishi, Y. An application of
reactive tabu search for service restoration in distribution systems and its comparison with the genetic algorithm and parallel simulated annealing. Electrical Engineering in Japan, 133(3), 71-82, 2000.

Glover, F. Tabu search, part II. ORSA Journal on Computing, 2, 4-32, 1989a.

Glover, F. Tabu search, part I. ORSA Journal on Computing, 1, 190-206, 1989b.

Hariri, S. and Raghavendra, C. SYREL: A symbolic reliability algorithm based on path
and cutset methods. IEEE Transactions on Reliability, 36, 1224-1232, 1987.

Holland, J. Genetic algorithm and the optimal allocation of trials. SIAM Journal on
Computing, 2(1), 88-105, 1973.

Hsieh, C. and Chen, Y. 2001. Reliability-oriented task allocation in cycle-free distributed computing systems using genetic algorithms. In Proc. IEEE Transaction on Reliability (pp. 1-17).

Lin, M. and Chen, D. 1992. Distributed program reliability analysis. In Proc. 3th Workshop on Distributed Computing Systems (pp. 395-401).

Lozano, S., Adenso-Diaz, B., Eguia, I. and Onieva, L. A one-step tabu search algorithm for manufacturing cell design. Journal of the Operational Research Society, 50,
509-516, 1999.

Nanry, W. and Barnes, J. Solving the pickup and delivery problem with time windows using reactive tabu search. Transportation Research Part B-Methodological,
34(2), 107-121, 2000.

Narasimhan, R. Goal programming in a fuzzy environment. Decision Sciences, 11(1),
325-336, 1980.

Pal, B. and Moitra, B. A goal programming procedure for solving problems with multiple fuzzy goals using dynamic programming. European Journal of Operational Research, 144(3), 480-491, 2003.

Parra, M., Terol, A. and Uria, M. A fuzzy goal programming approach to portfolio
selection. European Journal of Operational Research, 133(2), 287-297, 2001.

Raghavendra, C. and Hariri, S. Reliability optimization in the design of distributed
systems. IEEE Transactions on Reliability, SE-11, 1184-1193, 1985.

Rai, R., Kameshwaran, S. and Tiwari, M. Machine-tool selection and operation alloca-
tion in FMS: solving a fuzzy goal-programming model using a genetic algorithm.
International Journal of Production Research, 40(3), 641-665, 2002.

Shatz, S. and Wang, J. Models & algorithms for reliability-oriented task-allocation in
redundant distributed-computer systems. IEEE Transactions on Reliability, 38,
16-27, 1989.

Shen, C. and Tsai, W. A graph matching approach to optimal task assignment in
distributed computing systems using a minimax criterion. IEEE Transactions on
Computers, 34, 197-203, 1985.

Srinivasan, S. and Niraj, K. Safety and reliability driven task allocation in distributed
systems. IEEE Transactions on Parallel and Distributed Systems, 10(3), 238-251, 1999.

Stone, H. Multiprocessor scheduling with the aid of network °ow diagrams. IEEE Transactions on Software Engineering, 3, 85-93, 1977.

Tanenbaum, A. Distributed Operating Systems. Englewood Cli®s: N.J.:Prentice Hall, 1995.

Tiwari, R., Dharmar, S. and Rao, J. Fuzzy goal programming - an additive model.
Fuzzy Sets and Systems, 24, 27-34, 1987.

Tom, P. and Murthy, C. Algorithms for reliability-oriented module allocation in dis-
tributed computing systems. Journal of Systems and Software, 40, 125-138, 1998.

Tom, P. and Murthy, C. Optimal task allocation in distributed systems by graph
matching and state space search. Journal of Systems and Software, 46, 59-75, 1999.

Verma, A. and Tamhankar, M. Reliability-based optimal task-allocation in distributed-
database management systems. IEEE Transactions on Reliability, 46, 452-459,1997.

Wang, J. and Shatz, S. 1988a. Reliability-oriented task allocation in redundant distributed systems. In Proc. 12th International Conference on Computer Software and Applications (pp. 276-283).

Wang, J. and Shatz, S. 1988b Task allocation for optimized system reliability. In Proc. 7th Symposium on Reliable Distributed Systems (pp. 82-90).

Wood, R. Factoring algorithms for computing k-terminal network reliability. IEEE
Transactions on Reliability, 35, 269-278, 1986.

Zimmermann, H. Fuzzy programming and linear programming with several objective
functions. Fuzzy Sets and Systems, 1, 45-55, 1978.

Zimmermann, H. Fuzzy mathematical programming. Fuzzy Sets and Systems, 10(4), 291-298, 1983.