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

DOI10.1007/S10100-011-0217-4zbMATH Open1339.90155OpenAlexW1984384174MaRDI QIDQ300962FDOQ300962

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

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

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)

Cites Work

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

Cited In (4)

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

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)