What is resource allocation problem in DAA?

Answer 1

We consider scheduling problems in parallel and distributed

settings in which we need to schedule jobs on a

system offering a certain amount of some resource. Each job

requires a particular amount of the resource for its execution.

The total amount of the resource offered by the system is

different at different points of time. Our goal is to choose a

subset of jobs and schedule them such that at any timeslot,

the total amount of resource requirement does not exceed the

total amount of the resource available at that timeslot. We

wish to maximize the profit of the chosen subset of jobs.

The problem formulation is motivated by its applications

in environments such as cloud computing and bandwidth

allocation in networks. Below, we describe a real-life problem

encountered in scheduling scientific applications on a

massively parallel system.

We now describe a scheduling problem typically faced in

the scenario where a number of users are trying to execute

scientific applications on either a cluster of machines or a

supercomputer. The users have to make reservations for the

resources in order to execute their jobs. But, as there are

multiple users competing for the same resources, a user may

not be allocated all the resources she requested. For the sake

of simplicity, let us assume that the resources are processors

on the supercomputer or machines on the cluster. Consider

a particular user. The number of processors (or machines)

allocated to the user may be different at different points of

time (because of reservation policies and the presence of

critical jobs) The user gets to know in advance the number

of processors allocated to her for each timeslot. The user

has a set of jobs that she wishes to execute. Each job of the

user has a requirement on the number of processors needed

for execution. In addition, each job has a release time, a

processing time, a deadline and a profit. The user would

like to select a subset of jobs and schedule them in such

a way that at any timeslot, the total number of processors

required by the jobs active at the timeslot does not exceed the

total number processor available to the user at that timeslot.

Naturally, the user would wish to choose the subset of jobs

having the maximum profit. We would like to highlight that

such a scenario is frequently encountered in practice. We

assume that a job can be executed on any subset of machines

or processors as long as the resource requirement is met (i.e.,

the machines/processors are identical) and the jobs may not

be preempted. In fact, we consider a more general scenario

where job can even specify a set of time intervals where it

can be scheduled; note that this generalizes the notion of

release time and deadline.

Motivated by scheduling and bandwidth allocation scenarios

such as the above one, we study an abstract problem that

we call the Varying bandwidth resource allocation problem

with bag constraints (BAGVBRAP). We use bandwidth as

a generic term to refer to the quantity of the resource

under contention. So, the input will specify the bandwidth

available at each timeslot, and for each job, its bandwidth

requirement and the different time intervals in which it can

be scheduled. This kind of interval selection or interval

scheduling problems arise naturally in practice. We refer

to [1], [2], [3] for real-life applications of interval selection

and scheduling in parallel and distributed computing and

network management. The BAGVBRAP problem also has

applications in smart energy management. Here, we have a

set of electrical appliances that need to be scheduled over a

period of time, during which the amount of available power

may vary, due to the use of different power sources. The

BAGVBRAP problem generalizes several previously studied

scheduling and resource allocation problems. We next define

the problem and then discuss prior