SOP Transactions on Applied Mathematics

## Approximation Algorithms for Subclasses of the Makespan Problem on Unrelated Parallel Machines with Restricted Processing Times

Daniel R. Page***
, Computer Science
, University of Manitoba, Winnipeg
, Canada

SOP Transactions on Applied Mathematics, Volume 2, Number 1, pp.20-27, 2015

### Keywords

Approximation Algorithms, Combinatorial Optimization, Computational Complexity, Scheduling, Unrelated Parallel Machines

### Abstract

Let there be m parallel machines and n jobs, where a job j can be scheduled on machine i to take pi, j ∈ Z+ time units. The makespan Cmax is the completion time of a machine that finishes last. The goal is to produce a schedule with all n jobs that has minimum makespan. This is the makespan problem on unrelated parallel machines, denoted as R||Cmax. Assume p,q ∈ Z+ are constants, let A(p,q) = {a ∈ Z+ | p ≤ a ≤ q}. We explore a general NP-hard subclass of R||Cmax when processing times are between p and q inclusive or pi,j=∞ abbreviated as R|pi,j ∈ A(p,q)∪{∞}|Cmax, where pi,j = ∞ means job j cannot be scheduled to machine i. We give a (q/p)-approximation algorithm for R|pi,j ∈ A(p,q)∪{∞}|Cmax. As a consequence, we obtain a 2-approximation algorithm for the NP-hard subclass R||Cmax with job lengths 1, 2, or pi,j=∞. In addition, we prove R||Cmax with job lengths 1, 2, and 3 is NP-hard, and present a 3/2-approximation algorithm for this subclass of R||Cmax.

### Cite this Article

Daniel R. Page

***, Approximation Algorithms for Subclasses of the Makespan Problem on Unrelated Parallel Machines with Restricted Processing Times, SOP Transactions on Applied Mathematics, Volume 2, Number 1, pp.20-27, 2015.### Reference

- Davis, Ernest and Jaffe, Jeffrey M, "Algorithms for scheduling tasks on unrelated processors", Journal of the ACM (JACM), 28, 4, 721--736, 1981
- Ebenlendr, Tomáš and Krčál, Marek and Sgall, Jiří, "Graph balancing: A special case of scheduling unrelated parallel machines", Algorithmica, 68, 1, 62--80, 2014
- Ebenlendr, Tomáš and Křcal, Marek and Sgall, Jiří,
*Graph balancing: a special case of scheduling unrelated parallel machines*, 483--490, 2008 - Gairing, Martin and Monien, Burkhard and Woclaw, Andreas, "A faster combinatorial approximation algorithm for scheduling unrelated parallel machines", Theoretical Computer Science, 380, 1, 87--99, 2007
- Michael, R Garey and David, S Johnson, "Computers and intractability: a guide to the theory of NP-completeness", WH Freeman o., San Francisco, 1979
- Graham, Ronald L and Lawler, Eugene L and Lenstra, Jan Karel and Kan, AHG, "Optimization and approximation in deterministic sequencing and scheduling: a survey", Annals of Discrete Mathematics, 5, 287--326, 1979
- Hopcroft, John E and Karp, Richard M, "An n\^{}5/2 algorithm for maximum matchings in bipartite graphs", SIAM Journal on Computing, 2, 4, 225--231, 1973
- Ibarra, Oscar H and Kim, Chul E, "Heuristic algorithms for scheduling independent tasks on nonidentical processors", Journal of the ACM (JACM), 24, 2, 280--289, 1977
- Lenstra, Jan Karel and Shmoys, David B and Tardos, Éva, "Approximation algorithms for scheduling unrelated parallel machines", Mathematical Programming, 46, 1-3, 259--271, 1990
- Shchepin, Evgeny V and Vakhania, Nodari, "An optimal rounding gives a better approximation for scheduling unrelated machines", Operations Research Letters, 33, 2, 127--133, 2005
- Svensson, Ola, "Santa claus schedules jobs on unrelated machines", SIAM Journal on Computing, 41, 5, 1318--1341, 2012
- Vakhania, Nodari and Hernandez, Jose Alberto and Werner, Frank, "Scheduling unrelated machines with two types of jobs", 2014