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

We consider variants of the restricted assignment problem where a set of jobshas to be assigned to a set of machines, for each job a size and a set ofeligible machines is given, and the jobs may only be assigned to eligiblemachines with the goal of makespan minimization. For the variant with intervalrestrictions, where the machines can be arranged on a path such that each jobis eligible on a subpath, we present the first better than $2$-approximationand an improved inapproximability result. In particular, we give a$(2-\frac{1}{24})$-approximation and show that no better than$9/8$-approximation is possible, unless P=NP. Furthermore, we considerrestricted assignment with $R$ resource restrictions and rank $D$ unrelatedscheduling. In the former problem, a machine may process a job if it can meetits resource requirements regarding $R$ (renewable) resources. In the latter,the size of a job is dependent on the machine it is assigned to and thecorresponding processing time matrix has rank at most $D$. The problem withinterval restrictions includes the 1 resource variant, is encompassed by the 2resource variant, and regarding approximation the $R$ resource variant isessentially a special case of the rank $R+1$ problem. We show that no betterthan $3/2$, $8/7$, and $3/2$-approximation is possible (unless P=NP) for the 3resource, 2 resource, and rank 3 variant, respectively. Both the approximationresult for the interval case and the inapproximability result for the rank 3variant are solutions to open challenges stated in previous works. Lastly, wealso consider the reverse objective, that is, maximizing the minimal load anymachine receives, and achieve similar results.

(In-)Approximability Results for Interval, Resource Restricted, and Low Rank Scheduling