The longest processing time rule for identical parallel machines revisited
From MaRDI portal
(Redirected from Publication:2173053)
Abstract: We consider the Pm || Cmax scheduling problem where the goal is to schedule n jobs on m identical parallel machines to minimize makespan. We revisit the famous Longest Processing Time (LPT) rule proposed by Graham in 1969. LPT requires to sort jobs in non-ascending order of processing times and then to assign one job at a time to the machine whose load is smallest so far. We provide new insights on LPT and discuss the approximation ratio of a modification of LPT that improves Graham's bound from 4/3 - 1/(3m) to 4/3 - 1/(3(m-1)) for m >= 3 and from 7/6 to 9/8 for m = 2. We use Linear Programming (LP) to analyze the approximation ratio of our approach. This performance analysis can be seen as a valid alternative to formal proofs based on analytical derivation. Also, we derive from the proposed approach an O(n log n) heuristic. The heuristic splits the sorted jobset in tuples of m consecutive jobs (1,...,m; m+1,...,2m; etc.) and sorts the tuples in non-increasing order of the difference (slack) between largest job and smallest job in the tuple. Then, List Scheduling is applied to the set of sorted tuples. This approach strongly outperforms LPT on benchmark literature instances.
Recommendations
- Tight approximation bounds for the LPT rule applied to identical parallel machines with small jobs
- Performance of the LPT algorithm in multiprocessor scheduling
- New approximation bounds for LPT scheduling
- A note on LPT scheduling
- Parallel machines scheduling with nonsimultaneous machine available time
Cites work
- A composite heuristic for the identical parallel machine scheduling problem with minimum makespan objective
- A multi-exchange neighborhood for minimum makespan parallel machine scheduling problems
- A note on LPT scheduling
- A note on the Coffman-Sethi bound for LPT scheduling
- A Parametric Worst Case Analysis of the LPT Heuristic for Two Uniform Machines
- An Application of Bin-Packing to Multiprocessor Scheduling
- An EPTAS for scheduling jobs on uniform processors: using an MILP relaxation with a constant number of integral variables
- An ILP-based Proof System for the Crossing Number Problem
- Approximation results for the incremental knapsack problem
- Approximation schemes for scheduling on parallel machines
- Beating ratio 0.5 for weighted oblivious matching problems
- Bounds on Multiprocessing Timing Anomalies
- Graham's example is the only tight one for \(P \parallel C_{max}\)
- scientific article; zbMATH DE number 3521517 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1559404 (Why is no real title available?)
- scientific article; zbMATH DE number 2109192 (Why is no real title available?)
- Multiprocessor scheduling: Combining LPT and MULTIFIT
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- Partial solutions and multifit algorithm for multiprocessor scheduling
- Performance ratios of the Karmarkar-Karp differencing method
- Scatter Search Algorithms for Identical Parallel Machine Scheduling Problems
- Scheduling. Theory, algorithms, and systems
- The Asymptotic Optimality of the LPT Rule
- The general algorithm \(\text{LPT}(k)\) for scheduling identical parallel machines
- Worst-case analysis of the differencing method for the partition problem
Cited in
(13)- 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
- A modified LPT algorithm for the two uniform parallel machine makespan minimization problem
- Comparing the minimum completion times of two longest-first scheduling-heuristics
- Graham's example is the only tight one for \(P \parallel C_{max}\)
- The Asymptotic Optimality of the LPT Rule
- The LPT heuristic for minimizing total load on a proportionate openshop
- Update on the asymptotic optimality of LPT
- Automated placement of analog integrated circuits using priority-based constructive heuristic
- Fifty years of research in scheduling -- theory and applications
- An update on the asymptotic optimality of the longest processing time heuristic
- A characterization of optimal multiprocessor schedules and new dominance rules
This page was built for publication: The longest processing time rule for identical parallel machines revisited
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2173053)
