Minimum Message Waiting Time Scheduling in Distributed Systems
| Autor: | Francesca Martelli, Maurizio A. Bonuccelli |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2013 |
| Předmět: |
Waiting time
Mathematical optimization Schedule Linear programming Computer science packet scheduling Distributed computing heuristics NP-completeness Scheduling (computing) Computational Theory and Mathematics Hardware and Architecture Signal Processing minimum message waiting time Heuristics Communication complexity Polynomial-time reduction |
| Zdroj: | IEEE transactions on parallel and distributed systems 99 (2012): 1–7. doi:10.1109/TPDS.2012.284 info:cnr-pdr/source/autori:Martelli Francesca, Bonuccelli Maurizio Angelo/titolo:Minimum Message Waiting Time Scheduling in Distributed Systems/doi:10.1109%2FTPDS.2012.284/rivista:IEEE transactions on parallel and distributed systems (Print)/anno:2012/pagina_da:1/pagina_a:7/intervallo_pagine:1–7/volume:99 |
| DOI: | 10.1109/TPDS.2012.284 |
| Popis: | In this paper, we examine the problem of packet scheduling in a single-hop multichannel system, with the goal of minimizing the average message waiting time. Such an objective function represents the delay incurred by the users before receiving the desired data. We show that the problem of finding a schedule with minimum message waiting time, is NP-complete, by means of polynomial time reduction of the time table design problem to our problem. We present also several heuristics which result in outcomes very close to the optimal ones. We compare these heuristics by means of extensive simulations. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|