Optimizing task schedules using an artificial immune system approach

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Optimizing task schedules using an artificial immune system approach

Full text

Pdf (158 KB)

Source

Genetic And Evolutionary Computation Conference archive
Proceedings of the 10th annual conference on Genetic and evolutionary computation table of contents

Atlanta, GA, USA

SESSION: Ant colony optimization, swarm intelligence, and artificial immune systems papers table of contents

Pages 151-158

Year of Publication: 2008

ISBN:978-1-60558-130-9

Author

Han Yu

Physical and Digital Realization Research Center, Morotola Labs, Schaumburg, IL, USA

Sponsors

ACM: Association for Computing Machinery
SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 86, Citation Count: 0

Additional Information:

abstract references index terms

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1389095.1389116 What is a DOI?

ABSTRACT

Multiprocessor task scheduling is a widely studied optimization problem in the field of parallel computing. Many heuristic-based approaches have been applied to finding schedules that minimize the execution time of computing tasks on parallel processors. In this paper, we design an algorithm based on Artificial Immune Systems (AIS) to scheduling for heterogeneous computing environments. This approach distinguishes itself from many existing approaches in two aspects. First, it restricts the use of AIS to find optimal task-processor mapping, while taking advantage of heuristics used by deterministic scheduling approaches for task sequence assignment. Second, the calculation of the affinity takes into account both the solution quality and the distribution of population in the solution space. Empirical studies on benchmark task graphs show that this algorithm significantly outperforms HEFT, a deterministic algorithm. Further experiments also indicate that the algorithm is able to maintain high quality search even though a wide range of parameter settings are used.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Imtiaz Ahmad , Muhammad K. Dhodhi, Multiprocessor scheduling in a genetic paradigm, Parallel Computing, v.22 n.3, p.395-406, March 1996 [doi>10.1016/0167-8191(95)00068-2]
	2	Ishfaq Ahmad , Yu-Kwong Kwok, On Exploiting Task Duplication in Parallel Program Scheduling, IEEE Transactions on Parallel and Distributed Systems, v.9 n.9, p.872-892, September 1998 [doi>10.1109/71.722221]
	3	C. Boeres, E. Rios, and L. S. Ochi. Hybrid evolutionary static scheduling for heterogeneous systems. In Proceedings of the IEEE Congress on Evolutionary Computation, pages 1929--1935, 2005.
	4	S. W. Bollinger and S. F. Midkiff. Processor and link assignment in multicomputers using simulated annealing. In Proceedings of the International Conference on Parallel Processing, pages 1--7, 1988.
	5	A. Costa, P. Vargas, F. V. Zuben, and P. Franca. Makespan minimisation on parallel processors: An immune based approach. In Proceedings of the Congress on Evolutionary Computation, pages 920--926, 2002.
	6	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	7	E. Hart and P. Ross. An immune system approach to scheduling in changing environments. In Proceedings of Genetic and Evolutionary Computation Conference, pages 1559--1565, 1999.
	8	E. S. H. Hou , N. Ansari , H. Ren, A Genetic Algorithm for Multiprocessor Scheduling, IEEE Transactions on Parallel and Distributed Systems, v.5 n.2, p.113-120, February 1994 [doi>10.1109/71.265940]
	9	K. Hwang and J. Xu. Mapping partitioned program modules onto multicomputer nodes using simulated annealing. In Proceedings of the International Conference on Parallel Processing, pages 292--293, 1990.
	10	S. J. Kim and J. C. Browne. A general approach to mapping of parallel computation upon multiprocessor architectures. In International Conference on Parallel Processing, volume 2, pages 1--8, 1988.
	11	B. Kruatrachue and T. G. Lewis. Duplication Scheduling Heuristic, a new precedence task scheduler for parallel systems. Technical Report 87-60-3, Oregon State University, 1987.
	12	Yu-Kwong Kwok , Ishfaq Ahmad, Dynamic Critical-Path Scheduling: An Effective Technique for Allocating Task Graphs to Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.7 n.5, p.506-521, May 1996 [doi>10.1109/71.503776]
	13	Yu-Kwong Kwok , Ishfaq Ahmad, Efficient scheduling of arbitrary task graphs to multiprocessors using a parallel genetic algorithm, Journal of Parallel and Distributed Computing, v.47 n.1, p.58-77, Nov. 25, 1997 [doi>10.1006/jpdc.1997.1395]
	14	M. Mori, M. Tsukiyama, and T. Fukuda. Adapative scheduling system inspired by the immune system. In Proceedings of the IEEE Conference on Systems, Man and Cybernetics, pages 3833--3837, 1998.
	15	A. K. Nanda, D. DeGroot, and D. Stenger. Scheduling directed task graphs on multiprocessors using simulated annealing algorithms. In Proceedings of the 12th International Conference on Distributed Computing Systems, 1992.
	16	S. C. S. Porto and C. C. Ribeiro. A tabu search approach to task scheduling on heterogeneous processors under precedence constraints. International Journal of High-Speed Computing, 7(2), 1995.
	17	Haluk Topcuouglu , Salim Hariri , Min-you Wu, Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing, IEEE Transactions on Parallel and Distributed Systems, v.13 n.3, p.260-274, March 2002 [doi>10.1109/71.993206]
	18	T. Tsuchiya, T. Osada, and T. Kikuno. Genetic-based multiprocessor scheduling using task duplication. Microprocessors and Microsystems, 22:197--207, 1998.
	19	Lee Wang , Howard Jay Siegel , Vwani R. Roychowdhury , Anthony A. Maciejewski, Task matching and scheduling in heterogeneous computing environments using a genetic-algorithm-based approach, Journal of Parallel and Distributed Computing, v.47 n.1, p.8-22, Nov. 25, 1997 [doi>10.1006/jpdc.1997.1392]
	20	G. Wojtyla, K. Rzadca, and F. Seredynski. Artificial immune systems applied to multiprocessor scheduling. In Proceedings of the 6th International Conference on Parallel Processing and Applied Mathematics, pages 904--911, 2005.
	21	Annie S. Wu , Han Yu , Shiyuan Jin , Kuo-Chi Lin , Guy Schiavone, An Incremental Genetic Algorithm Approach to Multiprocessor Scheduling, IEEE Transactions on Parallel and Distributed Systems, v.15 n.9, p.824-834, September 2004 [doi>10.1109/TPDS.2004.38]
	22	M. Y. Wu , D. D. Gajski, Hypertool: A Programming Aid for Message-Passing Systems, IEEE Transactions on Parallel and Distributed Systems, v.1 n.3, p.330-343, July 1990 [doi>10.1109/71.80160]
	23	T. Yang , A. Gerasoulis, DSC: Scheduling Parallel Tasks on an Unbounded Number of Processors, IEEE Transactions on Parallel and Distributed Systems, v.5 n.9, p.951-967, September 1994 [doi>10.1109/71.308533]