@article{ART002120229},
author={Sang-Un, Lee},
title={Polynomial Time Algorithm for Satellite Communications Scheduling Problem with Capacity Constrainted Transponder},
journal={Journal of The Korea Society of Computer and Information},
issn={1598-849X},
year={2016},
volume={21},
number={6},
pages={47-53}
TY - JOUR
AU - Sang-Un, Lee
TI - Polynomial Time Algorithm for Satellite Communications Scheduling Problem with Capacity Constrainted Transponder
JO - Journal of The Korea Society of Computer and Information
PY - 2016
VL - 21
IS - 6
PB - The Korean Society Of Computer And Information
SP - 47
EP - 53
SN - 1598-849X
AB - This paper deals with the capacity constrained time slot assignment problem(CTSAP) that a satellite switches to traffic between × ground stations using on-board ≤ min -transponders switching modes in SS/TDMA time-division technology. There was no polynomial time algorithm to solve the optimal solution thus this problem classified by NP-hard. This paper suggests a heuristic algorithm with time complexity to solve the optimal solution for this problem.
Firstly, the proposed algorithm selects maximum packet lengths of combination and transmits the cut of minimum packet length in each switching mode(MSMC). In the case of last switching mode with inefficient transmission, we applies a compensation strategy to obtain the minimum number of switching modes and the minimum makespan. The proposed algorithm finds optimal solution in polynomial time for all of the experimental data.
KW - Time slot;Makespan;Switch mode;Duration;Capacity constrainted
DO -
UR -
ER -
Sang-Un, Lee. (2016). Polynomial Time Algorithm for Satellite Communications Scheduling Problem with Capacity Constrainted Transponder. Journal of The Korea Society of Computer and Information, 21(6), 47-53.
Sang-Un, Lee. 2016, "Polynomial Time Algorithm for Satellite Communications Scheduling Problem with Capacity Constrainted Transponder", Journal of The Korea Society of Computer and Information, vol.21, no.6 pp.47-53.
Sang-Un, Lee "Polynomial Time Algorithm for Satellite Communications Scheduling Problem with Capacity Constrainted Transponder" Journal of The Korea Society of Computer and Information 21.6 pp.47-53 (2016) : 47.
Sang-Un, Lee. Polynomial Time Algorithm for Satellite Communications Scheduling Problem with Capacity Constrainted Transponder. 2016; 21(6), 47-53.
Sang-Un, Lee. "Polynomial Time Algorithm for Satellite Communications Scheduling Problem with Capacity Constrainted Transponder" Journal of The Korea Society of Computer and Information 21, no.6 (2016) : 47-53.
Sang-Un, Lee. Polynomial Time Algorithm for Satellite Communications Scheduling Problem with Capacity Constrainted Transponder. Journal of The Korea Society of Computer and Information, 21(6), 47-53.
Sang-Un, Lee. Polynomial Time Algorithm for Satellite Communications Scheduling Problem with Capacity Constrainted Transponder. Journal of The Korea Society of Computer and Information. 2016; 21(6) 47-53.
Sang-Un, Lee. Polynomial Time Algorithm for Satellite Communications Scheduling Problem with Capacity Constrainted Transponder. 2016; 21(6), 47-53.
Sang-Un, Lee. "Polynomial Time Algorithm for Satellite Communications Scheduling Problem with Capacity Constrainted Transponder" Journal of The Korea Society of Computer and Information 21, no.6 (2016) : 47-53.
