Name
Title | ||
|---|---|---|
Asymmetric path-relinking based heuristics for large-scale job scheduling problem in TDRSS |
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. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1109/CHINACOM.2014.7054270 | ChinaCom |
Keywords | Field | DocType |
parallel machines,polynomials,satellite communication,satellite tracking,telecommunication scheduling,time-domain analysis,ljsp,nasa,np complexity,tdrss,adaptive construction,asymmetric path-relinking based heuristics,busy-day scheduling scenario,heuristic job scheduling framework,hybrid evolutionary,job slack time windows,key-path apr,large-scale job scheduling problem,multiple parallel machines,negative adaptive subsequence adjustment,nondeterministic polynomial complexity,p/n-asa,positive adaptive subsequence adjustment,replacement mechanisms,statistical property,time-domain flexibility,tracking data relay satellite system,scheduling,sociology,convergence,switches,antennas,statistics | Mathematical optimization,Heuristic,Fair-share scheduling,Computer science,Scheduling (computing),Flow shop scheduling,Real-time computing,Least slack time scheduling,Rate-monotonic scheduling,Job scheduler,Dynamic priority scheduling | Conference |
Citations | PageRank | References |
1 | 0.36 | 3 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| peng lin | 1 | 39 | 12.10 |
| Linling Kuang | 2 | 193 | 31.60 |
| Xiang Chen | 3 | 190 | 25.05 |
| jian yan | 4 | 1 | 2.05 |
| Jianhua Lu | 5 | 1348 | 146.48 |
| Xiao-Juan Wang | 6 | 22 | 8.34 |