@article{ART001929554},
author={Sang-Un, Lee},
title={Swap-Insert Algorithm for Driver Scheduling Problem},
journal={Journal of The Korea Society of Computer and Information},
issn={1598-849X},
year={2014},
volume={19},
number={11},
pages={175-181}
TY - JOUR
AU - Sang-Un, Lee
TI - Swap-Insert Algorithm for Driver Scheduling Problem
JO - Journal of The Korea Society of Computer and Information
PY - 2014
VL - 19
IS - 11
PB - The Korean Society Of Computer And Information
SP - 175
EP - 181
SN - 1598-849X
AB - This paper suggests O(ｍ) polynomial time heuristic algorithm to obtain the solution for the driverscheduling problem, DSP, that has been classified as NP-complete problem. The proposed algorithm getsthe initial assignment of ｎ minimum number of drivers from given ｍ schedules. Nextly, this algorithmgets the minimum total time (TC) using 5 rules of swap and insert for decrease of over times (OT) and idletimes (IT). Although this algorithm is a heuristic polynomial time algorithm with O(ｍ)time complexityrules to be find a optimal (or approximate) solution, this algorithm is equal to metaheuristic methods forthe 5 experimental data. To conclude, this paper shows the DSP is not NP-complete problem butPolynomial time (P)-problem with polynomial time rules.
KW - Driver scheduling problem;Parallelogram;Swap;Insert;Idle time
DO -
UR -
ER -
Sang-Un, Lee. (2014). Swap-Insert Algorithm for Driver Scheduling Problem. Journal of The Korea Society of Computer and Information, 19(11), 175-181.
Sang-Un, Lee. 2014, "Swap-Insert Algorithm for Driver Scheduling Problem", Journal of The Korea Society of Computer and Information, vol.19, no.11 pp.175-181.
Sang-Un, Lee "Swap-Insert Algorithm for Driver Scheduling Problem" Journal of The Korea Society of Computer and Information 19.11 pp.175-181 (2014) : 175.
Sang-Un, Lee. Swap-Insert Algorithm for Driver Scheduling Problem. 2014; 19(11), 175-181.
Sang-Un, Lee. "Swap-Insert Algorithm for Driver Scheduling Problem" Journal of The Korea Society of Computer and Information 19, no.11 (2014) : 175-181.
Sang-Un, Lee. Swap-Insert Algorithm for Driver Scheduling Problem. Journal of The Korea Society of Computer and Information, 19(11), 175-181.
Sang-Un, Lee. Swap-Insert Algorithm for Driver Scheduling Problem. Journal of The Korea Society of Computer and Information. 2014; 19(11) 175-181.
Sang-Un, Lee. Swap-Insert Algorithm for Driver Scheduling Problem. 2014; 19(11), 175-181.
Sang-Un, Lee. "Swap-Insert Algorithm for Driver Scheduling Problem" Journal of The Korea Society of Computer and Information 19, no.11 (2014) : 175-181.
