Name
Abstract | ||
|---|---|---|
Agile earth observing satellites(AEOS) scheduling problem has drawn much research attention in the last few years due to its wide range of applications in both military and civilian areas. Recently, a state-of-the-art adaptive large neighborhood search algorithm(ALNS) was proposed for solving this problem where a dichotomy algorithm was used to calculate the time-dependent transition time. ALNS was demonstrated to be very effective in comparison to CPLEX and other heuristic algorithms at the time of publishment. However, we find two major drawbacks of ALNS. First, the imbalance between diversification and intensification leads to premature convergence; Second, the frequent invoke of the dichotomy algorithm leads to tremendous duplicate calculations and thus high computational complexity of ALNS. In this paper, we propose a simple and fast heuristic algorithm (SFHA) which is composed of an intensified local improvement procedure and a diversified perturbation operation. SFHA also includes a preprocessing procedure to precalculate all possible transition times, which avoids duplicate calculation and speeds up search process. Computational results show that the proposed SFHA outperforms ALNS in terms of both solution quality and computational time. In particular, SFHA consistently attains better solutions than ALNS in half of its running time. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1109/CEC.2018.8477736 | 2018 IEEE Congress on Evolutionary Computation (CEC) |
Keywords | Field | DocType |
adaptive large neighborhood search algorithm,ALNS,agile earth observing satellites scheduling problem,CPLEX,convergence,computational complexity,diversified perturbation operation,military areas,time-dependent AEOS scheduling problem,computational time,intensified local improvement procedure,SFHA,heuristic algorithms,time-dependent transition time,dichotomy algorithm,civilian areas | Mathematical optimization,Heuristic,Job shop scheduling,Premature convergence,Scheduling (computing),Computer science,Heuristic (computer science),Preprocessor,Memory management,Computational complexity theory | Conference |
ISBN | Citations | PageRank |
978-1-5090-6018-4 | 0 | 0.34 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ji Lu | 1 | 0 | 0.34 |
| Yuning Chen | 2 | 2 | 3.41 |
| Renjie He | 3 | 70 | 11.63 |
| Ying-wu Chen | 4 | 227 | 16.61 |