2001 | OriginalPaper | Buchkapitel
A FPTAS for Approximating the Unrelated Parallel Machines Scheduling Problem with Costs
verfasst von : Eric Angel, Evripidis Bampis, Alexander Kononov
Erschienen in: Algorithms — ESA 2001
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We consider the classical problem of scheduling a set of independent jobs on a set of unrelated machines with costs. We are given a set of n monoprocessor jobs and m machines where each job is to be processed without preemptions. Executing job j on machine i requires time p ij ≥ 0 and incurs cost c ij . Our objective is to find a schedule obtaining a tradeoff between the makespan and the total cost. We focus on the case where the number of machines is a fixed constant, and we propose a simple FPTAS that computes for any ε > 0 a schedule with makespan at most (1 + ε)T and cost at most C opt (T), in time $$ \mathcal{O}\left( {n\left( {{n \mathord{\left/ {\vphantom {n \varepsilon }} \right. \kern-\nulldelimiterspace} \varepsilon }} \right)^m } \right) $$, given that there exists a schedule of makespan T, where C opt (T) is the cost of the minimum cost schedule which achieves a makespan of T. We show that the optimal makespan-cost trade-off (Pareto) curve can be approximated by an efficient polynomial time algorithm within any desired accuracy. Our results can also be applied to the scheduling problem where the rejection of jobs is allowed. Each job has a penalty associated to it, and one is allowed to schedule any subset of jobs. In this case the goal is the minimization of the makespan of the scheduled jobs and the total penalty of the rejected jobs.