Iterative Rounding for Bag of Tasks Scheduling with Rejection in High Performance Computing

In this paper, we consider a scheduling model, called bag of tasks scheduling problem with rejection, which schedules n jobs on m unrelated parallel machines in high performance computing, where each job consists of a bag of tasks with a processing time and a rejection penalty. Each job is either accepted and all the tasks must be processed and incurs a cost, or rejected which incurs a rejection penalty. Finally, we obtain bi-criteria ( \(\frac{e}{e-1}\) , \(\frac{2e-1}{e-1}\) )-approximation for bag of tasks scheduling problem with rejection by using iterative rounding and linear programming rounding.