An effective scheduling algorithm for linear makespan minimization on unrelated parallel machines

A simple yet common scheduling problem is identified, as a special case of the R||C_max problem. We name it Linear Makespan Minimization on Unrelated Parallel Machines (LMMUPM). A novel algorithm, MOBSA (Multi-Objective Based Scheduling Algorithm), is presented to solve it. Two auxiliary problems are introduced as the basis of our algorithm. The first one can be reduced to a Multi-Objective Integer Program, while the second is constructed based on the solution of the first one. Results on random datasets revealed that MOBSA produced smaller and more stable makespans than other scheduling algorithms. Additionally, the makespan produced by MOBSA was within 1% of the optimum for every case. Presently, MOBSA has been applied to parallelize EMAN, one of the most popular software packages for cryo-electron microscopy single particle reconstruction. High speedups and ideal load balancing have been obtained. It is expected that MOBSA is also applicable to other similar applications.