Research Article
Asymmetric Path-Relinking Based Heuristics for Large-scale Job Scheduling Problem in TDRSS
@INPROCEEDINGS{10.4108/icst.chinacom.2014.256216, author={Peng Lin and Linling Kuang and Xiang Chen and Jian Yan and Jianhua Lu and Xiaojuan Wang}, title={Asymmetric Path-Relinking Based Heuristics for Large-scale Job Scheduling Problem in TDRSS}, proceedings={9th International Conference on Communications and Networking in China}, publisher={IEEE}, proceedings_a={CHINACOM}, year={2015}, month={1}, keywords={nonhomogeneous parallel machine scheduling problem with time window (npm-tw) asymmetric path-relinking (apr) positive/negative adaptive subsequence adjustment (p/n-asa)}, doi={10.4108/icst.chinacom.2014.256216} }- Peng Lin
Linling Kuang
Xiang Chen
Jian Yan
Jianhua Lu
Xiaojuan Wang
Year: 2015
Asymmetric Path-Relinking Based Heuristics for Large-scale Job Scheduling Problem in TDRSS
CHINACOM
IEEE
DOI: 10.4108/icst.chinacom.2014.256216
Abstract
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.