Bartal, Yair; Leonardi, Stefano; Marchetti-Spaccamela, Alberto; Sgall, Jiří; Stougie, Leen Multiprocessor scheduling with rejection. (English) Zbl 0936.68012 SIAM J. Discrete Math. 13, No. 1, 64-78 (2000). Summary: We consider a version of multiprocessor scheduling with the special feature that jobs may be rejected at a certain penalty. An instance of the problem is given by \(m\) identical parallel machines and a set of \(n\) jobs, with each job characterized by a processing time and a penalty. In the on-line version the jobs become available one by one and we have to schedule or reject a job before we have any information about future jobs. The objective is to minimize the makespan of the schedule for accepted jobs plus the sum of the penalties of rejected jobs.The main result is a \(1+\phi\approx 2.618\) competitive algorithm for the on-line version of the problem, where \(\phi\) is the golden ratio. A matching lower bound shows that this is the best possible algorithm working for all \(m\). For fixed \(m\) we give improved bounds; in particular, for \(m=2\) we give a \(\phi\approx 1.618\) competitive algorithm, which is best possible.For the off-line problem we present a fully polynomial approximation scheme for fixed \(m\) and a polynomial approximation scheme for arbitrary \(m\). Moreover, we present an approximation algorithm which runs in time \(O(n\log n)\) for arbitrary \(m\) and guarantees a \(2-\frac{1}{m}\) approximation ratio. Cited in 2 ReviewsCited in 106 Documents MSC: 68M20 Performance evaluation, queueing, and scheduling in the context of computer systems 68Q25 Analysis of algorithms and problem complexity Keywords:multiprocessor scheduling; on-line algorithms; competitive analysis; approximation algorithms PDFBibTeX XMLCite \textit{Y. Bartal} et al., SIAM J. Discrete Math. 13, No. 1, 64--78 (2000; Zbl 0936.68012) Full Text: DOI