Paper Info
Title
Restricted Duplication Based MILP Formulation for Scheduling Task Graphs on Unrelated Parallel Machines.
Abstract
Duplication has proved to be a vital technique for scheduling task graphs on a network of unrelated parallel machines. Few attempts have been made to model duplication in a Mixed Integer Linear Program (MILP) to reduce schedule length. Other known optimal MILPs duplicate a job on all the available processing elements and this increases their complexities. This paper proposes a new REStricted Duplication (RESDMILP) approach to model duplication in a MILP. The complexity of this model increases with the increase in the amount of duplication. Experiments conducted have revealed that RESDMILP achieves better runtimes when the problem instance is solved optimally and provides better lower bound and percentage gap if it is run for a fixed amount of time. The percentage gap is defined as (U B - LB)/U B where U B and LB are the upper and lower bounds achieved by the MILPs respectively.
Year
DOI
Venue
2012
10.1109/PAAP.2012.37
PAAP
Keywords
Field
DocType
computational complexity,integer programming,linear programming,parallel machines,processor scheduling,RESDMILP,mixed integer linear program,percentage gap,restricted duplication based MILP formulation,schedule length reduction,task graph scheduling,unrelated parallel machines,Duplication,Heterogeneous,MILP,Multiprocessors,Scheduling
Integer,Graph,Mathematical optimization,Computer science,Scheduling (computing),Upper and lower bounds,Parallel computing,Integer programming,Linear programming,Gene duplication,Computational complexity theory
Conference
ISSN
Citations 
PageRank 
2168-3034
2
0.37
References 
Authors
0
4
Name
Order
Citations
PageRank
Jagpreet Singh1132.62
Bhargav Mangipudi220.37
Sandeep Betha320.37
Nitin Auluck4357.55