Footnote:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Description:
This thesis is about scheduling problems where jobs arrive over time. Depending on the problem, we consider the case that each job has a deadline, or the relaxation that the sum of flow times or completion times need to be minimized. Since most of the discussed problems are NP-hard, the goal is to find polynomial time algorithms with provable approximation guarantee, preferably in an on-line setting. In the first part of this thesis, we consider batch scheduling problems for the case that each job has a deadline, and hence two jobs may be added to the same batch if their due intervals intersect. We first present a framework that unifies all batch cost structures discussed in this part. For instance max-batching, where the cost of each batch is the maximum weight of any contained job. We show that max-batching is strongly NP-hard in this context if the size of each batch is additionally restricted by a constant capacity constraint, and we also give a polynomial time approximation scheme (PTAS) for this case. Moreover, we consider a minmax-variant of max-batching which finds application in the area of data aggregation. We show that this variant is strongly NP-hard as well, and we present a quasi-polynomial time approximation scheme (QPTAS) and moreover a PTAS for the case that the due interval lengths are constants. Finally, we show that the closely related batch cost structure used in joint replenishment results in an APX-hard problem, which is hence not likely to admit an approximation scheme, but we show that it admits a randomized 5/3-approximation algorithm. In the second part of this thesis, multiprocessor scheduling problems are discussed. We give the first proof that the competitive ratio of the well-known algorithm SRPT is strictly smaller than 2 for completion time scheduling on identical machines. Specifically, we give the upper bound 1.86. Since it is harder to find approximation guarantees for flow time scheduling, we investigate this case in the context of speed-scaling, where it is allowed to ...