☆ 4.7 Article

An improved approximation algorithm for scheduling monotonic moldable tasks

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH (2023)

Related references

Note: Only part of the references are listed.

Article Engineering, Manufacturing

Approximation algorithms for scheduling monotonic moldable tasks on multiple platforms

Fangfang Wu et al.

Summary: We study the scheduling of monotonic moldable tasks on multiple platforms, each with a set of processors. Moldable tasks can be divided and processed simultaneously on multiple processors. The tasks cannot span over multiple platforms. This scheduling model has various applications such as parallel computing, berth and quay crane allocation, and workforce assignment. We propose several approximation algorithms to minimize the makespan, including a 2-approximation algorithm for identical platforms, a Fully Polynomial Time Approximation Scheme (FPATS) for large processor counts, and a 2-approximation algorithm for a fixed number of heterogeneous platforms. These algorithms combine dual approximation schemes with novel approaches to improve performance. The results can be extended to the contiguous case where tasks require contiguous numbered processors.

JOURNAL OF SCHEDULING (2023)

Add to Collection

Article Computer Science, Artificial Intelligence

An extended formulation of moldable task scheduling problem and its application to quay crane assignments

Ozgur Unsal

Summary: In this paper, an extended formulation of the moldable task scheduling problem (MTSP) inspired by quay crane assignments is studied. A generic solution algorithm based on logic-based Benders decomposition is provided for solving instances of considerable sizes.

EXPERT SYSTEMS WITH APPLICATIONS (2021)

Add to Collection

Article Computer Science, Theory & Methods

Complexity and Inapproximability Results for Parallel Task Scheduling and Strip Packing

Soeren Henning et al.

THEORY OF COMPUTING SYSTEMS (2020)

Add to Collection

Article Management

Minimizing the number of workers in a paced mixed-model assembly line

Xavier Delorme et al.

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH (2019)

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

Article Computer Science, Theory & Methods

Malleable Task-Graph Scheduling with a Practical Speed-Up Model

Loris Marchal et al.

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS (2018)

Add to Collection

Article Computer Science, Theory & Methods

Scheduling Independent Moldable Tasks on Multi-Cores with GPUs

Raphael Bleuse et al.

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS (2017)

Add to Collection

Article Computer Science, Theory & Methods

A 3.42-Approximation Algorithm for Scheduling Malleable Tasks under Precedence Constraints

Chi-Yeh Chen et al.

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS (2013)

Add to Collection

Article Computer Science, Information Systems

A note on the Kenyon-Remila strip-packing algorithm

Maxim Sviridenko

INFORMATION PROCESSING LETTERS (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 Computer Science, Theory & Methods

APPROXIMATION ALGORITHMS FOR SCHEDULING PARALLEL JOBS

Klaus Jansen et al.

SIAM JOURNAL ON COMPUTING (2010)

Add to Collection

Article Operations Research & Management Science

Rectangle packing with one-dimensional resource augmentation

Klaus Jansen et al.

DISCRETE OPTIMIZATION (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 Computer Science, Software Engineering

Scheduling independent multiprocessor tasks

AK Amoura et al.

ALGORITHMICA (2002)

Add to Collection

Article Operations Research & Management Science

A near-optimal solution to a two-dimensional cutting stock problem

C Kenyon et al.

MATHEMATICS OF OPERATIONS RESEARCH (2000)

Add to Collection

© Peeref 2019-2024. All rights reserved.