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

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Part 1: Track A: Algorithms, Complexity and Models of ComputationInternational audienceWe consider the online scheduling of unit length jobs with two models of commitment. In immediate notification, the acceptance of a job must be decided as soon as it is released. In immediate decision, the actual time slot allocated to the job must also be fixed at the job’s arrival as well. Failure to honour a commitment will result in a penalty. The non-commitment version has been extensively studied. In this paper we give algorithms and lower bounds for the two models of commitment. For immediate decision, we give an O(m(1 + ρ)1/m)-competitive algorithm where m is the number of machines and ρ is the penalty factor, and when m is large we give an O(log(1 + ρ)) upper bound. This is matched by a lower bound of Ω(logρ) on the competitive ratio. For immediate notification we give a lower bound of Ω(logρ/loglogρ). We also give some better bounds when m = 1 or when ρ is small. Finally we give considerations to the case of separate arrival and start times

Online Scheduling of Unit Length Jobs with Commitment and Penalties