×

zbMATH — the first resource for mathematics

An optimization model for divisible-load scheduling considering processor time-window. (Chinese. English summary) Zbl 1399.90093
Summary: A divisible-load scheduling problem under the constraint of processor time-window for heterogeneous distributed systems is presented, and the make-span is minimized by finding the optimal load partition strategy and the optimal distribution sequence of processors. On the basis of existing research, the concept of time-window is introduced first, which makes the model more practical. Then a novel divisible-load scheduling non-blocking model is proposed considering the time-window. Meanwhile, a genetic algorithm is designed for the proposed model. In order to solve the model quickly and efficiently, the load partition and the distribution sequence of processors are encoded at the same time. Different crossover operators are designed to optimize the load partition and the distribution sequence of processors, and a modification operator is designed to modify the load partition scheme which does not satisfy the constraint of processors’ time-window. Moreover, an efficient local search operator is also designed to speed up the convergence rate of the algorithm. Finally, simulation experiments are carried out, and the results show that under the constraint of the processor time-window, the proposed algorithm can improve the performance of the existing algorithms by at least 20%, which proves the correctness and effectiveness of the proposed algorithm.
MSC:
90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI