Comparing the minimum completion times of two longest-first scheduling-heuristics

DOI10.1007/S10100-011-0217-4MaRDI QIDQ300962zbMATH OpenOpenAlexFDO

Authors Rico Walter

Publication date 29 June 2016

Published in CEJOR. Central European Journal of Operations Research (Search for Journal in Brave)

Full work available at URL https://www.db-thueringen.de/servlets/MCRFileNodeServlet/dbt_derivate_00022406/wp-jbe201013-1.pdf

zbMATH Keywords

heuristicsschedulingworst-case analysisidentical parallel machinesminimum completion time

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Case-oriented studies in operations research (90B90)

Recommendations

• The longest processing time rule for identical parallel machines revisited
• Performance of the LPT algorithm in multiprocessor scheduling
• A note on LPT scheduling
• The exact LPT-bound for maximizing the minimum completion time
• Parallel machines scheduling with nonsimultaneous machine available time

Cites work

• A performance guarantee for the greedy set-partitioning algorithm
• A polynomial-time approximation scheme for maximizing the minimum machine completion time
• Algorithms minimizing mean flow time: Schedule-length properties
• Analysis of Greedy Solutions for a Replacement Part Sequencing Problem
• Asymptotic Analysis of an Algorithm for Balanced Parallel Processor Scheduling
• Maximizing the minimum completion time on parallel machines
• On-line machine covering
• Ordinal on-line scheduling for maximizing the minimum machine completion time
• Scheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor System
• The exact LPT-bound for maximizing the minimum completion time

Cited in

(4)

• A fast and effective subset sum based improvement procedure for workload balancing on identical parallel machines
• Improved approaches to the exact solution of the machine covering problem
• Reducing ergonomic risks by job rotation scheduling
• Scheduling with tool changes to minimize total completion time: A study of heuristics and their performance

This page was built for publication: Comparing the minimum completion times of two longest-first scheduling-heuristics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q300962)