Bé czi, K is ó ; Ki ály, Tamás; Omlo , Simon
A icle — Published Ve sion
Scheduling wi h non- enewable esou ces: minimizing he
sum o comple ion imes
Jou nal o Scheduling
P o ided in Coope a ion wi h:
Sp inge Na u e
Sugges ed Ci a ion: Bé czi, K is ó ; Ki ály, Tamás; Omlo , Simon (2024) : Scheduling wi h non-
enewable esou ces: minimizing he sum o comple ion imes, Jou nal o Scheduling, ISSN
1099-1425, Sp inge US, New Yo k, NY, Vol. 27, Iss. 2, pp. 151-164,
h ps://doi.o g/10.1007/s10951-024-00807-y
This Ve sion is a ailable a :
h ps://hdl.handle.ne /10419/315300
S anda d-Nu zungsbedingungen:
Die Dokumen e au EconS o dü en zu eigenen wissenscha lichen
Zwecken und zum P i a geb auch gespeiche und kopie we den.
Sie dü en die Dokumen e nich ü ö en liche ode komme zielle
Zwecke e iel äl igen, ö en lich auss ellen, ö en lich zugänglich
machen, e eiben ode ande wei ig nu zen.
So e n die Ve asse die Dokumen e un e Open-Con en -Lizenzen
(insbesonde e CC-Lizenzen) zu Ve ügung ges ell haben soll en,
gel en abweichend on diesen Nu zungsbedingungen die in de do
genann en Lizenz gewäh en Nu zungs ech e.
Te ms o use:
Documen s in EconS o may be sa ed and copied o you pe sonal
and schola ly pu poses.
You a e no o copy documen s o public o comme cial pu poses, o
exhibi he documen s publicly, o make hem publicly a ailable on he
in e ne , o o dis ibu e o o he wise use he documen s in public.
I he documen s ha e been made a ailable unde an Open Con en
Licence (especially C ea i e Commons Licences), you may exe cise
u he usage igh s as speci ied in he indica ed licence.
h p://c ea i ecommons.o g/licenses/by/4.0/
Jou nal o Scheduling (2024) 27:151–164
h ps://doi.o g/10.1007/s10951-024-00807-y
Scheduling wi h non- enewable esou ces: minimizing he sum o
comple ion imes
K is ó Bé czi1·Tamás Ki ály2·Simon Omlo 3
Accep ed: 5 Feb ua y 2024 / Published online: 24 Ma ch 2024
© The Au ho (s) 2024
Abs ac
We conside single-machine scheduling wi h a non- enewable esou ce. In his se ing, we a e gi en a se o jobs, each
cha ac e ized by a p ocessing ime, a weigh , and a esou ce equi emen . A ixed poin s in ime, ce ain amoun s o he
esou ce a e made a ailable o be consumed by he jobs. The goal is o assign he jobs non-p eemp i ely o ime slo s on
he machine, so ha each job has enough esou ce a ailable a he s a o i s p ocessing. The objec i e ha we conside is
he minimiza ion o he sum o weigh ed comple ion imes. The main con ibu ion o he pape is a PTAS o he case o
0 p ocessing imes (1| m =1,pj=0|wjCj). In addi ion, we show s ong NP-ha dness o he case o uni esou ce
equi emen s and weigh s (1| m =1,aj=1|Cj), hus answe ing an open ques ion o Gyö gyi and Kis. We also p o e
ha he schedule co esponding o he Sho es P ocessing Time Fi s o de ing p o ides a 3/2-app oxima ion o he la e
p oblem. Finally, we in es iga e a a ian o he p oblem whe e p ocessing imes a e 0 and he esou ce a i al imes a e
unknown. We p esen a (4+)-app oxima ion algo i hm, oge he wi h a (4−ε)-inapp oximabili y esul , o any ε>0.
Keywo ds App oxima ion algo i hm ·Non- enewable esou ces ·Polynomial- ime app oxima ion scheme ·S ong
NP-ha dness ·Scheduling ·Weigh ed sum o comple ion imes
An ex ended abs ac o his wo k appea ed in he 6 h In e na ional
Symposium on Combina o ial Op imiza ion (ISCO 2020). This
esea ch has been implemen ed wi h he suppo p o ided by he
Lendüle P og amme o he Hunga ian Academy o Sciences—G an
Numbe LP2021-1/2021, by he Minis y o Inno a ion and
Technology o Hunga y om he Na ional Resea ch, De elopmen
and Inno a ion Fund, inanced unde he ELTE TKP 2021-NKTA-62
unding scheme, and by Dynasne Eu opean Resea ch Council
Syne gy p ojec (ERC-2018-SYG 810115).
BK is ó Bé czi
[email p o ec ed]
Tamás Ki ály
[email p o ec ed]
Simon Omlo
[email p o ec ed]
1MTA-ELTE Ma oid Op imiza ion Resea ch G oup,
HUN-REN-ELTE Ege á y Resea ch G oup, Depa men o
Ope a ions Resea ch, Eö ös Lo ánd Uni e si y, Budapes ,
Hunga y
2HUN-REN-ELTE Ege á y Resea ch G oup, Depa men o
Ope a ions Resea ch, Eö ös Lo ánd Uni e si y, Budapes ,
Hunga y
3Facul y o S a is ics, TU Do mund Uni e si y, Do mund,
Ge many
1 In oduc ion
Scheduling p oblems wi h non- enewable esou ce con-
s ain s a ise na u ally in a ious a eas whe e esou ces like
aw ma e ials, ene gy, o inancial unding a i e a p ede e -
mined da es. In he gene al se ing, we a e gi en a se o jobs
and a se o machines. Each job is equipped wi h a equi e-
men ec o ha encodes he needs o he gi en job o he
di e en ypes o esou ces. The e is an ini ial s ock o each
esou ce, and some addi ional esou ce a i al imes in he
u u e a e known oge he wi h he a i ing quan i ies. The
aim is o ind a schedule o he jobs on he machines such
ha he necessa y esou ces a e a ailable o each job when
hei p ocessing begins.
We will use he s anda d α|β|γno a ion o G aham e
al. (1979). G igo ie e al. (2005) ex ended his no a ion
by adding he es ic ion m = o he β ield, meaning
ha he e a e esou ces ( m s ands o ‘ aw ma e ials’).
In he p esen pape , we concen a e on p oblem wi h a sin-
gle machine and a single esou ce, whe e he objec i e is
o minimize he weigh ed sum o comple ion imes, i.e.,
1| m =1|wjCj. While he e is an abundance o esul s
on he app oximabili y o he makespan objec i e, much less
123
152 Jou nal o Scheduling (2024) 27:151–164
is known abou he complexi y and app oximabili y o he
o al weigh ed comple ion ime objec i e.
Rela ed wo k Scheduling p oblems wi h esou ce es ic-
ions (also called inancial cons ain s, o aw ma e ial
equi emen s) we e in oduced by Ca lie and Kan (1982)
and by Slowi´nski (1984). Ca lie (1984) se led he compu a-
ional complexi y o se e al a ian s o he single machine
case. In pa icula , he showed ha 1| m =1|wjCjis
NP-ha d in he s ong sense. This was also p o ed indepen-
den ly by Ga a o e al. (2011). Kis (2015) showed ha he
p oblem emains weakly NP-ha d e en when he numbe o
esou ce a i al imes is 2. On he posi i e side, he ga e an
FPTAS o 1| m =1,q=2|wjCj. A a ian o he p ob-
lem whe e each job has p ocessing ime 1, he e a e q=n
esou ce a i al imes such ha i=iM and bi=M o
i=1,...,n, and M=j∈Jaj/nis an in ege , was con-
side ed in Ga a o e al. (2011). Gyö gyi and Kis (2019)ga e
polynomial ime algo i hms o se e al special cases, and also
showed ha he p oblem emains weakly NP-ha d e en unde
he e y s ong assump ion ha o each indi idual job, he
p ocessing ime, he esou ce equi emen and he weigh a e
equal. They also p o ided a 2-app oxima ion algo i hm o
his a ian , and a polynomial- ime app oxima ion scheme
(PTAS) o he a ian whe e he numbe o esou ce a i al
imes is a cons an and he p ocessing ime equals he weigh
o each job, while he esou ce equi emen s a e a bi a y.
Independen ly o he p esen pape , Gyö gyi and Kis
(2020) ecen ly published an analysis o simple g eedy algo-
i hms o se e al a ian s o he p oblem. They also showed
ha minimizing he sum o comple ion imes is NP-ha d e en
o wo esou ce a i al imes and uni esou ce equi emen s,
and p o ided a FPTAS o a a ian in which he jobs ha e
a bi a y weigh s, bu he numbe o esou ce a i al imes is
bounded by a cons an . None o ou esul s a e implied by
hei pape .
In compa ison o o al weigh ed comple ion ime, much
mo e is known abou he maximum makespan and maximum
la eness objec i es. Slowi´nski (1984) s udied he p eemp-
i e scheduling o independen jobs on pa allel un ela ed
machines wi h he use o addi ional enewable and non-
enewable esou ces unde inancial cons ain s. Toke e al.
(1991) examined a single-machine scheduling p oblem unde
non- enewable esou ce cons ain , using he makespan as
a pe o mance c i e ion. Xie (1997) gene alized his esul
o he p oblem wi h mul iple inancial esou ce cons ain s.
G igo ie e al. (2005) p esen ed polynomial ime algo i hms,
app oxima ions and complexi y esul s o single-machine
scheduling p oblems wi h uni o all-equal p ocessing imes
and maximum la eness and makespan objec i es. In a se ies
o pape s (Gyö gyi & Kis, 2014,2015a,2015b,2017,
Gyö gyi, 2017), Gyö gyi and Kis p esen ed app oxima ion
schemes and inapp oximabili y esul s bo h o single and
pa allel machine p oblems wi h he makespan and he maxi-
mum la eness objec i es. In Gyö gyi and Kis (2018), hey
p oposed a b anch-and-cu algo i hm o minimizing he
maximum la eness.
Ou esul s We i s conside he p oblem 1| m =1,aj=
1|Cj. The complexi y o his p oblem was posed as an
open ques ion in Gyö gyi and Kis (2018). We show ha he
p oblem is NP-ha d in he s ong sense.
Theo em 1 1| m =1,aj=1|Cjis s ongly NP-ha d.
In he ligh o Theo em 1, one migh be in e es ed in
inding an app oxima ion algo i hm o he p oblem. Gi en
any scheduling p oblem on a single machine, he Sho es
P ocessing Time Fi s (SPT) schedule o de s he jobs by
inc easing o de o p ocessing imes. We p o e ha sp p o-
ides a 3/2-app oxima ion. Al hough he algo i hm is e y
simple as i is me ely scheduling acco ding o he SPT o de ,
he analysis o he app oxima ion ac o is a he in ol ed.
Theo em 2 The SPT schedule gi es a 3
2-app oxima ion o
1| m =1,aj=1|Cj, and he app oxima ion gua an ee
is igh .
The second p oblem conside ed is he special case when
he p ocessing ime is 0 o e e y job. This se ing is ele an
o si ua ions whe e p ocessing imes a e negligible compa ed
o he gaps be ween esou ce a i al imes, and he bo leneck
is esou ce a ailabili y. Examples include inancial schedul-
ing p oblems whe e he jobs a e no ime consuming bu he
a ailabili y o unding a ies in ime, o p oduc ion p oblems
whe e p oduc s a e shipped a ixed ime in e als and p o-
duc ion ime is negligible compa ed o hese in e als. No e
ha he numbe o machines is i ele an i p ocessing imes
a e 0. Fi s we desc ibe a as and simple g eedy app oxima-
ion algo i hm o he p oblem.
Theo em 3 Fo 1| m =1,pj=0|Cjwj, he e exis s a
6-app oxima ion algo i hm wi h unning ime O(nlog n).
A e he p oo o Theo em 3, we gi e a sligh ly mo e
complica ed (4+ε)-app oxima ion ha illus a es one o he
impo an ideas o he gene al PTAS.
As a nex s ep owa d he main esul , we p esen a PTAS
o he case o a cons an numbe o esou ce a i al imes.
This p ocedu e will be used as a sub ou ine in ou algo i hm
o he gene al case.
Theo em 4 Conside he numbe o a i al imes q o be
cons an . Fo any ixed posi i e in ege k, he e is a (1+q
k)-
app oxima ion algo i hm o 1| m =1,pj=0|Cjwj
wi h unning ime O(nqk+1).
The main con ibu ion o he pape is a PTAS o he same
p oblem wi h an a bi a y numbe o esou ce a i al imes.
123
Jou nal o Scheduling (2024) 27:151–164 153
Theo em 5 The e exis s a PTAS o 1| m =1,pj=
0|Cjwj.
Finally, we conside a a ian o 1| m =1,pj=
0|Cjwjwhe e he numbe o esou ce a i al imes and
he a i ing quan i ies (in he o de o he a i als) a e known,
bu he a i al imes a e unknown. We deno e his p oblem by
1| m =1,pj=0, iunknown|Cjwj. We obse e ha
he g eedy 6-app oxima ion algo i hm o Theo em 3is ac u-
ally a 6-app oxima ion o his p oblem, oo. We can imp o e
he app oxima ion ac o o ge he ollowing igh esul .
Theo em 6 Fo 1| m =1,pj=0, iunknown|Cjwj,
he e exis s a (4+ε)-app oxima ion wi h unning ime poly-
nomial in 1/ε and he inpu leng h. Mo eo e , he e is no
(4−ε)-app oxima ion algo i hm o he p oblem o any
ε>0.
O ganiza ion The es o he pape is o ganized as ollows.
Basic no a ion and e minology a e in oduced in Sec .2.A
s ong NP-ha dness p oo and a 3/2-app oxima ion algo-
i hm o p oblem 1| m =1,aj=1|Cja e gi en in
Sec .3. Resul s on p oblem 1| m =1,pj=0|Cja e dis-
cussed in Sec .4, whe e a g eedy 6-app oxima ion, a PTAS
o he case o cons an esou ce a i al imes, and a PTAS o
he gene al case a e p esen ed. We close he pape in Sec . 5
by analyzing he a ian whe e he esou ce a i al imes a e
unknown.
2 P elimina ies
Th oughou he pape , we will use he ollowing no a ion. We
a e gi en a se Jo njobs. Each job j∈Jhas a non-nega i e
in ege p ocessing ime pj, a non-nega i e weigh wj, and
a esou ce equi emen aj.The esou ces a i e a ime
poin s 1,..., q, and he amoun o esou ce ha a i es
a iis deno ed by bi. We migh assume ha q
i=1bi=
n
j=1ajholds. We will always assume ha 1=0, as his
does no a ec he app oxima ion a io o ou algo i hms.
We will use he no a ion Bk=i≥kbi o he amoun o
esou ce ha a i es no ea lie han k.
The jobs should be p ocessed non-p eemp i ely on a sin-
gle machine. A schedule is an o de ing o he jobs, ha is,
a mapping σ:J→[n], whe e σ(j)=imeans ha job
jis he i h job scheduled on he machine. The comple ion
ime o job jin schedule σis deno ed by Cσ
j. We will d op
he index σi he schedule is clea om he con ex . In any
easonable schedule, he e is an idle ime be o e a job jonly
i he e is no enough esou ce le o s a ja e inishing he
las job be o e he idle pe iod. Hence, he comple ion ime
o job jis de e mined by he o de ing and by he esou ce
a i al imes, as jwill be scheduled a he i s momen when
he p eceding jobs a e al eady inished and he amoun o
a ailable esou ce is a leas aj.
A di e en ep esen a ion o schedules will be used in
Sec .4, whe e he p ocessing imes a e assumed o be 0. In
his case, e e y job is p ocessed a one o he esou ce a i al
imes in any easonable schedule. Hence, a schedule can be
ep esen ed by a mapping π:J→[q], whe e π(j)deno es
he index o he esou ce a i al ime when job jis p ocessed.
3 The p oblem 1| m =1,aj=1|Cj
3.1 S ong NP-comple eness
The aim o his sec ion is o p o e Theo em 1.
Theo em 1 1| m =1,aj=1|Cjis s ongly NP-ha d.
P oo Recall ha all ajand wj alues a e 1, and each job
has an in ege p ocessing ime pj. The numbe o esou ce
a i al imes is pa o he inpu .
We p o e NP-comple eness by educ ion om he 3-
Pa i ion p oblem. The inpu con ains numbe s B∈N,
n∈N, and xj∈N(j=1,...,3n)such ha B/4<xj<
B/2 and 3n
j=1xj=nB (no e ha we will no use he uppe
bound xj<B/2 in he p oo ). A easible solu ion is a pa i-
ion J1,...,Jno [3n]such ha |Ji|=3 and j∈Jixj=B
o e e y i∈[n]. In con as o he Pa i ion p oblem, he
3- pa i ion p oblem emains NP-comple e e en when he
in ege s xja e bounded abo e by a polynomial in n. Tha
is, he p oblem emains NP-comple e e en when he num-
be s in he inpu a e ep esen ed as una y numbe s (Ga ey &
Johnson, 1979, Pages 96–105 and 224).
We assume wi hou loss o gene ali y ha Bis di isible
by 4, so xj≥B/4+1≥2 o e e y j.Le K=4nB.The
educ ion o 1| m =1,aj=1|Cjin ol es h ee ypes
o jobs.
No mal jobs These co espond o he numbe s xjin he
3- Pa i ion ins ance, so he e a e 3no hem and he p o-
cessing ime pjo he j h no mal job is xj.
Small jobs Thei p ocessing ime is 1 and he e a e nK o
hem.
La ge jobs Thei p ocessing ime is Kand he e a e nK o
hem.
The e a e also h ee ypes o esou ce a i als (see Fig. 1):
Type 1 Th ee esou ces a i e a imes i(B+K)(i=
0,...,n−1).
Type 2 One esou ce a i es a i(B+K)+j(i=0,...,n−1,
j=B,...,B+K−1).
Type 3 One esou ce a i es a n(B+K)+iK (i=
0,...,nK −1).
123
154 Jou nal o Scheduling (2024) 27:151–164
Fig. 1 Resou ce a i als in he
educ ion o 3- Pa i ion
Suppose ha he 3- Pa i ion ins ance has a easible
solu ion J1,...,Jn. We conside he ollowing schedule σ:
esou ces o Type 1 a e used by no mal jobs, such ha jobs in
Jia e scheduled be ween (i−1)(B+K)and iB+(i−1)K
(in sp o de ). Type 2 esou ces a e used by small jobs ha
s a immedia ely. Type 3 esou ces a e used by he la ge jobs
ha also s a immedia ely a he esou ce a i al imes (see
Fig.2).
Ins ead o Cj, we conside he equi alen shi ed objec-
i e unc ion (Cj− (j)−pj), whe e (j)is he a i al
ime o he esou ce used by job jand pjis he p ocess-
ing ime o j—we assume wi hou loss o gene ali y ha
esou ces a e used by jobs in o de o a i al. No e ha all
e ms o (Cj− (j)−pj)a e nonnega i e. As small jobs
and la ge jobs s a immedia ely a he a i al o he co e-
sponding esou ce in schedule σ, hei con ibu ion o he
shi ed objec i e unc ion is 0. The jobs in Jiha e o al p o-
cessing ime B, and hei con ibu ion o he shi ed objec i e
unc ion is wice he p ocessing ime o he sho es job, plus
he p ocessing ime o he second sho es job, which is a
mos B. Hence he schedule σhas objec i e alue a mos
nB.
We claim ha i he 3- Pa i ion ins ance has no easible
solu ion, hen he objec i e alue o any schedule is s ic ly
la ge han nB. Fi s , no ice ha i a la ge job is scheduled o
s a be o e ime n(B+K), hen (Cj− (j)−pj)has a
e m s ic ly la ge han nB as he e is a esou ce ha a i es
while he la ge job is p ocessed and is no used o mo e
han nB ime uni s. Simila ly, i he i s la ge job s a s a
n(B+K)bu uses a esou ce ha a i ed ea lie , hen he
esou ce ha a i es a n(B+K)is no used o mo e han
nB ime uni s. We can conclude ha he i s la ge job uses
he esou ce a i ing a n(B+K).
I he i s la ge job does no s a a n(B+K), hen all
la ge jobs ha e posi i e con ibu ion o he objec i e alue, so
again, he objec i e alue is la ge han nB. We can he e o e
assume ha he la ge jobs s a exac ly a n(B+K)+iK
(i=0,...,nK −1)and ha he e is no idle ime be o e
(B+K)n. In pa icula , his means ha all o he jobs a e
al eady comple ed a ime (B+K)n.
Conside Type 2 esou ces a i ing a i(B+K)+j
(j=B,...,B+K−1) o some ixed i≤n−1. I
he i s esou ce o he second esou ce in his in e al is no
used immedia ely, hen none o he subsequen ones a e, so
he objec i e alue is a leas K−1>nB. Hence, we may
assume ha bo h he i s and he second esou ces a e used
immedia ely. This means ha i s esou ce is used immedi-
a ely by a small job, since no mal jobs ha e p ocessing ime
a leas 2. Thus, he esou ce a i ing a i(B+K)+Bis
immedia ely used by a small job, o e e y i≤n−1.
Suppose ha some o he esou ce in he in e al i(B+
K)+j(j=B+1,...,B+K−1) is used by a no mal
job. I i is ollowed by a small job, hen we may imp o e
he objec i e alue by exchanging he wo. Thus, in his case,
we can assume ha he las esou ce o he in e al is used
by a no mal job ( his al eady implies i≤n−2, because a
la ge job s a s a n(B+K)), and also he Type 1 esou ces
a i ing a (i+1)(B+K)a e used by no mal jobs. Bu his
is impossible, because no mal jobs ha e p ocessing ime a
leas B/4+1, and a small job s a s a ime (i+1)(B+K)+B
by.
To sum up, we can assume ha all esou ces o Type 2
a e used immedia ely by small jobs. This means ha no mal
jobs ha e o use esou ces o Type 1, and mus exac ly ill he
gaps o leng h Bbe ween he a i al o esou ces o Type 2.
This is only possible i he 3-pa i ion ins ance has a easible
solu ion, concluding he p oo o Theo em 1.
3.2 Sho es p ocessing ime i s o uni esou ce
equi emen s
In he p e ious sec ion, we ha e seen ha scheduling wi h a
non- enewable esou ce is s ongly NP-ha d al eady o uni
esou ce equi emen s. Now we show ha scheduling he jobs
acco ding o an sp o de ing p o ides a 3/2-app oxima ion
o he p oblem wi h uni weigh and uni esou ce equi e-
men s, hus p o ing Theo em 2.
Theo em 2 The SPT schedule gi es a 3
2-app oxima ion o
1| m =1,aj=1|Cj, and he app oxima ion gua an ee
is igh .
P oo Conside an ins ance Io he p oblem. Le σsp and
σop deno e he SPT and he op imal schedule, and le sp
and op deno e he sum o he comple ion imes in hese
wo schedules, espec i ely. We will use he no a ion jsp (i),
psp (i),Ssp (i), and Csp (i) o he i h job in he SPT sched-
ule, i s p ocessing ime, i s s a ing ime, and i s comple ion
ime, espec i ely. We also use simila no a ion wi h subsc ip
op o he op imal schedule.
Ou s a egy is o simpli y he ins ance by e ealing i s
s uc u al p ope ies while no dec easing sp
op . This way we
ge an uppe bound o he app oxima ion ac o . We i s
conside he esou ce a i al imes.
Claim 1 We may assume ha he i h esou ce a i es a
Sop (i) o i =1,...,n.
123
Jou nal o Scheduling (2024) 27:151–164 155
Fig. 2 The schedule
co esponding o a easible
solu ion o 3- Pa i ion
P oo As he i h esou ce is used by job jop (i), he a i al
ime o ha esou ce is a mos Sop (i). I we mo e he a i al
ime o he esou ce o exac ly Sop (i), hen op does no
change and sp canno dec ease.
The nex claim shows ha we can ge id o he idle imes
in he op imal schedule.
Claim 2 We may assume ha he e is no idle ime in schedule
op , ha is, Sop (i)=Cop (i−1) o i =2,...,n.
P oo Suppose ha he e is some isuch ha i>Cop (i−1).
We educe iby Δ= i−Cop (i−1) o all i≥i. Then
o each i≥i, he comple ion ime Cop (i)dec eases by
Δ. Fo each i≥i, he comple ion ime Csp (i)dec eases
by a mos Δ. This ollows om he ac ha he esou ce
a i al imes dec ease by Δand he comple ion ime o he
p e ious job can dec ease by a mos Δ(which can be shown
by induc ion). Hence op dec eases by a leas as much as
sp . Since sp ≥op , he a io sp
op will no dec ease by his
change.
Nex , we modi y he p ocessing imes.
Claim 3 We may assume ha pop (1)>psp (1)and ha
psp (1)=0.
P oo I bo h schedules s a wi h he same job, hen we can
emo e he job om he ins ance and dec ease b1by 1. Then
op dec eases by he same amoun as sp . We can epea
his un il he schedules s a wi h jobs o di e en p ocess-
ing imes. Now pop (1)>psp (1), since sp s a s wi h he
sho es job. Dec easing he p ocessing ime o job jsp (1)
o 0 (wi hou changing any a i al ime) dec eases sp by
psp (1)and op by a leas psp (1). We can elimina e idle
imes in he new op imal schedule as in he p oo o Claim
2.
Claim 4 We may assume ha pj∈{0,1} o all j ∈J.
P oo Le pmax =maxj∈Jpjbe he maximum p ocessing
ime. Scaling he p ocessing imes by di iding all p ocessing
and a i al imes by pmax has no e ec on sp
op , hence we may
assume ha pmax =1. Now assume ha he e is a job jwi h
p=pj∈(0,1).Le p=min{pj|j∈J,pj>p}and
p=max{pj|j∈J,pj<p}.Le Jp={j∈J|pj=p}
be he se o jobs wi h p ocessing ime p. We will show ha
we can ei he inc ease he p ocessing ime o all jobs in Jp
o po dec ease he p ocessing ime o all jobs in Jp o p
wi hou dec easing sp
op .
Fo j∈J,le hjdeno e he numbe o jobs p ocessed
a e jin σop plus 1, i.e. hj=n−σop (j)+1. We conside
he e ec o inc easing he p ocessing imes o all jobs in Jp
by some Δ∈[p−p,p−p]and app op ia ely modi ying he
a i al imes o he esou ces o ma ch he new s a ing imes
(no e ha Δmay be nega i e, in which case we dec ease he
p ocessing imes and s a ing imes). This will inc ease op
by Δj∈Jphj. Indeed, e e y ime we change he p ocessing
ime o one job j, he comple ion ime o jand o all jobs
a e jwill be inc eased by Δ.
No ice ha he o de o he jobs in he SPT schedule does
no change. Conside he SPT schedule be o e he change. Le
job j∈Jbe any job, le j0be he he i s job ha is p ocessed
a e he las idle ime be o e he s a ing ime o j, and le
i=σsp (j0)(i he e is no idle ime be o e j,le i=1). Le
jbe he numbe o jobs j∈Jpwi h σop (j)<i; no ice
ha hese a e exac ly he jobs whose modi ica ion a ec s i.
Thus, he a i al ime iis changed by Δ o each o hose
jobs, so he new a i al ime is i+Δ j. This means ha he
s a ing ime o job j0in he changed SPT schedule is a leas
Ssp
j0+Δ j.Nowle gjbe he numbe o jobs j∈Jp ha
a e p ocessed in he ime in e al [ i,Csp
j)be o e he change.
Fo each o hose jobs, he p ocessing ime is changed by Δ
and he job is s a ed a o a e i+Δ j, since he SPT o de
does no change. Thus, he new comple ion ime o jis a
leas Csp
j+Δ j+Δgj. Consequen ly, sp will inc ease by
a leas j∈J( j+gj)Δ i Δ>0, and dec ease by a mos
j∈J( j+gj)|Δ|i Δ<0.
I j∈J( j+gj)
j∈Jphj≥sp
op , hen inc easing he p ocessing imes
in Jp o pwill no dec ease sp
op . O he wise, dec easing he
p ocessing imes in Jp o pwill no dec ease sp
op . Each ime
we apply his ope a ion, he numbe o dis inc p ocessing
imes dec eases by 1. Finally, we ge an ins ance whe e he
only p ocessing imes a e pmin =0 and pmax =1.
Finally, we modi y he o de o he jobs in he op imal
solu ion. I σop and σsp p ocess a job o leng h 0 a he
same ime, hen we can emo e he job om he ins ance and
educe he numbe o esou ces ha a i e a his ime by 1.
This will educe op and sp by he same amoun .
Le be he ime a which schedule σsp i s s a s o
p ocess a job o leng h 1. On one hand, σop does no p ocess
jobs o leng h 0 be o e by he abo e a gumen . On he o he
123
156 Jou nal o Scheduling (2024) 27:151–164
hand, he e is no idle ime a e in σsp , because ha would
mean idle ime in σop . Thus, i we mo e all jobs o leng h
0 and hei co esponding esou ce a i als in σop o ime
, hen sp does no change bu op dec eases. We may hus
assume ha schedule σop p ocesses e e y job o leng h 0 a
.
Le k1be he numbe o jobs o leng h 0 a e he ans o -
ma ions. These a e p ocessed a ime in σop , and hese a e
exac ly he jobs p ocessed be o e ime in σsp . Thus, he e
a e k1a i al imes be o e , whe e σop p ocesses jobs o
leng h 1. Le k1+k2be he o al numbe o jobs o leng h 1.
We conclude ha σop i s p ocesses k1jobs o leng h 1,
hen k1jobs o leng h 0 and hen k2jobs o leng h 1, while
σsp s a s wi h he jobs o leng h 0 ha ing a lo o idle ime
in he beginning and hen consecu i ely p ocesses all jobs o
leng h 1 (see Fig.3). The weigh ed sums o comple ion imes
a e hen gi en by
op =k1(k1+1)
2+k2
1+k2k1+k2(k2+1)
2
and
sp =k1(k1−1)
2+k2k1+k1(k1+1)
2
+(k1+k2)k1+k2(k2+1)
2.
We ge
3
2op −sp =k2
1
4+k2
2
4−k1k2
2+3k1+k2
4
≥(k1−k2)2
4≥0,
showing ha he app oxima ion ac o is a mos 3
2.
Se ing k2=k1and le ing k1go o in ini y gi es us a
sequence o ins ances such ha sp
op con e ges o 3
2as we
ha e sp =9
2k2
1+O(k1)and op =3k2
1+O(k1).This
concludes he p oo o Theo em 2.
4 The p oblem 1| m =1,pj=0|Cjwj
In his sec ion we conside he p oblem 1| m =1,pj=
0|Cjwj, ano he special case o 1| m =1|Cjwj.
The p oblem clea ly is NP-ha d e en o q=2 as he knap-
sack p oblem can be educed o i . Indeed, maximizing he
weigh o he i ems in he knapsack is equi alen o he ask o
maximizing he weigh o jobs ha a e scheduled a he i s
esou ce a i al ime. Recall ha Kis (2015) ga e a FPTAS
o 1| m =1|Cjwjwhen he e a e wo esou ce a i al
imes.
Fi s we gi e a 6-app oxima ion o he p oblem based
on a g eedy app oach. We also desc ibe a mo e complica ed
(4+ε)-app oxima ion ha illus a es one o he impo an
ideas o he mo e gene al PTAS. Then we p o ide a PTAS
o he case when q, he numbe o esou ce a i al imes is
a cons an . This algo i hm will be used as a sub ou ine in he
PTAS o he gene al case. Finally, we p o e he main esul
o he pape which is a PTAS o he case o an a bi a y
numbe o esou ce a i al imes.
Since he p ocessing imes a e 0, e e y job is p ocessed
a one o he a i al imes in any op imal schedule. Thus, a
schedule can be ep esen ed by a mapping π:J→[q],
whe e π(j)deno es he index o he esou ce a i al ime
when job jis p ocessed. A schedule is easible i he esou ce
equi emen s a e me , ha is, i
j:π(j)≤k
aj≤
i≤k
bi(1)
o all 1 ≤k≤q. As we assume ha ibi=jajholds,
his is equi alen o
j:π(j)≥k
aj≥Bk(2)
o all 1 ≤k≤q, whe e Bk=i≥kbi. Conside he se o
jobs ha a e no p ocessed be o e a gi en ime poin k. Then
(2) says ha i he esou ce equi emen s o hese jobs add up
o a leas Bk, hen ou schedule is easible. We will mos ly
use his la e cha ac e iza ion o easibili y, as ou algo i hms
assign he jobs o la e ime poin s i s . The in ui ion is ha
we can bound he app oxima ion a io by gi ing su icien ly
good uppe bounds o e e y kon he o al weigh W≥ko
jobs ha a e p ocessed a ime poin ko la e . We p esen
he e one such uppe bound, ha will be used in he i s esul
o he nex sec ion, as well as in Sec .5.Fo 1≤k≤q,le
mk=min{w(J):J⊆J,
j∈J
aj≥Bk},
and le Mkbe he se o jobs whe e he minimum is achie ed.
Lemma 1 Le πbe a easible schedule, and le W≥k=
j:π(j)≥kwj.I W
≥k≤α·mk o e e y 1≤k≤q, hen π
is an α-app oxima ion.
P oo Le πop be he op imal schedule, and le Wop
≥k=
j:πop (j)≥kwj. We can bound he objec i e alue o πby
j∈J
wjCj=q
k=1( k− k−1)W≥k≤αq
k=1( k− k−1)mk
≤αq
k=1( k− k−1)Wop
≥k=αj∈JwjCop
j,
which is α imes he objec i e alue o πop .
123
Jou nal o Scheduling (2024) 27:151–164 157
Fig. 3 Schedules σop and σsp
a e he educ ions. The jobs o
leng h 0 a e scheduled in σop a
he i s esou ce a i al ime
when mul iple esou ces a i e
4.1 A g eedy 6-app oxima ion o a bi a y q
The idea o ou i s algo i hm is o ha e a balance be ween
adding jobs ha ha e small weigh s and jobs ha ha e high
esou ce equi emen s. Mo e p ecisely, we will assign jobs o
he ime poin s in e e se o de . When we add a job o he se
o jobs scheduled a e a gi en ime poin , we will choose he
mos ine icien job, i.e. he job minimizing wj/ajamong all
jobs ha ha e weigh a mos he weigh Wo all jobs ha
ha e al eady been chosen up o his poin . I he e is no job
wi h weigh a mos W, hen we simply choose a job wi h
minimal weigh . In ui i ely, his ule gua an ees ha he jobs
we choose a e no oo e icien bu hei o al weigh is no
oo la ge ei he .
Algo i hm 1 G eedy algo i hm o 1| m =1,pj=
0|Cjwj.
Inpu : Jobs Jwi h |J|=n, esou ce equi emen s aj, weigh s
wj, esou ce a i al imes 1≤... ≤ qand esou ce quan i ies
b1,...bq.
Ou pu : A easible schedule π.
1: Se A=0.
2: Se W=0.
3: o i om 0 o q−1do
4: while A<Bq−ido
5: i he e is an unassigned job jwi h wj≤W hen
6: Le jbe an unassigned job wi h wj≤Wminimizing
wj/aj.
7: else
8: Le jbe an unassigned job minimizing wj.
9: W←W+wj
10: A←A+aj
11: Se π(j)=q−i.
12: e u n π
Theo em 3 Fo 1| m =1,pj=0|Cjwj, he e exis s a
6-app oxima ion algo i hm wi h unning ime O(nlog n).
P oo I is clea ha he schedule π e u ned by Algo i hm 1
sa is ies (2), so i is easible. We claim ha πsa is ies he
equi emen s o Lemma 1wi h α=6, i.e., W≥k≤6mk o
e e y k.Le Mkdeno e he se o jobs whe e he minimum
mkis achie ed.
To bound W≥k o a gi en k, we conside he algo i hm
up un il he las s ep whe e q−i≥k, and di ide i in o 3
phases (some o hese may be emp y):
– Phase 1: un il he i s i e a ion whe e Wbecomes a leas
mk
– Phase 2: un il he las i e a ion whe e A<Bk
– Phase 3: he las s ep, whe e Abecomes a leas Bk.
A he end o phase 1, we ha e W≤2mk, because a he
beginning o he las s ep o phase 1, we ei he add a job o
weigh a mos W(which is less han mka ha poin ), o
we add a job o minimum weigh , which is again a mos mk
because some job in Mkis s ill unassigned.
In phase 2, he o al weigh added is a mos mk. Indeed,
h oughou phase 2, some job in Mkis s ill unassigned, bu
W≥mk, so we always pick an unassigned job jwi h wj≤
Wminimizing wj/aj. Thus, he job selec ed is a leas as
ine icien as any unassigned job in Mk, so he o al weigh
o he selec ed jobs canno be la ge han mk.
A he beginning o phase 3, we ha e A<Bkand mk≤
W≤3mk. A his poin , he e is s ill an unassigned job in
Mk, so he selec ed job has weigh a mos W≤3mk. Thus,
he o al weigh is a mos 6mk.
The unning ime bound ollows by o de ing he jobs
acco ding o hei weigh and by using AVL ees o picking
jin he while loop.
The ollowing example shows ha he bound is igh . We
ha e 5 jobs wi h weigh s w1=w2=1−2ε,w3=1−ε,
w4=1 and w5=3. The esou ce equi emen s a e a1=
a2=ε/5, a3=1−ε/2, a4=1 and a5=4. The esou ce
a i al imes a e 1=0 and 2=1, wi h esou ce quan i ies
b1=5−ε/10 and b2=1. He e he op imum solu ion is
o schedule he job wi h weigh 1 o ime poin 2and all he
emaining jobs o ime poin 1. Howe e , ou algo i hm will
schedule he job wi h weigh 1 o ime poin 1and all he
emaining jobs o 2.
123
158 Jou nal o Scheduling (2024) 27:151–164
4.2 A (4+")-app oxima ion o a bi a y q
Now we gi e a sligh ly be e app oxima ion o he p ob-
lem. The algo i hm is a bi mo e complica ed han he one
p esen ed in Sec .4.1, bu he p oo illus a es one o he
impo an ideas o he gene al PTAS.
The idea o he algo i hm is as ollows. We may assume
wi hou loss o gene ali y ha esou ce a i al imes a e in e-
ge , because mul iplying all a i al imes by a la ge in ege
does no change he p oblem. Fi s we shi all esou ce a i al
imes o powe s o 2. Fo each a i al ime iin he shi ed
ins ance, we apply he FPTAS by Kis (2015) o he ins ance
which has only wo esou ce a i al imes 1and i, and he
esou ce quan i y o iis Bi. Deno e he se o jobs assigned
o i his way by Li. Then, we schedule each job ja he la es
ime poin iwhe e j∈Li, i.e. π(j)=max{i:j∈Li}.
Mo e o mally, le Ibe an ins ance o 1| m =1,pj=
0|jCjwj. We assume 1=0 and 2=1 ( he la e
assump ion is wi hou loss o gene ali y because we can add
an a i al ime wi h 0 esou ce a i al). We de ine a new
ins ance Io 1| m =1,pj=0|jCjwjwi h shi ed
esou ce a i al imes as ollows. Se
i=0i i=1,
2i−2 o i=2,...,log2( q)+2,
and
b
i=bii i=1,2,
[b: ∈(2i−3,2i−2]] o i=3,...,log2( q)+2.
Claim 5 A solu ion o Iwi h weigh ed sum o comple ion
imes W can be ans o med in o a solu ion o Iwi h
weigh ed sum o comple ion imes a mos 2W. Fu he mo e,
any easible schedule o Iis also easible o I.
P oo Le us de ine ∗
i=min{
: i≤
} o i=1,...,q.
Le πbe he solu ion o I. Then assigning all jobs ha a e
assigned o ime poin i o ∗
igi es us a easible solu ion
o I. By his change, he comple ion o any job is a mos
doubled ( ecall ha each iis assumed o be in ege ).
Since he a ailable amoun o esou ces a each ime in I
is a mos as much as in I, a easible schedule o Iis also
a easible schedule o I.
Claim 6 The e exis s a polynomial ime (2+ε)-app oxima ion
algo i hm o cons an ε o all ins ances Iwhe e he
esou ce a i al imes a e in ege powe s o 2.
P oo We use he p ocedu e ha we desc ibed abo e, i.e., o
each i>1 we sol e he ins ance wi h Bi esou ce a i ing a
iand he es a 1, using he FPTAS p o ided by Kis (2015).
As de ined abo e, Liis he se o jobs assigned o iby he
FPTAS, and π(j)=max{i:j∈Li}.
Le α=1+ε.Le πop be an op imum solu ion and le
Jop
kbe he se o jobs jwi h πop (j)=k.Weha e
w(Li)≤α
q
k=i
w(Jop
k)
o i=1,...,q. Then we ge
2α
j∈J
wjCπop
j=
q
i=2
(2α) ·2i−2w(Jop
i)
=
q
i=2
α·2i−2w(Jop
i)⎛
⎝1+
∞
j=1
2−j⎞
⎠
≥
q
i=2
α2i−2
q
k=i
w(Jop
k)
≥
q
i=2
2i−2w(Li),
hus he app oxima ion a io ollows.
The wo claims show ha his app oach leads o a (4+ε)-
app oxima ion wi h unning ime polynomial in 1/ε and he
inpu leng h.
4.3 PTAS o cons an q
Theaimo hissec ionis ogi eaPTAS o hecasewhen he
numbe o esou ce a i al imes is a cons an . The algo i hm
is a gene aliza ion o a well known PTAS o he knapsack
p oblem, and will be used la e as a sub ou ine in he PTAS
o an a bi a y numbe o esou ce a i al imes. The idea
is o choose a numbe k∈Z+, guess he khea ies jobs
ha a e p ocessed a each esou ce a i al ime i, and hen
de e mine he emaining jobs ha a e scheduled a iin a
g eedy manne . Since we go o e all possible se s con aining
a mos kjobs o each esou ce a i al ime, he e is an
exponen ial dependence on he numbe qo esou ce a i al
imes in he unning ime.
Theo em 4 Conside he numbe o a i al imes q o be
cons an . Fo any ixed posi i e in ege k, he e is a (1+q
k)-
app oxima ion algo i hm o 1| m =1,pj=0|Cjwj
wi h unning ime O(nqk+1).
P oo We claim ha Algo i hm 2sa is ies he equi emen s
o he heo em. Le πop be an op imal schedule and de ine
Jop
i={j∈J:πop (j)=i}.Le Hop
ibe he se o he
khea ies jobs in Jop
ii |Jop
i|≥k, o he wise le Hop
i=
Jop
i.Le Ji={j∈J:π(j)=i}deno e he se o jobs
123
