Approximation for scheduling on uniform nonsimultaneous parallel machines |
| |
Authors: | Liliana Grigoriu Donald K Friesen |
| |
Affiliation: | 1.Fakult?t für Wirtschaftswissenschaften, Wirtschaftsinformatik und Wirtschaftsrecht, Universit?t Siegen,Siegen,Germany;2.Department of Computer Science,Texas A&M University,College Station,USA |
| |
Abstract: | We consider the problem of scheduling on uniform machines which may not start processing at the same time with the purpose of minimizing the maximum completion time. We propose using a variant of the MULTIFIT algorithm, LMULTIFIT, which generates schedules which end within 1.382 times the optimal maximum completion time for the general problem, and within \(\sqrt{6}/2\) times the optimal maximum completion time for problem instances with two machines. Both developments represent improvements over previous results. We prove that LMULTIFIT worst-case bounds for scheduling on simultaneous uniform machines are also LMULTIFIT worst-case approximation bounds for scheduling on nonsimultaneous uniform machines and show that worst-case approximation bounds of MULTIFIT variants for simultaneous uniform machines from previous literature also apply to LMULTIFIT. We also comment on how a PTAS for scheduling on a constant number of uniform machines with fixed jobs can be used to obtain a PTAS for scheduling on a constant number of uniform nonsimultaneous parallel machines. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|