On scheduling problems with parallel multi-purpose machines

Zsuzsanna Makai


In a multi-purpose machine scheduling problem, jobs can be processed by any machine of a prespecified subset of the machine-set. For the preemptive problem we give a combinatorial algorithm and obtain a min-max theorem for the minimal makespan. We give a combinatorial 2-approximation algorithm based on this algorithm for the non-preemptive case, which is NP-hard. We introduce a new special preemption rule: a job may be interrupted and resumed immediately on another machine. This version is also NP-hard, and a 2-approximation is presented.

Bibtex entry:

AUTHOR = {Makai, Zsuzsanna},
TITLE = {On scheduling problems with parallel multi-purpose machines},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2005},
NUMBER = {TR-2005-02}

Last modification: 29.12.2020. Please email your comments to Tamás Király!