Unrelated parallel machines with release times and job rejection

We study the problem of scheduling on unrelated parallel machines with release times and job rejection. We design a simple greedy algorithm that achieves an (m+1)-approximation ratio, where m is the number of machines. We further develop a linear-programming-rounding algorithm with a 3-approximation guarantee. Then we present a pseudo-polynomial time dynamic programming algorithm that computes exact optimal solutions. Building upon this framework, we develop a fully polynomial-time approximation scheme (FPTAS) that combines scaling with dynamic programming to produce (1+ε)-approximate solutions when m is a fixed constant. Notably, when m=1 our FPTAS achieves a running time of O(n2/ε), improving upon the earlier O(n3/ε)-time FPTAS of Zhang et al. [European Journal of Operational Research, 198, 975 (2009)]. To evaluate the effectiveness of our methods, we design extensive computational experiments. To the best of our knowledge, this is the first work that develops both exact and approximation algorithms for unrelated machine scheduling with release times and job rejection.