Article ID: | iaor20035 |
Country: | United Kingdom |
Volume: | 29 |
Issue: | 13 |
Start Page Number: | 1793 |
End Page Number: | 1806 |
Publication Date: | Nov 2002 |
Journal: | Computers and Operations Research |
Authors: | Kim Sehun, Yeo Jaehyun, Lee Heesoo |
Keywords: | scheduling, heuristics, graphs |
In this paper, we propose an efficient algorithm to find a collision-free time slot schedule in a time division multiple access frame. In order to minimize the system delay, the optimal schedule must be defined as the one that has the minimum frame length and provides the maximum slot utilization. The proposed algorithm is based on the sequential vertex coloring algorithm. Numerical examples and comparisons with the algorithm in previous research have shown that the proposed algorithm can find near-optimal solutions in respect of the system delay.