الگوریتم های هیوریسیک برای تخصیص و برنامه ریزی ماموریت پرواز در یک واحد حمل و نقل هوایی نظامی

We consider an operations planning problem in a military aviation unit that performs a number of flight missions with multiple identical aircrafts. The problem is to assign the flight missions to the aircrafts and to schedule these assigned missions on each aircraft. Sequence-dependent setup times are required between the missions, and multiple aircrafts may be needed for a mission, but the aircrafts assigned to the same mission should start the mission simultaneously. We develop heuristic algorithms for the problem with the objective of minimizing makespan, i.e., the time by which all the missions have been completed. For evaluation of the performance of the algorithms, a series of computational tests was performed on a number of problem instances, and results show that the proposed algorithms give good or near optimal solutions in a reasonable amount of time.

In this paper, we consider an operations planning problem in the army aviation units of Korea. There are two types of aviation units in the army, assault units and mobility units. An assault unit performs missions of attacking enemy’s aircrafts, armors, and combat forces and protecting friendly units including mobility aviation units, while a mobility aviation unit conducts transportation missions such as moving infantry forces, ammunitions, and/or equipments to a place where they are needed. In this study, we focus on a scheduling problem in mobility aviation units. The problem considered is to assign transportation missions to each aircraft and to schedule these assigned missions on each aircraft for the objective of completing a given set of missions as early as possible. (Most, if not all, aircrafts in the aviation units are helicopters.) An aircraft has a limited capacity in terms of volume and weight that can be loaded on it. A mission is defined as a task to move combat forces or freights from one point to another point for further operations. If the capacity of an aircraft is not large enough to handle a mission, multiple aircrafts are needed to perform the mission. In this case, it is assumed that the aircrafts should start the mission simultaneously. This is because aircrafts may be easily attacked by the enemy after taking off from the starting point of the mission. Note that if multiple aircrafts perform the mission simultaneously they can mutually protect each other from attacks of the enemy. To perform a mission, an aircraft should move from the base to the starting point (origin) of the mission and then to the end point (destination) of the mission, and finally back to the base. The flight time from the base to the starting point of the mission can be considered as setup time and that from the end point of the mission to the base as set-down time. An aircraft may perform multiple missions consecutively before returning to the base. In this case, there should be setup time between two missions, i.e., flight time from the end point of the preceding mission to the starting point of the succeeding mission. Note that such setup times depend on the sequence of the missions. In this study, we regard the time to move from the end point of a mission to the starting point of the next mission as the setup time for the latter mission and we do not consider set-down time of the former mission or assume the set-down time is zero. This study focuses on the mission scheduling problem with the objective of minimizing makespan i.e., the time by which all the missions have been completed. This problem may be considered as a parallel-processor scheduling problem. However, while it is assumed that a task can be scheduled on only one machine in most research articles on parallel-machine scheduling problems, a task (mission) may have to be performed by multiple machines (aircrafts) in our problem if resource required for the task exceeds the capacity of the machine. The mission scheduling problem is similar to the split delivery vehicle routing problem (SDVRP) presented by Archetti and Speranza, 2006 and Kang and Lee, 2007, in which the demand of a customer exceeds the capacity of a vehicle and multiple vehicles are used for the delivery of the demand. Note that aircrafts and missions in our problem may be regarded as vehicles and deliveries for the customers, respectively, in the SDVRP. The mission scheduling problem is also similar to the multi-processor task scheduling problem (MTSP), in which each task needs to be processed on a number of parallel processors simultaneously. However, in our problem, sequence-dependent setup times are required between tasks, and hence our problem can be considered as a generalized version of the SDVRP and MTSP. Since the SDVRP and MTSP are proven to be NP-hard by Archetti and Speranza, 2006 and Błażewicz et al., 1986, respectively, the mission scheduling problem considered in this paper is also NP-hard. There have been many studies on the problem of scheduling jobs on identical parallel machines with the objective of minimizing makespan, which is shown to be NP-complete even in the two-machine case (Garey & Johnson, 1979). Various heuristic algorithms have been developed for the problem including those of Blackstone and Phillips, 1981, Lee and Massey, 1988, França et al., 1994, Hübscher and Glover, 1994, Ho and Wong, 1995, Gupta and Ruiz-Torres, 2001, Mokotoff et al., 2001, Hwang and Kim, 2003, Akyol and Bayhan, 2006 and Kashan and Karimi, 2009, while the worst-case performance is analyzed for simple heuristic algorithms in Graham, 1969 and Coffman et al., 1978. On the other hand, Dell’Amico and Martello (1995) propose a branch and bound algorithm, and Mokotoff (2004) presents a cutting plane method for optimal solutions. There are a number of research articles on multiple-machine scheduling problems for jobs with sequence-dependent setup times. Guinet, 1993, França et al., 1996, Gendreau et al., 2001, Mendes et al., 2002 and Behnamian et al., 2009 develop heuristic algorithms for identical parallel machine problems with the objective of minimizing makespan, while Kurz and Askin (2001) present heuristics considering release dates of jobs. In addition, Helal et al., 2006 and Rabadi et al., 2006 present heuristic algorithms for unrelated parallel machine problems with the makespan criterion, and Das et al., 1995, Ríos-Mercado and Bard, 1998, Ríos-Mercado and Bard, 1999, Norman, 1999, Ruiz et al., 2005 and Ruiz and Stützle, 2008 develop heuristics for flowshop scheduling problems with the makespan criterion. See Allahverdi, Ng, Cheng, and Kovalyov (2008) for a survey on studies on multi-machine scheduling problems with setups. There also have been various studies on the multi-processor task scheduling problem (MTSP), especially on the following two cases: the one in which a job (task) should be processed by a fixed (and pre-specified) number of machines that can be arbitrarily selected, and the one in which a set of machines is pre-specified for each job. For the first case, Błażewicz et al. (1986) show that there exists a polynomial-time algorithm for the problem with the objective of minimizing makespan when the processing times for all jobs are equal. Later, Błażewicz, Drozdowski, Schmidt, and Werra (1990) extend the study for a preemptive scheduling case in which each job can be processed on one of parallel processor groups, each with one or two processors. In addition, Chen and Lai, 1991, Zhu and Ahuja, 1993, Lin and Chen, 1994, Oğuz and Ercan, 1997, Li et al., 1998 and Sung and Park, 1998 consider the first case and give heuristic algorithms for the makespan criterion. The second case is dealt with in Bozoki and Richard, 1970, Bianco et al., 1994, Krämer, 1997, Bianco et al., 1999, Chen and Lee, 1999 and Caramia and Giordani, 2010. See Drozdowski, 1996 and Lee et al., 1997 for reviews on research papers on MTSPs. In this study, we focus on the problem of assigning given missions to aircrafts and scheduling the assigned missions on the aircrafts while considering sequence-dependent setup times between the missions and the constraint that individual tasks for the same mission should be started simultaneously if the mission needs to be performed by more than one aircraft. We develop heuristic algorithms for the mission assignment/scheduling problem with the objective of minimizing makespan. This paper is organized as follows. In the next section, we describe the problem in more detail and present an integer programming formulation for the problem. Heuristic algorithms developed for the problem are presented in Section 3. To evaluate performance of the proposed heuristics, computational experiments are performed on randomly generated problem instances and results are reported in Section 4. Finally, Section 5 concludes the paper with a short summary and recommendations for further research.

In this paper, we proposed heuristic algorithms for a mission assignment and scheduling problem in a military aviation unit with the objective of minimizing makespan. We considered situations in which a flight mission is to be performed by one or more aircrafts and tasks for a mission should be started simultaneously if multiple aircrafts are needed for the mission. In the heuristics, solutions are represented with sequences of missions, and we presented methods to convert a (partial) sequence of missions into a solution (assignment and schedule). We proposed two-phase heuristic algorithms in which an initial solution is obtained in the first phase and it is improved in the second phase. Results of experimental tests showed that the proposed heuristics give good or near-optimal solutions within a reasonable amount of computational time. This research can be extended in several directions. For example, metaheuristics such as tabu search, simulated annealing, and genetic algorithms can be used in the second phase (if more time is allowed for mission assignment and scheduling). In this research, it is assumed that the number of aircrafts required for a mission is given and fixed. However, in many cases, where tasks for a mission can be performed sequentially (not simultaneously), the operations planning officer of an aviation unit can or may have to determine the number of aircrafts to perform each mission. In this case, an aircraft can perform multiple unit-jobs of a mission, and individual unit-jobs need to be assigned to the aircrafts. Also, one needs to consider cases in which there are different types of aircrafts and certain missions require specific and/or multiple types of aircrafts with different capacities from different aviation units. Although we focused on the aircraft mission scheduling problem in this research, the solution methods proposed in this study may be applied (after certain modifications if needed) to other practical applications, such as diagnostic test in multicomputer systems (Krawczyk & Kubale, 1985), target assignment and fire sequencing (Kwon, Lee, & Park, 1997), berth allocation in a container terminal (Guan, Xiao, Cheung, & Li, 2002), and operation of real-time machine-vision systems (Oğuz & Ercan, 2005), where a job can be processed by a number of machines at the same time.