Hall, Leslie A.Schulz, Andreas S.Shmoys, David B.Wein, Joel2022-05-112022-05-1119962197-8085https://depositonce.tu-berlin.de/handle/11303/16898http://dx.doi.org/10.14279/depositonce-15676In this paper we introduce two general techniques for the design and analysis of approximation algorithms for NP-hard scheduling problems in which the objective is to minimize the weighted sum of the job completion times. For a variety of scheduling models, these techniques yield the first algorithms that are guaranteed to find schedules that have objective function value within a constant factor of the optimum. In the first approach, we use an optimal solution to a linear programming relaxation in order to guide a simple list-scheduling rule. Consequently, we also obtain results about the strength of the relaxation. Our second approach yields on-line algorithms for these problems: in this setting, we are scheduling jobs that continually arrive to be processed and, for each time t, we must construct the schedule until time t without any knowledge of the jobs that will arrive afterwards. Our on-line technique yields constant performance guarantees for a variety of scheduling environments, and in some cases essentially matches the performance of our off-line LP-based algorithms.en510 Mathematikapproximation algorithmsNP-hard scheduling problemsweighted sum of the job completion timesResearch Paper