The worst-case analysis of the MULTIFIT algorithm for scheduling nonsimultaneous parallel machines

DOI10.1016/S0166-218X(99)00049-9zbMath0931.68017WikidataQ127883981 ScholiaQ127883981MaRDI QIDQ1304470

Hark-Chin Hwang, Soo Y. Chang

Publication date: 7 February 2000

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

nonsimultaneous multiprocessor scheduling problem

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items

Worst-case performance analysis of some approximation algorithms for minimizing makespan and flowtime ⋮ Scheduling on same-speed processors with at most one downtime on each machine ⋮ Scheduling with job rejection and nonsimultaneous machine available time on unrelated parallel machines ⋮ Approximation for scheduling on uniform nonsimultaneous parallel machines ⋮ Exact performance of MULTIFIT for nonsimultaneous machines ⋮ Scheduling on uniform processors with at most one downtime on each machine ⋮ The effect of machine availability on the worst-case performance of LPT ⋮ The multifit algorithm for set partitioning containing kernels ⋮ Optimal online algorithm for scheduling on two identical machines with machine availability constraints.

Cites Work

• Unnamed Item
• Parallel machines scheduling with nonsimultaneous machine available time
• An Application of Bin-Packing to Multiprocessor Scheduling
• Bounds on Multiprocessing Timing Anomalies