×

Divisible load scheduling in distributed system with buffer constraints: genetic algorithm and linear programming approach. (English) Zbl 1098.68017

Summary: Scheduling divisible loads in a single-level tree network/system with processors having finite buffer size is addressed. In earlier studies in divisible load scheduling the processors are assumed to have no buffer constraints or have infinite buffer capacity. Hence, the processing time and the load fractions assigned to the processors in the network are obtained by assuming that all the processors will stop computing at the same instant in time.
Also in earlier studies, a closed-form expression for the processing time is derived, and using this closed-form expression, an optimal sequence of load distribution is obtained. When the processors in the network have finite buffer then this assumption that all the processors stop computing at the same time instant is not valid. So for a network with buffer constraints, there are two important problems: (i) for a given sequence of load distribution, how to obtain the processing time, and the load fractions assigned to the processors, and (ii) for a given network, how to obtain the optimal sequence of load distribution. Here problem (i) of obtaining the processing time and the load fractions assigned to the processors in the network, for a given sequence of load distribution, is not difficult to solve and is modelled as a linear programming problem and its solution is obtained. For a single-level tree network with \(m\) child processors there are \(m!\) sequences of load distribution. The optimal sequence of load distribution is the sequence of load distribution, for which the processing time of the entire processing load is a minimum. So, problem (ii) of obtaining the optimal sequence of load distribution is difficult. It is shown in an earlier study that this problem (ii) is NP-hard.
In this paper, a genetic algorithm (GA) is used for problem (ii) to obtain the sequence of load distribution. Various issues related to genetic algorithms such as solution representation, selection methods and genetic operators are presented. Numerical results are provided to show the advantages of GA methodology.

MSC:

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems

Software:

Genocop; GAToolBox
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DOI: 10.1109/7.18637
[2] DOI: 10.1109/7.106129
[3] DOI: 10.1109/21.120070
[4] DOI: 10.1109/7.259524
[5] DOI: 10.1109/7.481247
[6] Bharadwaj J., Scheduling Divisible Loads in Parallel and Distributed Systems (1996)
[7] DOI: 10.1109/71.308534 · Zbl 05107667
[8] DOI: 10.1109/7.381944
[9] Special Issue on: Divisible Load Scheduling. 2003.Cluster Computing, 6
[10] Beaumont, O., Legrand, A. and Robert, Y., Optimal algorithms for scheduling divisible work loads on heterogeneous systems. Paper presented at the International Parallel and Distributed Processing Symposium (IPDPS’03), IEEE Computer Society Press.
[11] DOI: 10.1109/TPDS.2004.1271181 · Zbl 05106940
[12] DOI: 10.1109/71.895794 · Zbl 05107937
[13] DOI: 10.1016/S0898-1221(03)90190-8 · Zbl 1116.90356
[14] Drozdowski M., Found Comput Decision Sci. 27 pp 43– (2002)
[15] DOI: 10.1016/0898-1221(96)00156-3 · Zbl 0864.68004
[16] DOI: 10.1109/TPDS.2004.1264811 · Zbl 05106791
[17] Suresh, S., Mani, V., Omkar, S.N. and Kim, H.J. A real coded genetic algorithm for data partitioning and scheduling in networks with arbitrary processor release time. pp.529–539. 10th Asia-Pacific Computer Systems Architecture Conference, LNCS-3740
[18] DOI: 10.1109/7.892677
[19] Li, X., Bharadwaj, V. and Ko, C.C., 2001, Divisible load scheduling on a hypercube cluster with finite-size buffers and granularity constraints. Presented at the First IEEE/ACM International Symposium on Cluster Computing and the Grid, pp. 660–667
[20] DOI: 10.1023/A:1020971118034
[21] DOI: 10.1016/S0140-3664(03)00181-6 · Zbl 05397299
[22] DOI: 10.1023/A:1020910932147
[23] Drozdowski, M. and Wolniewicz, P., 2001, Technical report RA-001/2001, Institute of Computing Science, Poznan University of Technology on the complexity of divisible job scheduling with limited memory buffers.
[24] Beaumont, O., Legrand, A., Marchal, L. and Robert, Y., 2004, Independent and divisible task scheduling on heterogeneous star-shaped platforms with limited memory. Research report RA-2004-22, LIP, ENS, Lyon, France.
[25] Agrawal R., IEEE Trans Comput. 37 pp 1272– (1988)
[26] Ghose, D. and Kim, H.J., 2004, Technical report KNU/CI/MSL/001/2004, A generalized linear programming approach to optimal divisible load scheduling Kangwon National University, Department of Control and Instrumentation, Chunchon, Korea.
[27] Holland H.J., Adaptation in Natural and Artificial Systems (1975)
[28] Goldberg D.E., Genetic Algorithms in Search, Optimization and Machine Learning (1989) · Zbl 0721.68056
[29] David L., Handbook of Genetic Algorithms (1991)
[30] Michalewicz Z., Genetic Algorithms+Data Structures = Evolution Programs (1994) · Zbl 0818.68017
[31] DOI: 10.1109/71.265940 · Zbl 05106686
[32] DOI: 10.1109/71.790600 · Zbl 05107584
[33] Frieder O., IEEE Trans Knowledge Data Eng. 3 pp 1785– (2003)
[34] DOI: 10.1109/71.790598 · Zbl 05107582
[35] DOI: 10.1109/TPDS.2002.1036068 · Zbl 05107614
[36] DOI: 10.1145/225545.225546 · Zbl 0884.65144
[37] Joines, J. and Houck, C., 1994, On the use of non-stationary penalty functions to solve constrained optimization problems with genetic algorithms, Presented at the IEEE International Symposium on Evolutionary Computation, pp. 579–584
[38] Goldberg D.E., Presented at the First International Conference on Genetic Algorithms pp 154– (1985)
[39] Suresh, S., Mani, V., Omkar, S.N. and Kim, H.J., Genetic algorithms for divisile load scheduling, Technical report AE/GC/001/2004, Department of Aerospace Engineering, Indian Institute of Science, Bangalore, India.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.