Multiprocessor scheduling: Combining LPT and MULTIFIT
The paper considers the problem of scheduling a set of n independent jobs on m identical machines with the objective of minimizing the total finishing time. Two well-known heuristic algorithms, namely LPT and MULTIFIT, are reviewed with respect to their advantages and drawbacks. A new algorithm called COMBINE is proposed which uses the result of LPT as the incumbent and then applies MULTIFIT with fewer iterations. The performance of the proposed new algorithm is better than that of LPT becauses it uses LPT as an incumbent. Furthermore, it is shown that the error bound of the new algorithm is never worse than that of MULTIFIT. Although it is not known for the general multiprocessor problem how much improvement is obtained in the error bound for COMBINE over MULTIFIT, it is shown that the improvement is significant for the two-processor system. Empirical comparison results are finally provided.
- An Application of Bin-Packing to Multiprocessor Scheduling
- Bounds for Certain Multiprocessing Anomalies
- Bounds on Multiprocessing Timing Anomalies
- Evaluation of a MULTIFIT-based scheduling algorithm
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Tighter Bounds for the Multifit Processor Scheduling Algorithm
- A general lower bound for the makespan problem
- Minimizing makespan subject to minimum total flow-time on identical parallel machines
- Minimizing the makespan on two identical parallel machines with mold constraints
- Scheduling identical parallel machines with tooling constraints
- A new heuristic for workload balancing on identical parallel machines and a statistical perspective on the workload balancing criteria
- Tight approximation bounds for the LPT rule applied to identical parallel machines with small jobs
- The multiple traveling salesman problem in presence of drone- and robot-supported packet stations
- The longest processing time rule for identical parallel machines revisited
- A note on minimizing the sum of squares of machine completion times on two identical parallel machines
- A note on posterior tight worst-case bounds for longest processing time schedules
- A tight linear time \(\frac{13}{12}\)-approximation algorithm for the \(P2 || C_{\max}\) problem
- Machine scheduling performance with maintenance and failure
- The partitioning min-max weighted matching problem
- Heuristic scheduling of parallel machines with sequence-dependent set-up times
- scientific article; zbMATH DE number 1559404 (Why is no real title available?)
- Loading and scheduling for flexible manufacturing systems with controllable processing times
- Performance of the LPT algorithm in multiprocessor scheduling
- The LPT heuristic for minimizing total load on a proportionate openshop
- Update on the asymptotic optimality of LPT
- An update on the asymptotic optimality of the longest processing time heuristic
- Parallel machines scheduling with nonsimultaneous machine available time
- Scheduling with flexible resources in parallel workcenters to minimize maximum completion time
- Partial solutions and multifit algorithm for multiprocessor scheduling
This page was built for publication: Multiprocessor scheduling: Combining LPT and MULTIFIT
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1109673)
