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 Plus annual

Presents the access of premium content as premium feature

Premium Content

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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In this paper we consider single machine scheduling problems with additionalnon-renewable resource constraints. Examples for non-renewable resourcesinclude raw materials, energy, or money. Usually they have an initial stock andreplenishments arrive over time at a-priori known time points and quantities.The jobs have some requirements from the resources and a job can only bestarted if the available quantity from each of the required resources exceedsthe requirements of the job. Upon starting a job, it consumes its requirementswhich decreases the available quantities of the respective non-renewableresources. There is a broad theoretical and practical background for this classof problems. Most of the literature concentrate on the makespan, and themaximum lateness objectives. This paper focuses on the total weightedcompletion time objective for which the list of the approximation algorithms isvery short. In this paper we extend that list by considering new special casesand obtain new complexity results and approximation algorithms. We show thateven if there is only a single non-renewable resource, and each job has unitweight and requires only one unit from the resource, the problem is stillNP-hard, however, in our construction we need a high-multiplicity encoding ofthe jobs in the input. We also propose an FPTAS for a variant in which the jobshave arbitrary weights, and the number of supply time points is bounded by aconstant. Finally, we prove some non-trivial approximation guarantees forsimple greedy algorithms for some further variants of the problem.

New complexity and approximability results for minimizing the total  weighted completion time on a single machine subject to non-renewable  resource constraints