Search

We study an extension of the well-known bin-packing problem to multiple dimensions, resulting in the "vector packing" problem. The problem is to find the minimum number of multidimensional bins to pack a set of vectors into without exceeding the bin capacity in any dimension of any bin. While we use approximate methods to inform our search, we ultimately return optimal solutions. This work is an attempt to extend the results of [Kor03] to multiple dimensions and combine it with some new techniques. A hybrid DFBnB algorithm which searches in two separate problem spaces is used as the final algorithm. Our hybrid algorithm also uses a heuristic to assist the search, and an approximate algorithm to initially bound the cost of an optimal solution. The resulting algorithm can be run on vector-packing problems with any number of dimensions, and good results are shown for up to five-dimensional problems. An attempt is also made to define a method to compare these results with future algorithms, as consensus on appropriate test suites for vector-packing problems seems to be lacking.

International audience; In this paper, we introduce a generalization of the vector bin packing problem, where the bins have variable sizes. This generalization can be used to model virtual machine placement problems and in particular to build feasible solutions for the machine reassignment problem. We propose several families of greedy heuristics for this problem and show that they are flexible and can be adapted to handle additional constraints. We present structural properties of the machine reassignment problem, that allow us to decompose it into smaller subproblems and adapt our heuristics to them. We evaluate our heuristics on academic benchmarks of the vector bin packing problem, a randomly generated vector bin packing problem with heterogeneous bins benchmark as well as Google’s realistic instances of the machine reassignment problem.

International audience; We propose a novel job scheduling approach for homogeneous cluster computing platforms. Its key feature is the use of virtual machine technology to share fractional node resources in a precise and controlled manner. Other VM-based scheduling approaches have focused primarily on technical issues or extensions to existing batch scheduling systems, while we take a more aggressive approach and seek to find heuristics that maximize an objective metric correlated with job performance. We derive absolute performance bounds and develop algorithms for the online, non-clairvoyant version of our scheduling problem. We further evaluate these algorithms in simulation against both synthetic and real-world HPC workloads and compare our algorithms to standard batch scheduling approaches. We find that our approach improves over batch scheduling by orders of magnitude in terms of job stretch, while leading to comparable or better resource utilization. Our results demonstrate that virtualization technology coupled with lightweight online scheduling strategies can afford dramatic improvements in performance for executing HPC workloads.

High-Multiplicity encoding is a natural encoding of data. In scheduling, it simply consists in stating once the characteristics of each type of tasks and the number of tasks of this type. This encoding is very compact and natural but it is generally supposed in scheduling that all tasks are specified separately. High-Multiplicity scheduling, when considered, raises many complexity issues because of the small input size. The aim of this thesis is to provide insights on how to cope with high-multiplicity scheduling problems. We also seek to contribute to scheduling and packing in general. We expose different techniques and approaches and use them to solve specific scheduling and packing problems. We study the high-multiplicity single machine scheduling problem with forbidden start and completion times and show that this problem is polynomial with large diversity instances. We present the identical coupled-task scheduling problem and display many difficulties and issues occurring in high-multiplicity scheduling on this problem. We improve the best upper and lower bounds on the bin stretching problem. We study the vector packing problems with heterogeneous bins and propose heuristics for this problem. Finally, we present a general reduction algorithm for packing problems which can be applied in polynomial time, even with high-multiplicity encoding of the input., L’encodage High-Multiplicity est un encodage naturel des données consistant, en ordonnancement, à réunir les tâches similaires et, pour chaque type, décrire les caractéristiques d’une seule tâche et le nombre de tâches de ce type. Cet encodage est très compact et lorsqu’il est considéré, pose de nombreux problème pour analyser la complexité des problèmes considérés. L’objectif de cette thèse est de proposer des techniques permettant de traiter les problèmes high-multiplicity. Nous exposons celles-ci à travers divers exemples. Nous étudions le problème d’ordonnancement high-multiplicity avec indisponibilités des opérateurs et montrons que celui-ci est polynomial lorsque le nombre de type de tâches est supérieur au nombre d’instants d’indisponibilités. Nous étudions les problème d’ordonnancement de tâches couplées identiques et montrons sur ce problème de nombreuses difficultés majeures de l’ordonnancement high-multiplicity. Nous améliorons les meilleures bornes supérieures et inférieures sur le problème de bin stretching. Nous étudions le problème de vector packing avec des récipients hétérogènes et proposons des heuristiques pour celui-ci. Enfin, nous proposons un algorithme de réduction très général pour les problèmes de placement d’objets. Cet algorithme peut être appliqué en temps polynomial en le nombre de types d’objets et de récipients.

We propose a novel job scheduling approach for homogeneous cluster computing platforms. Its key feature is the use of virtual machine technology to share fractional node resources in a precise and controlled manner. Other VM-based scheduling approaches have focused primarily on technical issues or on extensions to existing batch scheduling systems, while we take a more aggressive approach and seek to find heuristics that maximize an objective metric correlated with job performance. We derive absolute performance bounds and develop algorithms for the online, non-clairvoyant version of our scheduling problem. We further evaluate these algorithms in simulation against both synthetic and real-world HPC workloads and compare our algorithms to standard batch scheduling approaches. We find that our approach improves over batch scheduling by orders of magnitude in terms of job stretch, while leading to comparable or better resource utilization. Our results demonstrate that virtualization technology coupled with lightweight online scheduling strategies can afford dramatic improvements in performance for executing HPC workloads.; Nous proposons une nouvelle approche de l'ordonnancement des applications sur les calculateurs parallèles homogènes. Sa principale caractéristique est l'utilisation de machines virtuelles pour organiser le partage de \emph{fractions} des ressources de manière précise et contrôlée. Les approches existantes utilisant des machines virtuelles se sont principalement intéressées à des problèmes techniques ou à l'extension des systèmes de batch existants. Notre approche est beaucoup plus aggressive et nous recherchons des heuristiques qui optimisent une métrique particulière. Nous établissons des bornes de performance absolues et nous développons des algorithmes pour la version en-ligne, non clairvoyante, de notre problème d'ordonnancement. Nous évaluons ces algorithmes au moyen de simulations impliquant soit des traces synthétiques, soit de traces d'un système HPC existant. Nous comparons par ce moyen nos solutions aux algorithmes d'ordonnancement par \emph{batch} les plus classiques. Nous montrons que notre approche permet d'améliorer de plusieurs ordres de grandeur le facteur de ralentissement (\emph{stretch}) subit par les applications par rapport aux systèmes de \emph{batch}, tout en ayant une utilisation comparable ou moindre des ressources. Nos résultats montrent que l'utilisation conjointe des techniques de virtualisation et de stratégies d'ordonnancement en-ligne permet d'améliorer très significativement l'exécution des applications dans les systèmes de calcul HPC.

We solve the Bin Packing problem in $O^*(2^k)$ time, where $k$ is the number of items less or equal to one third of the bin capacity. This parameter measures the distance from the polynomially solvable case of only large (i.e., greater than one third) items. Our algorithm is actually designed to work for a more general Vector Bin Packing problem, in which items are multidimensional vectors. We improve over the previous fastest $O^*(k! \cdot 4^k)$ time algorithm. Our algorithm works by reducing the problem to finding an exact weight perfect matching in a (multi-)graph with $O^*(2^k)$ edges, whose weights are integers of the order of $O^*(2^k)$. To solve the matching problem in the desired time, we give a variant of the classic Mulmuley-Vazirani-Vazirani algorithm with only a linear dependence on the edge weights and the number of edges, which may be of independent interest. Moreover, we give a tight lower bound, under the Strong Exponential Time Hypothesis (SETH), showing that the constant $2$ in the base of the exponent cannot be further improved for Vector Bin Packing. Our techniques also lead to improved algorithms for Vector Multiple Knapsack, Vector Bin Covering, and Perfect Matching with Hitting Constraints., Comment: ICALP 2022