Scheduling Service Staffs for Alien Airlines Using Block Gibbs Sampling

Min LU; Li WANG; Ling TANG

doi:10.11999/JEIT180181

Volume 40 Issue 10

Sep. 2018

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2018 > 40(10): 2513-2520

Min LU, Li WANG, Ling TANG. Scheduling Service Staffs for Alien Airlines Using Block Gibbs Sampling[J]. Journal of Electronics & Information Technology, 2018, 40(10): 2513-2520. doi: 10.11999/JEIT180181

Citation:

Min LU, Li WANG, Ling TANG. Scheduling Service Staffs for Alien Airlines Using Block Gibbs Sampling[J]. Journal of Electronics & Information Technology, 2018, 40(10): 2513-2520. doi: 10.11999/JEIT180181

Citation:

PDF( 761 KB)

Scheduling Service Staffs for Alien Airlines Using Block Gibbs Sampling

doi: 10.11999/JEIT180181

Min LU^{1, 2, 3, 4
,
,},
Li WANG^{1, 3},
Ling TANG^{1, 3}

1.
College of Computer Science and Technology, Civil Aviation University of China, Tianjin 300300, China
2.
Key Laboratory of Machine Intelligence and Advanced Computing, Sun Yat-sen University, Guangzhou 510275, China
3.
Information Technology Research Base of CAAC, Civil Aviation University of China, Tianjin 300300, China
4.
Key Laboratory of Intelligent Application Technology for Civil Aviation Passenger Services, Tianjin 300300, China

Funds: The National Natural Science Foundation of China (61502499), The Civil Aviation Key Technologies R&D Program of China (MHRD20140105), The Open Project in Key Laboratory of Machine Intelligence and Advanced Computing of the Ministry of Education (Sun Yat-sen University) (MSC-201704A), The Fundamental Research Funds for the Central Universities of China (3122013C005), The Project from Key Laboratory of Intelligent Application Technology for Civil Aviation Passenger Services

Received Date: 2018-02-09
Rev Recd Date: 2018-07-05

Available Online: 2018-07-27

Publish Date: 2018-10-01

Abstract

Abstract

Scheduling staffs servicing alien airlines aims to yield task-person assignments by covering the required skills and minimizing employee total working hours as well as balancing staffs’ workload. Its essence is a personnel scheduling problem constrained by multiple task types, hierarchical skills as well as day and night alternation. The existing algorithms do not consider the constraint of day and night alternation. An algorithm is proposed to address that issue. The proposed algorithm firstly designs a data copy trick to quickly model the issue of staff scheduling constrained by day and night alternation. A novel Block Gibbs sampling technique with replacement is designed to efficiently optimize the formulated problem. Theoretical analysis indicates that the computational complexity of the proposed algorithm is the same scale to that of the baselines, whereas the proposed algorithm gains high sampling efficiency. Experimental results on a real dataset shows the improvement of the proposed algorithm over the existing methods is at least 0.62% in terms of evaluation measures.
- Aircraft ground handling,
- Staff scheduling,
- Block Gibbs sampling,
- Hierarchical skill

FullText(HTML)

References(15)

References

BERGH J, BELIËN J, and BRUECKER P. Personnel scheduling: A literature review[J].European Journal of Operational Research, 2013, 226(3): 367–385 doi: 10.1016/j.ejor.2012.11.029

ERNST A T, JIANG H, and KRISHNAMOORTHY M. Staff scheduling and rostering: A review of applications, methods and models[J]. European Journal of Operational Research, 2004, 153(1): 3–27 doi: 10.1016/S0377-2217(03)00095-X

KHOSRAVI A K, TAMANNAEI T, and REISI-NAFCHI M. A comprehensive approach for railway crew scheduling problem[J]. International Journal of Transportation Engineering, 2017, 4(3): 197–210 doi: 10.22119/IJTE.2017.43836

RAHIMIAN E, AKARTUNALI K, and LEVINE J. A hybrid integer and constraint programming approach to solve nurse rostering problems[J]. Computers&Operations Research, 2017, 82: 83–94 doi: 10.1016/j.cor.2017.01.016

FUJITA K, MURAKAMI K, and AMASAKA K. A shift scheduling model introducing non-regular employees for hotel restaurants[J]. Journal of Japanese Operations Management and Strategy, 2016, 6(1): 17–33 doi: 10.20586/joms.6.1_17

BRUECKER P D and BURKE E. Personnel scheduling: Models and complexity[J]. European Journal of Operational Research, 2011, 210(3): 467–473 doi: 10.1016/j.ejor.2010.11.017

RESTREPO M I, ENDRON B, and ROUSSAUB M. A two-stage stochastic programming approach for multi-activity tour scheduling[J]. European Journal of Operational Research, 2017, 262(2): 620–635 doi: 10.1016/j.ejor.2017.04.055

WALTER M and ZIMMERMANN J. Minimizing average project team size given multi-skilled workers with heterogeneous skill levels[J]. Computers&Operations Research, 2016, 70: 163–179 doi: 10.1016/j.cor.2015.11.011

BRUECKER P, BERGH J, BELIËN J, et al. Workforce planning incorporating skills: state of the art[J]. European Journal of Operational Research, 2015, 243(1): 1–16 doi: 10.1016/j.ejor.2014.10.038

FIRAT M, BRISKORN D, and LAUGIER A. A Branch-and-Price algorithm for stable workforce assignments with hierarchical skills[J]. European Journal of Operational Research, 2016, 251(2): 676–685 doi: 10.1016/j.ejor.2015.11.039

SMET P, BILGINL B, DE CAUSMAECKER P, et al. Modelling and evaluation issues in nurse rostering[J]. Annals of Operations Research, 2014, 218(1): 303–326 doi: 10.1007/s10479-012-1116-3

SCIPIONE D, SULLIVAN F, ZAVADSKY V, et al. Optimizing staff scheduling by Monte-Carlo simulation[C]. Proceedings of the Annual Symposium on Computer Application in Medical Care, Washington D.C, USA, 1992: 678–681.

CHENG C C, CARVE N, and RAHIMI S. Constraint based staff scheduling optimization: Using single player Monte Carlo tree search[C]. Proceedings of the 16th International Conference on Artificial Intelligence, Las Vegas, USA, 2014: 633–638.

ZULCH G, ROTTINGER S, and VOLLSTED T. A simulation approach for planning and re-assigning of personnel in manufacturing[J]. International Journal of Production Economics, 2004, 90(2): 265–277 doi: 10.1016/j.ijpe.2003.11.008

GÉRARD M, CLAUTIAUX F, and SADYKOV R. Column generation based approaches for a tour scheduling problem with a multi-skill heterogeneous workforce[J]. European Journal of Operational Research, 2016, 252(3): 1019–1030 doi: 10.1016/j.ejor.2016.01.036

Relative Articles

Supplements(0)

Cited By

Proportional views