Multiprocessor scheduling: Combining LPT and MULTIFIT
From MaRDI portal
Publication:1109673
DOI10.1016/0166-218X(88)90079-0zbMath0655.90036WikidataQ127352600 ScholiaQ127352600MaRDI QIDQ1109673
Chung-Yee Lee, J. David Massey
Publication date: 1988
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
multiprocessor schedulingerror boundheuristic algorithmscomparison of algorithmsidentical machinesimprovementindependent jobstotal finishing time
Numerical mathematical programming methods (65K05) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)
Related Items
A note on minimizing the sum of squares of machine completion times on two identical parallel machines ⋮ Loading and scheduling for flexible manufacturing systems with controllable processing times ⋮ The partitioning min-max weighted matching problem ⋮ Scheduling with flexible resources in parallel workcenters to minimize maximum completion time ⋮ Machine scheduling performance with maintenance and failure ⋮ The longest processing time rule for identical parallel machines revisited ⋮ Partial solutions and multifit algorithm for multiprocessor scheduling ⋮ A note on posterior tight worst-case bounds for longest processing time schedules ⋮ The LPT heuristic for minimizing total load on a proportionate openshop ⋮ A tight linear time \(\frac{13}{12}\)-approximation algorithm for the \(P2 || C_{\max}\) problem ⋮ Minimizing the makespan on two identical parallel machines with mold constraints ⋮ Unnamed Item ⋮ 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 ⋮ Performance of the LPT algorithm in multiprocessor scheduling ⋮ Heuristic scheduling of parallel machines with sequence-dependent set-up times ⋮ A general lower bound for the makespan problem ⋮ Parallel machines scheduling with nonsimultaneous machine available time ⋮ Minimizing makespan subject to minimum total flow-time on identical parallel machines ⋮ 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
Cites Work
