الگوریتم های دقیق و هیوریستیک برای سوخت گیری هوایی برای مسئله برنامه ریزی ماشین های موازی با توجه به تاریخ عضویت و زمان آماده سازی

The Aerial Refueling Scheduling Problem (ARSP) can be defined as determining the refueling completion times for fighter aircrafts (jobs) on multiple tankers (machines) to minimize the total weighted tardiness. ARSP can be modeled as a parallel machine scheduling with ready times and due date-to-deadline window to minimize total weighted tardiness. ARSP assumes that the jobs have different ready times and a due date-to-deadline window between refueling due date and a deadline to return without refueling. In this paper, we first formulate the ARSP as a mixed integer programming model. The objective function is a piece-wise tardiness cost that takes into account due date-to-deadline windows and job priorities. Since ARSP is NP-hard, two heuristics are proposed to obtain solutions in reasonable computation times, namely (1) modified ATC rule (MATC), (2) a simulated annealing method (SA). The proposed heuristic algorithms are tested in terms of solution quality and CPU time through computational experiments with data randomly generated to represent aerial refueling operations of an in-theater air operation. Solutions provided by both algorithms were compared to optimal solutions for problems with up to 12 jobs and to each other for larger problems with up to 60 jobs. The results show that, MATC is more likely to outperform SA especially when the problem size increases, although it has significantly worse performance than SA in terms of deviation from optimal solution for small size problems. Moreover CPU time performance of MATC is significantly better than SA in both cases.

Aerial refueling (AR) is the process of transferring fuel from a tanker aircraft to a receiver aircraft during flight. AR is extensively used in large-scale military operations because of its advantages for an air force. In-theater aerial refueling is supported entirely through aerial refueling tracks (tracks 1 and 2 in Fig. 1), which are similar to gas stations floating in the sky. Empty alternative tracks 3–6 and wings 1–9 that are formed by various even numbers of aircrafts are also shown in Fig. 1. Tankers orbit in a track location with a constant speed and altitude waiting for receivers to arrive for refueling. The Aerial Refueling Scheduling Problem (ARSP) can be defined as determining the assignment of each fighter aircraft (job) to tanker (machine) and the refueling completion times for the aircrafts. ARSP assumes that aircraft wings stay together as a group, alternative track locations and assigned track stations (tracks 1 and 2) for the tankers are known, the number of tankers does not change during an operation (i.e., tankers replace each other without delay), and aircraft wings which move dynamically in the sky, can reach to available tankers in equal times.Since the fighting force endurance in the air operation is much more important than the fuel costs of the air operation, ARSP was modeled as receiver-based. Thus, fuel source is assumed continuous to supply the receivers’ demand without delay. ARSP can be modeled as an identical parallel machine scheduling problem with the tankers being machines and the aircraft fighters being jobs that have ready times (time they are available) and require certain amount of processing (refueling) time regardless to which tanker they are assigned. Minimizing the total weighted tardiness is a reasonable objective function to meet the aircrafts’ refueling due dates and ultimately the mission’s due date. Additionally, the aircrafts have a refueling deadline that they cannot miss; otherwise, they will have to go back to their base resulting in unscheduled jobs with a high cost. To effectively model both aspects of due dates and deadlines, a new piecewise tardiness cost function is defined to capture the cost structure over a time horizon that encompasses the due dates and deadlines. In this paper, a mixed integer linear programming (MILP) model will be developed to find optimal solutions for the problem. However, since the identical parallel machine scheduling is NP-hard even with only two machines (Blazewicz et al., 2007, Garey and Johnson, 1979 and Karp, 1972), ARSP is also NP-hard, which means that obtaining optimal solutions for large instances will be computationally difficult. Therefore, a composite dispatching rule, namely the Modified ATC (MATC) is proposed based on the commonly used Apparent Tardiness Cost (ATC) rule, which is often applied to total weighted tardiness problems. Dispatching (or priority) rules are very common heuristics for scheduling problems due to their easy implementation and low computational requirements. A Simulated Annealing (SA) metaheuristic is also developed for the problem at hand to compare the effectiveness of the proposed MATC rule for large instances. The rest of this paper is organized as follows. In Section 2, the ARSP is defined and mapped to the abstract scheduling problem. Related research is summarized in Section 3. A MIP for the problem is developed in Section 4 and solution methods are introduced in Section 5. A computational study for small and large problem sizes is described in Section 6. Finally results are concluded in Section 7.

This paper presented the ARSP, a real world problem that requires high quality solutions in an acceptable timeframe. ARSP was modeled as parallel machine scheduling problem with due date-to-deadline windows and dynamic ready times to minimize total weighted tardiness. As the dimensions of the problem get larger, the solution process of mathematical modeling loses its effectiveness. A new composite dispatching rule called MATC was developed to obtain good solutions quickly and its effectiveness was studied by comparing it with SA metaheuristic through computational experiments. MATC rule was modified from ATC rule keeping its main rationale of calculating priority index for the jobs waiting to be scheduled to deal with specific ARSP constraints such as d-to-D window and dynamic ready times. Computational experiments demonstrate that although MATC has significantly worse deviation performance from optimal solution than SA for small size problems, it is more likely to outperform SA when the problem size increases. Moreover CPU time of MATC is significantly shorter than SA in both cases. Starting initially from a better than random solution may be advantageous in problems like ARSP for which good solutions cannot be easily obtained. A good initial solution can reduce the CPU time considerably. Therefore, it is observed that the proposed MATC algorithm has potential to be used to construct good initial solutions that can be improved by another metaheuristic such as SA. In future research, more constraints such as machine compatibility, sequence dependent setup times and unexpected disruptions may be included in the model. Some hybrid metaheuristics using MATC as constructive heuristic may be developed to obtain better results.