Project scheduling heuristics-based standard PSO for task-resource assignment in heterogeneous grid. (English) Zbl 1214.90051

Chen, Ruey-Maw; Wang, Chuin-Mu

Abstr. Appl. Anal. 2011, Article ID 589862, 20 p. (2011).

Summary: The task scheduling problem has been widely studied for assigning resources to tasks in heterogeneous grid environment. Effective task scheduling is an important issue for the performance of grid computing. Meanwhile, the task scheduling problem is an NP-complete problem. Hence, this investigation introduces a named “standard” particle swarm optimization (PSO) metaheuristic approach to efficiently solve the task scheduling problems in grid. Meanwhile, two promising heuristics based on multimode project scheduling are proposed to help in solving interesting scheduling problems. They are the best performance resource heuristic and the latest finish time heuristic. These two heuristics applied to the PSO scheme are for speeding up the search of the particle and improving the capability of finding a sound schedule. Moreover, both global communication topology and local ring communication topology are also investigated for efficient study of proposed scheme. Simulation results demonstrate that the proposed approach in this investigation can successfully solve the task-resource assignment problems in grid computing and similar scheduling problems.

MSC:

90B35	Deterministic scheduling theory in operations research
90C59	Approximation methods and heuristics in mathematical programming
68T20	Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

Software:

PSPLIB

References:

[1]	I. Foster, C. Kesselman, and S. Tuecke, “The anatomy of the grid: enabling scalable virtual organizations,” International Journal of High Performance Computing Applications, vol. 15, no. 3, pp. 200-222, 2001.
[2]	T. Chen, B. Zhang, X. Hao, and Y. Dai, “Task scheduling in grid based on particle swarm optimization,” in Proceedings of the 5th International Symposium on Parallel and Distributed Computing (ISPDC ’06), pp. 238-245, July 2006.
[3]	A. Salman, I. Ahmad, and S. Al-Madani, “Particle swarm optimization for task assignment problem,” Microprocessors and Microsystems, vol. 26, no. 8, pp. 363-371, 2002. · Zbl 05461988
[4]	M. Aggarwal, R. D. Kent, and A. Ngom, “Genetic algorithm based scheduler for computational grids,” in Proceedings of the 19th International Symposium on High Performance Computing Systems and Applications (HPCS ’05), pp. 209-215, May 2005.
[5]	G. Malewicz, A. L. Rosenberg, and M. Yurkewych, “On scheduling complex dags for internet-based computing,” in Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS ’05), April 2005.
[6]	L. He, S. A. Jarvis, D. P. Spooner, D. Bacigalupo, G. Tan, and G. R. Nudd, “Mapping DAG-based applications to multiclusters with background workload,” in Proceedings of the IEEE International Symposium on Cluster Computing and the Grid, pp. 855-862, May 2005.
[7]	G. T. Ross and R. M. Soland, “A branch and bound algorithm for the generalized assignment problem,” Mathematical Programming, vol. 8, pp. 91-103, 1975. · Zbl 0308.90028
[8]	R. M. Chen, S. T. Lo, and Y. M. Huang, “Combining competitive scheme with slack neurons to solve real-time job scheduling problem,” Expert Systems with Applications, vol. 33, no. 1, pp. 75-85, 2007.
[9]	F. E. Sandnes, “Secure distributed configuration management with randomised scheduling of system-administration tasks,” IEICE Transactions on Information and Systems, vol. E86-D, no. 9, pp. 1601-1610, 2003.
[10]	M. Basu, “Hybridization of artificial immune systems and sequential quadratic programming for dynamic economic dispatch,” Electric Power Components and Systems, vol. 37, no. 9, pp. 1036-1045, 2009.
[11]	J. H. Holland, “Genetic algorithms and classifier systems: foundations and future directions,” in Proceedings of the 2nd International Conference on Genetic Algorithms and Their Application, 1987.
[12]	S. Kirkpatrick, C. D. Gelatt Jr., and M. P. Vecchi, “Optimization by simulated annealing,” Science, vol. 220, no. 4598, pp. 671-680, 1983. · Zbl 1225.90162
[13]	F. Glover, “Tabu search-part I,” ORSA Journal on Computing, vol. 1, no. 3, pp. 190-206, 1989. · Zbl 0753.90054
[14]	F. Glover, “Tabu search-part II,” ORSA Journal on Computing, vol. 2, no. 1, pp. 4-32, 1990. · Zbl 0771.90084
[15]	M. Dorigo and L. M. Gambardella, “Ant colony system: a cooperative learning approach to the traveling salesman problem,” IEEE Transactions on Evolutionary Computation, vol. 1, no. 1, pp. 53-66, 1997.
[16]	J. Kennedy and R. Eberhart, “Particle swarm optimization,” in Proceedings of the 4th IEEE International Conference on Neural Networks, pp. 1942-1948, December 1995.
[17]	J. Oh and C. Wu, “Genetic-algorithm-based real-time task scheduling with multiple goals,” Journal of Systems and Software, vol. 71, no. 3, pp. 245-258, 2004. · Zbl 05433527
[18]	Z. Liu and H. Wang, “GA-based resource-constrained project scheduling with the objective of minimizing activities’ cost,” in Proceedings of the International Conference on Intelligent Computing (ICIC ’05), vol. 3644 of Lecture Notes in Computer Science, pp. 937-946, August 2005.
[19]	N. Amjady and A. Shirzadi, “Unit commitment using a new integer coded genetic algorithm,” European Transactions on Electrical Power, vol. 19, no. 8, pp. 1161-1176, 2009.
[20]	O. Sinnen, L. A. Sousa, and F. E. Sandnes, “Toward a realistic task scheduling model,” IEEE Transactions on Parallel and Distributed Systems, vol. 17, no. 3, pp. 263-275, 2006. · Zbl 05106808
[21]	K. Bouleimen and H. Lecocq, “A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version,” European Journal of Operational Research, vol. 149, no. 2, pp. 268-281, 2003. · Zbl 1040.90015
[22]	K. H. Kim and K. C. Moon, “Berth scheduling by simulated annealing,” Transportation Research B, vol. 37, no. 6, pp. 541-560, 2003.
[23]	G. Wan and B. P.-C. Yen, “Tabu search for single machine scheduling with distinct due windows and weighted earliness/tardiness penalties,” European Journal of Operational Research, vol. 142, no. 2, pp. 271-281, 2002. · Zbl 1082.90531
[24]	S. G. Ponnambalam, P. Aravindan, and S. V. Rajesh, “Tabu search algorithm for job shop scheduling,” International Journal of Advanced Manufacturing Technology, vol. 16, no. 10, pp. 765-771, 2000.
[25]	S. T. Lo, R. M. Chen, Y. M. Huang, and C. L. Wu, “Multiprocessor system scheduling with precedence and resource constraints using an enhanced ant colony system,” Expert Systems with Applications, vol. 34, no. 3, pp. 2071-2081, 2008.
[26]	W. J. Gutjahr and M. S. Rauner, “An ACO algorithm for a dynamic regional nurse-scheduling problem in Austria,” Computers and Operations Research, vol. 34, no. 3, pp. 642-666, 2007. · Zbl 1120.90019
[27]	F. Zhao, Y. Hong, D. Yu, Y. Yang, and Q. Zhang, “A hybrid particle swarm optimisation algorithm and fuzzy logic for process planning and production scheduling integration in holonic manufacturing systems,” International Journal of Computer Integrated Manufacturing, vol. 23, no. 1, pp. 20-39, 2010.
[28]	T. L. Lin, S. J. Horng, T. W. Kao et al., “An efficient job-shop scheduling algorithm based on particle swarm optimization,” Expert Systems with Applications, vol. 37, no. 3, pp. 2629-2636, 2010.
[29]	H. Liu, A. Abraham, and Z. Wang, “A multi-swarm approach to multi-objective flexible job-shop scheduling problems,” Fundamenta Informaticae, vol. 95, no. 4, pp. 465-489, 2009.
[30]	R. M. Chen, C. L. Wu, C. M. Wang, and S. T. Lo, “Using novel particle swarm optimization scheme to solve resource-constrained scheduling problem in PSPLIB,” Expert Systems with Applications, vol. 37, no. 3, pp. 1899-1910, 2010.
[31]	C. Chiu, M. J. J. Wu, Y. T. Tsai, N. H. Chiu, M. S. H. Ho, and H. J. Shyu, “Constrain-based particle swarm optimization (CBPSO) for call center scheduling,” International Journal of Innovative Computing, Information and Control, vol. 5, no. 12, pp. 4541-4549, 2009.
[32]	M. F. Tasgetiren, Y. C. Liang, M. Sevkli, and G. Gencyilmaz, “A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem,” European Journal of Operational Research, vol. 177, no. 3, pp. 1930-1947, 2007. · Zbl 1110.90044
[33]	J. Behnamian, M. Zandieh, and S. M. T. Fatemi Ghomi, “Due windows group scheduling using an effective hybrid optimization approach,” International Journal of Advanced Manufacturing Technology, vol. 46, no. 5-8, pp. 721-735, 2010. · Zbl 1197.90195
[34]	Y. Hei, X. Li, K. Yi, and H. Yang, “Novel scheduling strategy for downlink multiuser MIMO system: particle swarm optimization,” Science in China F, vol. 52, no. 12, pp. 2279-2289, 2009. · Zbl 1181.94084
[35]	M. Clerc and J. Kennedy, “The particle swarm-explosion, stability, and convergence in a multidimensional complex space,” IEEE Transactions on Evolutionary Computation, vol. 6, no. 1, pp. 58-73, 2002. · Zbl 05451976
[36]	S. Hartmann, “Project scheduling with multiple modes: a genetic algorithm,” Annals of Operations Research, vol. 102, no. 1, pp. 111-135, 2001. · Zbl 1024.90039
[37]	F. F. Boctor, “Heuristics for scheduling projects with resource restrictions and several resource-duration modes,” International Journal of Production Research, vol. 31, no. 11, pp. 2547-2558, 1993.
[38]	P. Brucker, A. Drexl, R. Möhring, K. Neumann, and E. Pesch, “Resource-constrained project scheduling: notation, classification, models, and methods,” European Journal of Operational Research, vol. 112, no. 1, pp. 3-41, 1999. · Zbl 0937.90030
[39]	D. Bratton and J. Kennedy, “Defining a standard for particle swarm optimization,” in Proceedings of the IEEE Swarm Intelligence Symposium (SIS ’07), pp. 120-127, April 2007.
[40]	D. J. Watts and S. H. Strogatz, “Collective dynamics of ‘small-world’ networks,” Nature, vol. 393, no. 6684, pp. 440-442, 1998. · Zbl 1368.05139
[41]	J. N. Lin and H. Z. Wu, “Scheduling in grid computing environment based on genetic algorithm,” Journal of Computer Research and Development, vol. 41, no. 12, pp. 2195-2199, 2004 (Chinese).
[42]	Project Scheduling Problem Library, PSPLIB, http://129.187.106.231/psplib/.
[43]	W. Herroelen, B. De Reyck, and E. Demeulemeester, “Resource-constrained project scheduling: a survey of recent developments,” Computers & Operations Research, vol. 25, no. 4, pp. 279-302, 1998. · Zbl 1040.90525
[44]	B. Jarboui, N. Damak, P. Siarry, and A. Rebai, “A combinatorial particle swarm optimization for solving multi-mode resource-constrained project scheduling problems,” Applied Mathematics and Computation, vol. 195, no. 1, pp. 299-308, 2008. · Zbl 1180.90125
[45]	J. Alcaraz, C. Maroto, and R. Ruiz, “Solving the multi-mode resource-constrained project scheduling problem with genetic algorithms,” Journal of the Operational Research Society, vol. 54, no. 6, pp. 614-626, 2003. · Zbl 1095.90541
[46]	J. Józefowska, M. Mika, R. Ró\Dzycki, G. Waligóra, and J. W\ceglarz, “Simulated annealing for multi-mode resource-constrained project scheduling,” Annals of Operations Research, vol. 102, no. 1-4, pp. 137-155, 2001. · Zbl 0990.90513
[47]	C. W. Chiang, Y. Q. Huang, and W. Y. Wang, “Ant colony optimization with parameter adaptation for multi-mode resource-constrained project scheduling,” Journal of Intelligent and Fuzzy Systems, vol. 19, no. 4-5, pp. 345-358, 2008. · Zbl 1210.90177
[48]	S. Hartmann and A. Drexl, “Project scheduling with multiple modes: a comparison of exact algorithms,” Networks, vol. 32, no. 4, pp. 283-297, 1998. · Zbl 1002.90025