Approximation of the parallel machine scheduling problem with additional unit resources

This problem appears in the design of download plans for Earth observation satellites, when scheduling the transfer of the acquired data to ground stations. Within this context, it may be required to process jobs by batches standing for the set of files related to a single observation. We show that there exists a (2−1m)-approximation algorithm respecting such batch sequences. Moreover, provided that the ratio ρ, between maximum and minimum processing times, is bounded by ⌊s−1m−1⌋, we show that the proposed algorithm approximates the optimal schedule within a factor 1+s−1n.