The Library
An improved approximation algorithm for scheduling monotonic moldable tasks
Tools
Tools
Tools
Wu, Fangfang, Zhang, Xiandong and Chen, Bo (2023) An improved approximation algorithm for scheduling monotonic moldable tasks. European Journal of Operational Research, 306 (2). pp. 567-578. doi:10.1016/j.ejor.2022.08.034 ISSN 0377-2217.
|
PDF
WRAP-An-improved-approximation-algorithm-for-scheduling-monotonic-moldable-tasks-Chen-2022.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (1107Kb) | Preview |
|
![[img]](https://wrap.warwick.ac.uk/style/images/fileicons/application_pdf.png) |
PDF
WRAP-An-improved-approximation-algorithm-for-scheduling-monotonic-moldable-tasks-Chen-2022.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (630Kb) |
Official URL: https://doi.org/10.1016/j.ejor.2022.08.034
Abstract
We are concerned with the problem of scheduling monotonic moldable tasks on identical processors to minimize the makespan. We focus on the natural case where the number m of processors as resources is fixed or relatively small compared with the number n of tasks. We present an efficient (3/2)-approximation algorithm with time complexity O(nm log(nm)) (for m > n) and O(n2 log n) (for m ≤ n). To the best of our knowledge, the best relevant known results are: (a) a (3/2 + e)-approximation algorithm with time complexity O(nm log(n/e)), (b) a fully polynomial-time approximation scheme for the case of m ≥ 16n/e, and (c) a polynomial-time approximation scheme with time complexity O(ng(1/e)) when m is bounded by a polynomial in n, where g(·) is a super-exponential function. On the other hand, the novel general technique developed in this paper for removing the e-term in the worst-case performance ratio can be applied to improving the performance guarantee of certain dual algorithms for other combinatorial optimization problems.
| Item Type: | Journal Article | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
||||||||||||
| Divisions: | Faculty of Social Sciences > Warwick Business School > Operational Research & Management Sciences Faculty of Social Sciences > Warwick Business School |
||||||||||||
| Library of Congress Subject Headings (LCSH): | Approximation algorithms, Monotonic functions, Production scheduling -- Research | ||||||||||||
| Journal or Publication Title: | European Journal of Operational Research | ||||||||||||
| Publisher: | Elsevier Science BV | ||||||||||||
| ISSN: | 0377-2217 | ||||||||||||
| Official Date: | 16 April 2023 | ||||||||||||
| Dates: |
|
||||||||||||
| Volume: | 306 | ||||||||||||
| Number: | 2 | ||||||||||||
| Page Range: | pp. 567-578 | ||||||||||||
| DOI: | 10.1016/j.ejor.2022.08.034 | ||||||||||||
| Status: | Peer Reviewed | ||||||||||||
| Publication Status: | Published | ||||||||||||
| Access rights to Published version: | Open Access (Creative Commons) | ||||||||||||
| Date of first compliant deposit: | 30 August 2022 | ||||||||||||
| Date of first compliant Open Access: | 3 January 2023 | ||||||||||||
| RIOXX Funder/Project Grant: |
|
||||||||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
