☆ 4.3 Article

Approximation algorithms for scheduling monotonic moldable tasks on multiple platforms

JOURNAL OF SCHEDULING (2023)

Related references

Note: Only part of the references are listed.

Article Management

An improved approximation algorithm for scheduling monotonic moldable tasks

Fangfang Wu et al.

Summary: We propose an efficient (3/2)-approximation algorithm for scheduling monotonic moldable tasks on identical processors. The algorithm has a time complexity of O(nmlog(nm)) (for m > n) and O(n(2) log n) (for m <= n). The best known results include a (3/2 + epsilon)-approximation algorithm with a time complexity of O(nm log(n/epsilon)), a fully polynomial-time approximation scheme for m >= 16n/epsilon, and a polynomial-time approximation scheme with a time complexity of O(n(g(1/epsilon))) for bounded m. Additionally, the paper introduces a novel general technique for improving the performance guarantee of certain dual algorithms for other combinatorial optimization problems.

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH (2023)

Add to Collection

Article Management

Optimal workforce assignment to operations of a paced assembly line

Alexandre Dolgui et al.

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH (2018)

Add to Collection

Proceedings Paper Computer Science, Hardware & Architecture

Scheduling Monotone Moldable Jobs in Linear Time

Klaus Jansen et al.

2018 32ND IEEE INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM (IPDPS) (2018)

Add to Collection

Article Computer Science, Theory & Methods

Improved approximation algorithms for scheduling parallel jobs on identical clusters

Marin Bougeret et al.

THEORETICAL COMPUTER SCIENCE (2015)

Add to Collection

Proceedings Paper Computer Science, Theory & Methods

Tight approximation for scheduling parallel jobs on identical clusters

Marin Bougeret et al.

2012 IEEE 26TH INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM WORKSHOPS & PHD FORUM (IPDPSW) (2012)

Add to Collection

Article Management

Berth and quay crane allocation: a moldable task scheduling model

J. Blazewicz et al.

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY (2011)

Add to Collection

Article Mathematics, Applied

APPROXIMATION ALGORITHMS FOR MULTIPLE STRIP PACKING AND SCHEDULING PARALLEL JOBS IN PLATFORMS

Marin Bougeret et al.

DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS (2011)

Add to Collection

Article Computer Science, Theory & Methods

APPROXIMATION ALGORITHMS FOR SCHEDULING PARALLEL JOBS

Klaus Jansen et al.

SIAM JOURNAL ON COMPUTING (2010)

Add to Collection

Article Computer Science, Software Engineering

Cooperation in multi-organization scheduling

Fanny Pascual et al.

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE (2009)

Add to Collection

Article Computer Science, Theory & Methods

A 3/2-approximation algorithm for scheduling independent monotonic malleable tasks

Gregory Mounie et al.

SIAM JOURNAL ON COMPUTING (2007)

Add to Collection

Article Engineering, Manufacturing

Scheduling parallel jobs to minimize the makespan

Berit Johannes

JOURNAL OF SCHEDULING (2006)

Add to Collection

Article Mathematics, Applied

The multiple subset sum problem

A Caprara et al.

SIAM JOURNAL ON OPTIMIZATION (2000)

Add to Collection

© Peeref 2019-2024. All rights reserved.