CLASS-CONSTRAINED RESOURCE ALLOCATION PROBLEMS

The work considers 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 problems 
of parallelizable jobs.  

In the 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 received when in classic 
scheduling problems, in which each job is characterized by its length, we 
characterize each job by additional parameters that 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). The objective is to minimize the completion time
of all the jobs. Previous work in this area dealt only with cases in which 
these parameters are not limited at all, or limited to the value one.

Since all 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 packing problems, we consider also the on-line version, 
in which the set of items to be packed is unknown in advance and the placement 
of each item needs to be done upon its arrival.