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

Online makespan minimization is a classic model in the field of scheduling.In this paper, we consider the over-time version, where each job is associatedwith a release time and a processing time. We only know a job after its releasetime and should schedule it on one machine afterward. The Longest ProcessingTime First (LPT) algorithm, as proven by Chen and Vestjens in 1997, achieves acompetitive ratio of 1.5. However, for the case of two machines, Noga andSeiden introduced the SLEEPY algorithm, which achieves a competitive ratio of1.382. Unfortunately, for the case of $m\geq 3$, there has been no convincingresult that surpasses the performance of LPT. we propose a naturalgeneralization that involves locking all the other machines for a certainperiod after starting a job, thereby preventing them from initiating new jobs.We show this simple approach can beat the $1.5$ barrier and achieve$1.482$-competitive when $m=3$. However, when $m$ becomes large, we observethat this simple generalization fails to beat $1.5$. Meanwhile, we introduce anovel technique called dynamic locking to overcome the new challenge. As aresult, we achieve a competitive ratio of $1.5-\frac{1}{O(m^2)}$, which beatsthe LPT algorithm ($1.5$-comeptitive) for every constant $m$.

Online Makespan Minimization: Beat LPT by Dynamic Locking