Two-dimensional packing problems and optimization in distributed computing systems.
A classical problem of scheduling the set of tasks optimizing load balancing for a set of given processors was considered iin 1966 by Graham who proposed algorithm sending each task to a least loaded machine (processor). This was the first example of approximate algorithm with guaranteed constant approximation quality. But all tasks and processors (machines) in Graham's example were simple (only one processor was sufficient for each task). On the other hand Graham's algorithm was an on-line one that is each task was sended to processor without knowing future tasks. With wide use of computational clusters very actual became the problem of scheduling parallel tasks on the set of parallel clusters in the class of on-line algorithms. This problem has very close relation to a two dimensional packing problem, so-called multiple strip packing problem which we consider in this paper. So, in this paper the problem of scheduling parallel tasks on a group of clusters is addressed. We propose new formal model for this process as an optimization of packing rectangles in a set of strips of different widths (Multiple Strip Packing problem). Some modern results concerning this problem and some open problems are presented. Practical aspects of optimization of scheduling parallel tasks process with different criteria of its quality are considered. The description of modeling system developed in the ISP RAS for experimental investigation of scheduling algorithms is presented and its properties are described.
Proceedings of the Institute for System Programming, vol. 26, issue 1, 2014, pp. 483-502.
ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).
DOI: 10.15514/ISPRAS-2014-26(1)-21Full text of the paper in pdf (in Russian) Back to the contents of the volume