关键词: 任务部分覆盖率, NP-hard问题, 整数规划模型, CPLEX优化软件

Abstract: Airport ground service plays an important role in ensuring the safe landing and normal operation of aircraft. The airport has a large number of tasks waiting to be assigned to a limited number of shifts each day, and a task represents a service, which must be performed by one or multiple ground crew of a shift with required qualification/proficiency within a prescribed time period. Qualifications may be language requirements or proficiency in an airline's registration system, and once a qualification requirement is in place, the corresponding proficiency requirement will follow. A shift is a period of time for one or multiple workers of exactly the same qualifications to work together on exactly the same tasks. A shift gives the starting and ending time and a list of the qualification/ proficiency pairs associated with one or multiple ground crew. The number of shifts is limited relative to the number of tasks, so not all tasks are assigned, and the more important the tasks, the higher the priority. The benefit of a task is expressed as the product of “task duration” and “task priority”, so the goal is to maximize the total benefit of the assigned tasks.
In previous studies, on the basis of meeting other constraints between tasks and shifts, time constraints must also be fully met before they can be assigned. However, with the different off-peak seasons and the occurrence of temporary emergencies, the number of tasks at the airport will increase dramatically in a certain period of time, while personnel will be seriously insufficient. At this time, if the initial duration of tasks is completely covered, it is necessary to consider that the task will be fully covered. As a result, a large number of tasks cannot be assigned to the shift, reducing the utilization of the shift. In practice, airport tasks are allowed to start earlier or later in the duration of the task, so long as the working hours meet the partial coverage requirements, then the task is allowed to be fully performed in the case of expedited shifts. In addition, it can be found from the multiple attributes of tasks and shifts that in order to avoid waste of resources, arranging shifts that are similar to the requirements of task qualification and proficiency as far as possible to perform the corresponding tasks isconducive to improving the operation efficiency and service level of airports, and at the same time controlling the waste of resources, which is also the aspect that more and more airports pay attention to when solving the task assignment problem.
Airport task assignment problem belongs to NP-hard problem. Due to the multiple attributes of task and shift, this paper studies the problem of airport task assignment, which considers not only the maximum benefit of task but also the qualification and proficiency between task and frequency. An integer programming model is established, and according to the characteristics of tasks and shift in the research problem, the model is analyzed and effective inequalities are proposed. CPLEX optimization software is applied to simulate the actual data based on different factors. The numerical experiment results show that the feasibility and validity of the model. In addition, the accurate solution of large scale problem can be obtained within the acceptable time range. Meanwhile, the effect of effective inequality is tested and analyzed. It is found that the average value of the objective function can be increased by 9.6% even if the coverage is set as high as 80%. When qualification matching is also considered, the average value of the objective function can also be increased by 6.98%. Since tasks and shifts have multiple attributes, this paper also tests and analyzes two factors that affect the objective function: the qualification requirements of tasks and the working hours of shifts. The comparison of the test results considering the data of different attribute factors shows that reducing the qualification requirement of the task has the greatest impact on the objective function, and the increase in the average value of the objective function is as high as 27.96%, so the impact on the task completion rate is more intuitive. This conclusion is also in line with the reality, in order to reduce the task requirements, the airport every year through the staff training and qualification assessment to improve the level of staff. By comparing the test results of these examples, an instructive conclusion is drawn, that is, adjusting the two factors and the matching degree of task coverage and qualification respectively according to the characteristics of the problem can not only effectively improve the task completion rate and operation efficiency of the airport, but also control the waste of resources while maintaining a certain level of service. It can provide scientific basis for the actual operation decision of enterprises.

Key words: task part coverage, NP-hard problem, integer programming model, CPLEX optimization software