KJCKorea
Journal Central

@article{ART002050542},
author={Sang-Un, Lee},
title={A Heuristic Polynomial Time Algorithm for Crew Scheduling Problem},
journal={Journal of The Korea Society of Computer and Information},
issn={1598-849X},
year={2015},
volume={20},
number={11},
pages={69-75}

TY - JOUR
AU - Sang-Un, Lee
TI - A Heuristic Polynomial Time Algorithm for Crew Scheduling Problem
JO - Journal of The Korea Society of Computer and Information
PY - 2015
VL - 20
IS - 11
PB - The Korean Society Of Computer And Information
SP - 69
EP - 75
SN - 1598-849X
AB - This paper suggests heuristic polynomial time algorithm for crew scheduling problem that is a kind of optimization problems. This problem has been solved by linear programming, set cover problem, set partition problem, column generation, etc. But the optimal solution has not been obtained by these methods. This paper sorts transit costs cij to ascending order, and the task i and j crew paths are merged in case of the sum of operation time ∑0 is less than day working time T . As a result, we can be obtain the minimum number of crews min K and minimum transit cost z= mincij . For the transit cost of specific number of crews K(K>minK) , we delete the maximum cij as much as the number of K- minK , and to partition a crew path. For the 5 benchmark data, this algorithm can be gets less transit cost than state-of-the-art algorithms, and gets the minimum number of crews.
KW - Tasks;Crews;Transit cost;Ascending sort;Path merge and partition
DO -
UR -
ER -

Sang-Un, Lee. (2015). A Heuristic Polynomial Time Algorithm for Crew Scheduling Problem. Journal of The Korea Society of Computer and Information, 20(11), 69-75.

Sang-Un, Lee. 2015, "A Heuristic Polynomial Time Algorithm for Crew Scheduling Problem", Journal of The Korea Society of Computer and Information, vol.20, no.11 pp.69-75.

Sang-Un, Lee "A Heuristic Polynomial Time Algorithm for Crew Scheduling Problem" Journal of The Korea Society of Computer and Information 20.11 pp.69-75 (2015) : 69.

Sang-Un, Lee. A Heuristic Polynomial Time Algorithm for Crew Scheduling Problem. 2015; 20(11), 69-75.

Sang-Un, Lee. "A Heuristic Polynomial Time Algorithm for Crew Scheduling Problem" Journal of The Korea Society of Computer and Information 20, no.11 (2015) : 69-75.

Sang-Un, Lee. A Heuristic Polynomial Time Algorithm for Crew Scheduling Problem. Journal of The Korea Society of Computer and Information, 20(11), 69-75.

Sang-Un, Lee. A Heuristic Polynomial Time Algorithm for Crew Scheduling Problem. Journal of The Korea Society of Computer and Information. 2015; 20(11) 69-75.

Sang-Un, Lee. A Heuristic Polynomial Time Algorithm for Crew Scheduling Problem. 2015; 20(11), 69-75.

Sang-Un, Lee. "A Heuristic Polynomial Time Algorithm for Crew Scheduling Problem" Journal of The Korea Society of Computer and Information 20, no.11 (2015) : 69-75.