English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

The paper considers single-machine scheduling problems with a non-renewableresource. In this setting, we are given a set jobs, each of which ischaracterized by a processing time, a weight, and the job also has someresource requirement. At fixed points in time, a certain amount of the resourceis made available to be consumed by the jobs. The goal is to assign the jobsnon-preemptively to time slots on the machine, so that at any time theirresource requirement does not exceed the available amounts of resources. Theobjective that we consider here is the minimization of the sum of weightedcompletion times.  We give polynomial approximation algorithms and complexity results for singlescheduling machine problems. In particular, we show strong NP-hardness of thecase of unit resource requirements and weights ($1|rm=1,a_j=1|\sum C_j$), thusanswering an open question of Gy\"orgyi and Kis. We also prove that theschedule corresponding to the Shortest Processing Time First ordering providesa $3/2$-approximation for the same problem. We give simple constant factorapproximations and a more complicated PTAS for the case of $0$ processing times($1|rm=1,p_j=0|\sum w_jC_j$). We close the paper by proposing a new variant ofthe problem in which the resource arrival times are unknown. A$4$-approximation is presented for this variant, together with an$(4-\varepsilon)$-inapproximability result.

Scheduling with Non-Renewable Resources: Minimizing the Sum of Completion Times