Using a sparse promoting method in linear programming approximations to schedule parallel jobs

摘要

In this paper, we tackle the well-known problem of scheduling a collection of parallel jobs on a set of processorsrneither in a cluster or in a multiprocessor computer. For the makespan objective, that is, the completionrntime of the last job, this problem has been shown to be NP-hard, and several heuristics have already beenrnproposed to minimize the execution time. In this paper, we consider both rigid and moldable jobs. Our mainrncontribution is the introduction of a new approach to the scheduling problem, based on the recent discoveriesrnin the field of compressed sensing. In the proposed approach, all possible positions and shapes of the jobsrnare encoded into a matrix, and the scheduling is performed by selecting the best columns under natural constraints.rnThus, the solution to the new scheduling formulation is naturally sparse, and we may use appropriaternrelaxations to achieve the optimization task in the quickest possible way. Among many possible relaxationrnstrategies, we choose to minimize the ℓ_p-quasi-norm for p∈(0,1). Minimization of the `p-quasi-norm isrnimplemented via a successive linear programming approximation heuristic. We propose several new algorithmsrnbased on this approach, and we assess their efficiency through simulations. The experiments show thatrnthe scheme outperforms the classic Largest Task First list based algorithm for scheduling small to mediumrninstances but needs improvements to compete on larger numbers of jobs.