TR-2005-02

On scheduling problems with parallel multi-purpose machines

Zsuzsanna Makai



Abstract

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:

@techreport{egres-05-02,
AUTHOR = {Makai, Zsuzsanna},
TITLE = {On scheduling problems with parallel multi-purpose machines},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2005},
NUMBER = {TR-2005-02}
}


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