A branch-and-cut algorithm framework for the integrated aircraft hangar maintenance scheduling and staffing problem

Yichen Qin, Felix T.S. Chan, S. H. Chung, T. Qu

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review


The problem of maintenance scheduling and staffing at an aircraft heavy maintenance service company is studied. The objective is to establish an integrated aircraft maintenance schedule and maintenance technicians’ rosters to fulfil different maintenance requests while minimizing the overall tardiness cost and labor cost. Upon receiving the maintenance requests, the hangar planner has to determine if the maintenance company is capable to serve the aircraft within the planning period, then allocate the parking stands and staying time of each aircraft in the hangar for the subsequent maintenance operations. Due to the complexity of the combinatorial problem, the commercial solver using branch-and-bound algorithm is incapable to tackle with the medium-sized instance within reasonable time. To enhance the computational efficiency, a framework of branch-and-cut algorithm is proposed in this paper, aiming to decompose the original model and tighten the lower bound of the original problem by the effective cuts. The concept of combinatorial benders’ decomposition algorithm is adopted in the development of algorithm.

Original languageEnglish
Title of host publicationACM International Conference Proceeding Series
PublisherAssociation for Computing Machinery
Number of pages4
ISBN (Print)9781450361033
Publication statusPublished - 1 Mar 2019
Event2nd International Conference on Information Science and System, ICISS 2019 - Tokyo, Japan
Duration: 16 Mar 201919 Mar 2019

Publication series

NameACM International Conference Proceeding Series
VolumePart F148384


Conference2nd International Conference on Information Science and System, ICISS 2019


  • Aircraft hangar maintenance
  • Branch-and-cut algorithm
  • Hangar layout planning
  • Workforce scheduling

ASJC Scopus subject areas

  • Software
  • Human-Computer Interaction
  • Computer Vision and Pattern Recognition
  • Computer Networks and Communications

Cite this