Approximation for scheduling on uniform nonsimultaneous parallel machines
| Autor: | Liliana Grigoriu, Donald K. Friesen |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Mathematical optimization
021103 operations research Job shop scheduling General problem 0211 other engineering and technologies General Engineering 0102 computer and information sciences 02 engineering and technology Management Science and Operations Research 01 natural sciences Multiprocessor scheduling Scheduling (computing) 010201 computation theory & mathematics Artificial Intelligence Completion time Software Mathematics |
| Zdroj: | Journal of Scheduling. 20:593-600 |
| ISSN: | 1099-1425 1094-6136 |
| DOI: | 10.1007/s10951-016-0501-1 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink