Uniform machine scheduling with machine available constraints |
| |
Authors: | HE Yong |
| |
Institution: | (1) Department of Mathematics, Zhejiang University, 310027 Hangzhou |
| |
Abstract: | In this paper, we consider a uniform machine scheduling problem with nonsimultaneous available times. We prove that LPT algorithm has a worst case bound in the interval (1.52,5/3). We tighten this bound when the machine speed ratio is small or m=2. Furthermore, we present a linear compound algorithm QLC with a worst case bound of 6/5 for a two-machine system. |
| |
Keywords: | Uniform machine scheduling heuristic worst case analysis |
本文献已被 CNKI SpringerLink 等数据库收录! |