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/

Zendy Plus

Presents the zaia usage as premium feature

ZAIA

Presents the pdf analysis as premium feature

PDF Analysis

Insights

Presents the summarisation as premium feature

Summarisation

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the access of premium content as premium feature

Premium Content

Zendy Tools

Zendy Open

In this paper, we provide a new class of randomized approximation algorithms for scheduling problems by directly interpreti ng solutions to so-called time-indexed LPs as probabilities. The most general model we consider is sched- uling unrelated parallel machines with release dates (or ev en network scheduling) so as to minimize the average weighted completion time. The crucial idea for these multiple machine problems is not to use standard list scheduling but rather to assign jobs randomly to machines (with probabilities taken from an optimal LP solution) and to perform list scheduling on each of them. For the general model, we give a 2 ε -approximation algorithm. The best pre- viously known approximation algorithm has a performance guarantee of 16 3 (HSW96). Moreover, our algorithm also improves upon the best previously known approximation algorithms for the special case of identical parallel ma- chine scheduling (performance guarantee 2 89 ε in general (CPS 96) and 2 85 for the average completion time (CMNS97), respectively). A perhaps sur- prising implication for identical parallel machines is tha t jobs are randomly as- signed to machines, in which each machine is equally likely. In addition, in this case the algorithm has running time O nlog n and performance guarantee 2. The same algorithm also is a 2-approximation for the corresponding preemptive scheduling problem on identical parallel machines. Finally, the results for identical parallel machine schedu ling apply to both the off-line and the on-line settings with no difference in perf ormance guarantees. In the on-line setting, we are scheduling jobs that continuall y arrive to be processed and, for each time t, we must construct the schedule until time t without any knowledge of the jobs that will arrive afterwards.

Scheduling-LPs bear probabilities randomized approximations for min-sum criteria