The longest processing time rule for identical parallel machines revisited

DOI10.1007/s10951-018-0597-6zbMath1436.90048arXiv1801.05489OpenAlexW2963194629WikidataQ128736304 ScholiaQ128736304MaRDI QIDQ2173053

Rosario Scatamacchia, Frederico Della Croce

Publication date: 22 April 2020

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1801.05489

zbMATH Keywords

linear programmingapproximation algorithmsidentical parallel machine schedulingLPT rule

Mathematics Subject Classification ID

Linear programming (90C05) Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)

Related Items (5)

A characterization of optimal multiprocessor schedules and new dominance rules ⋮ The LPT heuristic for minimizing total load on a proportionate openshop ⋮ An improved algorithm for a two-stage production scheduling problem with an outsourcing option ⋮ Tight approximation bounds for the LPT rule applied to identical parallel machines with small jobs ⋮ Iterated greedy algorithms for a complex parallel machine scheduling problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Performance ratios of the Karmarkar-Karp differencing method
• Partial solutions and multifit algorithm for multiprocessor scheduling
• Multiprocessor scheduling: Combining LPT and MULTIFIT
• Approximation schemes for scheduling on parallel machines
• A composite heuristic for the identical parallel machine scheduling problem with minimum makespan objective
• Approximation results for the incremental knapsack problem
• A multi-exchange neighborhood for minimum makespan parallel machine scheduling problems
• A note on the Coffman-Sethi bound for LPT scheduling
• Worst-case analysis of the differencing method for the partition problem
• The Asymptotic Optimality of the LPT Rule
• An Application of Bin-Packing to Multiprocessor Scheduling
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• A Parametric Worst Case Analysis of the LPT Heuristic for Two Uniform Machines
• Beating ratio 0.5 for weighted oblivious matching problems
• An ILP-based Proof System for the Crossing Number Problem
• Scatter Search Algorithms for Identical Parallel Machine Scheduling Problems
• An EPTAS for Scheduling Jobs on Uniform Processors: Using an MILP Relaxation with a Constant Number of Integral Variables
• Bounds on Multiprocessing Timing Anomalies
• Scheduling
• A note on LPT scheduling

This page was built for publication: The longest processing time rule for identical parallel machines revisited