טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentTamir Tamar
SubjectClass-Constrained Resource Allocation Problems
DepartmentDepartment of Computer Science
Supervisor Professor Hadas Shachnai


Abstract

We consider variants of classic packing and scheduling problems. These variants are motivated by problems arising in storage management for multimedia systems, in production planning, and in scheduling parallelizable jobs. 

In our packing problems, sets of items of different types need to be placed in multiple bins. The items may be of different sizes and values. Each bin has a limited capacity, and a bound on the number of different types of items it can hold. In the class-constrained multiple knapsack problem we wish to maximize the total value of the packed items. In the class-constrained fair placement problem our goal is to place the same (large) portion from each set. In the class-constrained bin-packing problem, we seek to minimize the number of (identical) bins, needed for packing all the items.

A scheduling problem with similar constraints is obtained from classic scheduling when we characterize each job by its length and two additional parameters, which specify the maximal number of machines that can share its execution (allotment constraint), and the maximal number of machines that can process the job simultaneously (parallelism constraint). Our objective is to minimize the overall completion time of the schedule (makespan). Previous work in this area dealt only with cases in which these parameters are unbounded, or get the value one.

Since all of the above problems are NP-hard, we focus on devising and analyzing approximation algorithms. We present hardness results, approximation algorithms, and characterize classes of instances for which optimal solutions can be found efficiently. For the above packing problems, we consider also the on-line version, in which the set of items to be packed is unknown in advance and the decision regarding the placement of each item needs to be taken upon its arrival.