Asymmetric path-relinking based heuristics for large-scale job scheduling problem in TDRSS

In the busy-day scheduling scenario for tracking and data relay satellite system (TDRSS) provided by NASA, there are generally more than 400 jobs to be scheduled over two TDRSs, which builds up a large-scale job scheduling problem (LJSP) on multiple parallel machines. Since the global optima of such a LJSP can only be obtained with Non-deterministic Polynomial (NP) complexity, some classical heuristic algorithms, e.g., the GRASP, are often used to approach local optima with lower efficiency. In this paper, by fully exploiting the time-domain flexibility and statistical property of jobs´ slack time windows, a heuristic job scheduling framework is proposed to speed up the time convergence. The asymmetric path-relinking (APR) is firstly involved as a basic progressive operator, followed by the positive and negative adaptive subsequence adjustment (p/n-ASA) strategies, which are two adaptive construction and replacement mechanisms by maximizing usage the slack of jobs´ time windows. The key-path APR and hybrid evolutionary are further presented to accelerate the convergence. Simulation results show that, compared with the GRASP, our proposal can shorten the convergence time by almost 9 times, meanwhile with an improvement on the number of scheduled jobs.