Scheduling with Many Shared Resources

2025-05-03 0 0 790.68KB 26 页 10玖币

侵权投诉

Max A. Deppert !

Kiel University, Kiel, Germany

Klaus Jansen !

Kiel University, Kiel, Germany

Marten Maack !

Paderborn University, Paderborn, Germany

Simon Pukrop !

Paderborn University, Paderborn, Germany

Malin Rau !

Universität Hamburg, Hamburg, Germany

Abstract

Consider the many shared resource scheduling problem where jobs have to be scheduled on identical

parallel machines with the goal of minimizing the makespan. However, each job needs exactly

one additional shared resource in order to be executed and hence prevents the execution of jobs

that need the same resource while being processed. Previously a (2

(

+ 1))-approximation

was the best known result for this problem. Furthermore, a 6

5-approximation for the case with

only two machines was known as well as a PTAS for the case with a constant number of machines.

We present a simple and fast 5/3-approximation and a much more involved but still reasonable

1.5-approximation. Furthermore, we provide a PTAS for the case with only a constant number

of machines, which is arguably simpler and faster than the previously known one, as well as a

PTAS with resource augmentation for the general case. The approximation schemes make use of the

N-fold integer programming machinery, which has found more and more applications in the ﬁeld of

scheduling recently. It is plausible that the latter results can be improved and extended to more

general cases. Lastly, we give a 5/4−εinapproximability result for the natural problem extension

where each job may need up to a constant number (in particular 3) of diﬀerent resources.

2012 ACM Subject Classiﬁcation Theory of computation →Scheduling algorithms

Keywords and phrases

Scheduling, Approximation, Parallel Identical Machines, Resource Con-

straints, Conﬂicts

Funding

Max A. Deppert: Supported by the German Research Foundation (DFG) project JA

612/25-1

Klaus Jansen: Supported by the German Research Foundation (DFG) project JA 612/25-1

Marten Maack: Supported by the German Research Foundation (DFG) within the Collaborative

Research Centre “On-The-Fly Computing” under the project number 160364472 — SFB 901/3.

Simon Pukrop: Supported by the German Research Foundation (DFG) within the Collaborative

Research Centre “On-The-Fly Computing” under the project number 160364472 — SFB 901/3.

Malin Rau: Supported by DFG Research Group ADYN under grant DFG 411362735

1 Introduction

We consider the problem of makespan minimization on identical parallel machines with many

shared resources, or many shared resources scheduling (MSRS) for short. In this problem,

we are given

identical machines, a set

jobs, and a processing time or size

pj∈N≥0

for each job

j∈ J

. Furthermore, each job needs exactly one additional shared resource in

order to be executed and no other job needing the same resource can be processed at the

same time. Hence, the jobs are partitioned into (non-empty) classes

, i.e.,

, such

arXiv:2210.01523v1 [cs.DS] 4 Oct 2022

2 Scheduling with Many Shared Resources

that each class corresponds to one of the resources. A schedule (

σ, t

)maps each job to a

machine

J → {

, . . . , m}

and a starting time

J → N≥0

. It is called valid if no two

jobs overlap on the same machine and no two jobs of the same class are processed in parallel,

i.e.:

∀j, j0∈ J , j 6=j0with σ(j) = σ(j0):t(j) + pj≤t(j0)or t(j0) + p0

j≤t(j)

∀c∈ C :j, j0∈c, j 6=j0:t(j) + pj≤t(j0)or t(j0) + p0

j≤t(j)

The makespan

Cmax

of a schedule is deﬁned as

maxj∈J t

(

) +

and the goal is to ﬁnd a

schedule with minimum makespan. Note that MSRS also models the case in which some

jobs do not need a resource since in this case private resources can be introduced.

State of the Art and Motivation.

The study of scheduling problems with additional

resources has a long and rich tradition. Already in 1983, Blazewicz et al. [

] provided a

classiﬁcation for such problems along with basic hardness results and several additional

surveys have been published since then [

]. The MSRS problem, in particular, was

introduced by Hebrard et al. [

] who considered the scheduling of download plans for Earth

observation satellites and provided a (2

(

+1))-approximation for the problem. Strusevich

[

] revisited MSRS and presented an additional application in human resource management.

Moreover, he provided a faster, alternative (2

(

+ 1))-approximation that is claimed

to be simpler as well, and a 6

5-approximation for the case with only two machines. The

work also extends the three ﬁeld notation for scheduling problems based on the convention

for additional resources introduced in [

] to encompass the problem at hand. In particular,

MSRS is denoted as

P|res ·

111

|Cmax

in this notation. The most recent result regarding

MSRS is due to Dósa et al. [

] who provided an eﬃcient polynomial time approximation

scheme (EPTAS) for MSRS with a constant number of machines. In fact, the EPTAS even

works for a more general setting where each job

additionally may only be assigned to a

machine belonging to a given set M(j)of eligible machines.

We employ standard notation regarding approximation schemes: A polynomial time

approximation scheme (PTAS) provides a polynomial time (1 +

)-approximation for each

ε >

0. It is called eﬃcient, or EPTAS, if its running time is of the form

/ε

)

poly

(

|I|

)where

is some function and

|I|

the encoding length of the instance

. Moreover, an EPTAS is

called fully polynomial time approximation scheme (FPTAS) if the function

is a polynomial.

Since MSRS includes makespan minimization on identical machines (without resource

constraints) as a subproblem, it is NP-hard already on two machines and strongly NP-hard

if the number of machines is part of the input due to straightforward reductions from the

partition and 3-partition problem, respectively. Hence, approximation schemes are essentially

the best we can hope for.

The MSRS problem has also been considered with regard to the total completion time

objective [

]. The study of this variant is motivated by a scheduling problem in the

semiconductor industry. On one hand, the authors show NP-hardness for generalizations

of the problem, and on the other, they argue that the approach yielding a polynomial time

algorithm for total completion time minimization in the absence of resource constraints leads

to a (2 −1/m)-approximation for the considered problem.

Another way of looking at MSRS is to consider it as variant of scheduling with conﬂicts,

where a conﬂict graph is given in which the jobs are the vertices and no two jobs connected by

an edge may be processed at the same time. This problem was introduced for unit processing

times by Baker and Coﬀman in 1996 [

]. It is known to be APX-hard [

] already on two

machines with job sizes at most 4 and a bipartite agreement graph, i.e., the complement of

M. A. Deppert, K. Jansen, M. Maack, S. Pukrop, and M. Rau 3

the conﬂict graph. There are many positive and negative results for diﬀerent versions of this

problem (see, e.g., [

] and the references therein). For instance, the problem is NP-hard

on cographs with unit-size jobs but polynomial time solvable if the number of machines is

constant [6]. Note that in the case of MSRS, we have a particularly simple cograph, i.e., a

collection of disjoint cliques.

Results.

We present a 5

3-approximation in Section 2, a 3

2-approximation in Section 3,

approximation schemes in Section 4, and inapproximability results in Section 5. Note that

the 5

3- and 3

2-approximation have better approximation ratios than the previously known

(2m/(m+ 1))-approximation already for 6 and 4 machines, respectively.

The 5

3-approximation is a simple and fast algorithm that is based on placing full classes

of jobs taking special care of classes containing jobs with particularly big sizes and of classes

with large processing time overall. While the 3

2-approximation reuses some of the ideas

and observations of the ﬁrst result, it is much more involved. To achieve the second result,

we ﬁrst design a 3

2-approximation for the instances in which jobs cannot be too large

relative to the optimal makespan and then design an algorithm that carefully places classes

containing such large jobs and uses the ﬁrst algorithm as a subroutine for the placement of

the remaining classes. Note that our approaches are very diﬀerent to the one in [

], which

successively chooses jobs based on their size and the size of the remaining jobs in their class

and then inserts them with some procedure designed to avoid resource conﬂicts, and the one

in [29], which merges the classes into single jobs to avoid resource conﬂicts.

We provide an EPTAS for the variant of MSRS where the number of machines is

constant and an EPTAS with resource augmentation for the general case. In particular, we

need

(1 +

)

many machines in the latter result. Both results make use of the basic

framework introduced in [

] which in turn utilizes relatively recent algorithmic results

for integer programs (IPs) of a particular form – so-called N-fold IPs. Compared to the

mentioned work by Dósa et al. [

] – which provides an EPTAS for the case with a constant

number of machines as well – our result is arguably simpler and faster (going from at least

triply exponential in

m/ε

to doubly exponential). We also provide the result with resource

augmentation for the general case, which may be reﬁned in the future to work without

resource augmentation as well. Moreover, it seems plausible that the use of N-fold IPs in

the context of scheduling with additional resources may lead to further results in the future,

which do not have to be limited to approximation schemes.

Finally, we provide inapproximability results for variants of MSRS where each job may

need more than one resource. In particular, we show that there is no better than 5

approximation for the variant of MSRS with multiple resources per job, unless

even if no job needs more than three resources and all jobs have processing time 1, 2 or 3.

Previously, the APX-hardness result due to Even et al. [

] for scheduling with conﬂicts was

known, which did focus on a diﬀerent context and in particular does not provide bounds

regarding the number of resources a job may require.

Further Related Work.

As mentioned above, there exists extensive research regarding

scheduling with additional resources and we refer to the surveys [

–

] for an overview.

For instance, the variant with only one additional shared renewable resource where each job

needs some fraction of the resource capacity has received a lot of attention (see [

]

for some relatively recent examples). Interestingly, Hebrard [

] pointed out that this basic

setting is more closely related MSRS than it ﬁrst appears: Consider the case that we have

dedicated machines, i.e., each job is already assigned to a machine and we only have to

4 Scheduling with Many Shared Resources

choose the starting times, each job needs one unit of the singly additional shared resource,

and the shared resource has some integer capacity. This problem is equivalent to MSRS if

the multiple resources taken on the roles of the machines and the machines take the role of

the single resource. Hence, results for variants of this setting translate to MSRS as well. For

instance, MSRS can be solved in polynomial time if at most two classes include more than

one job [25] and [16] yields a (3 + ε)-approximation.

Scheduling with conﬂicts has also been studied from the orthogonal perspective, where

jobs that are in conﬂict may not be processed on the same machines. This problem was

already studied in the 1990’s (see e.g. [

]), and there has been a series of recent results

[

] regarding the setting corresponding to MSRS where the conﬂict graph is a

collection of disjoint cliques.

Preliminaries.

We introduce some additional notation, and a ﬁrst observation that will be

used throughout the following sections.

For any set of jobs

let

(

) =

Pj∈Xpj

denote its total processing time. Also let

(

) =

for all jobs

j∈ J

. While creating or discussing a schedule, for any machine

denote by

(

)the (current) total load of jobs on that machine

. Subsequently, for a set

of machines M,p(M) = Pm∈Mp(m).

For any combination of a set

X∈ { J ,C }

, a relation

∗ ∈ { <, ≤,≥, > }

, and a num-

ber

, we deﬁne

X∗λ

{x∈X|p(x)∗λ}

. Furthermore, given an interval

let

{x∈X|p(x)∈v}

. For example it holds that

J>1/2

{j∈ J | p(j)>1/2}

and

C(1/2,3/4]

{c∈ C | p(c)∈(1/2,3/4] }.

INote 1. It holds that OPT ≥max {p(J)

m,maxc∈C p(c)}.

Hence, we assume that

m < |C|

as otherwise there is a trivial schedule with one machine per

class. Furthermore, let us assume that we sort the jobs in decreasing order of processing

time. Consider the jobs

and

jm+1

at position

and

+ 1. Note that it has to hold that

OPT ≥p

(

) +

(

jm+1

), since either

jm+1

has to be scheduled on the same machine as one

of the ﬁrst mjobs, or two of the ﬁrst mjobs have to be scheduled at the same machine.

2 A 5/3-approximation

In this section we introduce a ﬁrst simple algorithm that gives some intuition on the problem

that will be used more cleverly in the next section. We start by lower bounding the makespan

of an optimal schedule and construct a schedule with makespan at most

. The algorithm

works by placing full classes of jobs in a speciﬁc order. More precisely, ﬁrst classes that

contain a job of size at least

, then classes with total processing time larger than

, and

lastly all residual classes get placed.

ITheorem 2.

There exists an algorithm that, for any instance

of MSRS, ﬁnds a schedule

with makespan bounded by

(

|I|

)steps, where for the jobs

and

jm+1

with

-th and

(

+1)-st largest processing time we deﬁne

max {1

mp(J),maxc∈C p(c), p(jm) + p(jm+1)}

As noted earlier,

denotes a lower bound on the makespan. We scale each job by 1

As a consequence all jobs have a processing time in (0

1] and the total load is bounded by

Denote by CB+:= {c∈ C | |c∩ J>1/2|= 1 }all classes containing a job of size greater than

2. We aim to ﬁnd a schedule with makespan in [1

3]. The following two observations

are directly implied by the deﬁnition of T.

IObservation 3. For each class c∈ C it holds that |c∩ J>1/2| ≤ 1.

M. A. Deppert, K. Jansen, M. Maack, S. Pukrop, and M. Rau 5

IObservation 4. It holds that |CB+|=|J>1/2| ≤ m.

Lastly, we address classes with a large total processing time.

ILemma 5.

Each class

c∈ C>2/3\ CB+

can be partitioned into parts

and

c\c1

such

that 1/3≤p(c1)≤2/3and p(c2)≤2/3. This partition can be found in time O(|c|).

Proof.

If there exists a job

with

(

)

3, we deﬁne

{j>}

and

c\c1

. Note

that

does not contain a job with processing time larger than 1

2and hence,

(

)

∈

and p(c2) = p(c)−p(c1)<1−1/3=2/3.

Otherwise, greedily add jobs from

to an empty set

until

(

)

≥

3and set

c\c1

Since all the jobs of

have processing time at most 1

3, it holds that

(

)

∈

3].

Consequently, it holds that p(c2)≤2/3as well. J

Algorithm: Algorithm_5/3

Step 1. Consider all classes containing a job with processing time larger than 1

CB+

Each of these classes is assigned to an individual machine, and all jobs from such a class are

scheduled consecutively, see Figure 1a.

Step 2. Consider all remaining classes with total processing time larger than 2

C>2/3\CB+

Try to add these classes on the machines ﬁlled with the classes

CB+

and afterward proceeds

to empty machines, see Figure 1b. If the considered machine has load in (1

3],close the

machine and no longer attempt to place any other job on it. Note that after placing the classes

CB+

all machines remained open. Let

be the machine we try to place class

c∈ C>2/3\ CB+

on. If

has load

(

)

≤

−p

(

), place the entire class on this machine and close it.

Otherwise, partition the class

in two parts

and

such that

(

)

≤p

(

)

≤

3(cf.

Lemma 5). Place the larger part

on the current machine starting at 5

−p

(

)and close

it, moving to the next machine. All jobs on this machine are delayed such that the ﬁrst job

starts at

(

). All jobs from

are scheduled between 0and

(

)on this machine. If it has

load of at least 1, this machine is closed as well.

Step 3 (Greedy). Finally, place the classes

C≤2/3\ CB+

, see Figure 1c. Consider the residual

machines one after another and add each class

c∈ C≤2/3\ CB+

entirely to the considered

machine. As soon as the load of a machine exceeds 1close it and move to the next.

J1J2

J3J4J5

(a) Classes with large jobs

J2J3

(b) Placing large classes

J2J3

Figure 1 The three steps of the algorithm (where J>1/2={J1,...,J5})

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

SchedulingwithManySharedResourcesMaxA.Deppert!KielUniversity,Kiel,GermanyKlausJansen!KielUniversity,Kiel,GermanyMartenMaack!PaderbornUniversity,Paderborn,GermanySimonPukrop!PaderbornUniversity,Paderborn,GermanyMalinRau!UniversitätHamburg,Hamburg,GermanyAbstractConsiderthemanysharedresourcescheduling...

展开>> 收起<<

Scheduling with Many Shared Resources.pdf

共26页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Scheduling with Many Shared Resources

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: