TY - GEN
T1 - Increasing waiting time satisfaction in parallel job scheduling via a flexible MILP approach
AU - Schlagkamp, Stephan
AU - Hofmann, Matthias
AU - Eufinger, Lars
AU - Ferreira da Silva, Rafael
N1 - Publisher Copyright:
© 2016 IEEE.
PY - 2016/9/13
Y1 - 2016/9/13
N2 - Scheduling of jobs in parallel computing is crucial to efficiently use shared resources, while attaining user satisfaction. In this paper, we evaluate how mixed-integer linear programming (MILP) can be applied for the online parallel job scheduling problem (which is well-known to be an NP-complete problem). Therefore, we introduce the idea of planning horizons for parallel job scheduling, and provide a MILP formulation of the targeted scheduling problem. Due to the linear fashion of possible MILP objective functions, the proposed scheduling algorithm is flexible towards different optimization goals. We make use of data collected in a user-based study and workload traces from two real production systems, and demonstrate that our approach suffices to increase users' waiting time satisfaction. Additionally, we show that our MILP formulation outperforms the EASY scheduling technique with conservative backfilling, when neglecting the online character of job submissions.
AB - Scheduling of jobs in parallel computing is crucial to efficiently use shared resources, while attaining user satisfaction. In this paper, we evaluate how mixed-integer linear programming (MILP) can be applied for the online parallel job scheduling problem (which is well-known to be an NP-complete problem). Therefore, we introduce the idea of planning horizons for parallel job scheduling, and provide a MILP formulation of the targeted scheduling problem. Due to the linear fashion of possible MILP objective functions, the proposed scheduling algorithm is flexible towards different optimization goals. We make use of data collected in a user-based study and workload traces from two real production systems, and demonstrate that our approach suffices to increase users' waiting time satisfaction. Additionally, we show that our MILP formulation outperforms the EASY scheduling technique with conservative backfilling, when neglecting the online character of job submissions.
KW - Linear programming
KW - Parallel job scheduling
KW - user satisfaction
UR - http://www.scopus.com/inward/record.url?scp=84991693764&partnerID=8YFLogxK
U2 - 10.1109/HPCSim.2016.7568331
DO - 10.1109/HPCSim.2016.7568331
M3 - Conference contribution
AN - SCOPUS:84991693764
T3 - 2016 International Conference on High Performance Computing and Simulation, HPCS 2016
SP - 164
EP - 171
BT - 2016 International Conference on High Performance Computing and Simulation, HPCS 2016
A2 - Zeljkovic, Vesna
A2 - Smari, Waleed W.
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 14th International Conference on High Performance Computing and Simulation, HPCS 2016
Y2 - 18 July 2016 through 22 July 2016
ER -