Repository: DepositOnce â€“ institutional repository for research data and publications of TU Berlin https://depositonce.tu-berlin.de
TY - RPRT
AU - Skutella, Martin
AU - Verschae, Jos
PY - 2010
TI - A Robust PTAS for Machine Covering and Packing
DO - 10.14279/depositonce-14466
UR - http://dx.doi.org/10.14279/depositonce-14466
PB - Technische UniversitÃ¤t Berlin
LA - en
AB - Scheduling a set of n jobs on m identical parallel machines so as to minimize the makespan or maximize the minimum machine load are two of the most important and fundamental scheduling problems studied in the literature. We consider the general online scenario where jobs are consecutively added to and/or deleted from an instance. The goal is to always maintain a (close to) optimal assignment of the current set of jobs to the m machines. This goal is essentially doomed to failure unless, upon arrival or departure of a job, we allow to reassign some other jobs. Considering that the reassignment of a job induces a cost proportional to its size, the total cost for reassigning jobs must preferably be bounded by a constant r times the total size of added or deleted jobs.
KW - scheduling
KW - approximation
KW - online
KW - reassignment costs
KW - robustness
KW - ILP in constant dimension
ER -