Refine
Language
- English (13)
Keywords
- Container terminal (1)
- Integer programming (1)
- Storage space allocation (1)
- Yard crane scheduling (1)
- approximation (1)
- approximation scheme (1)
- competitive analysis (1)
- online (1)
- online scheduling (1)
- scheduling (1)
We study two related problems in non-preemptive scheduling and packing of malleable tasks with precedence constraints to minimize the makespan. We distinguish the scheduling variant, in which we allow the free choice of processors, and the packing variant, in which a task must be assigned to a contiguous subset of processors.
For precedence constraints of bounded width, we completely resolve the complexity status for any particular problem setting concerning width bound and number of processors, and give polynomial-time algorithms with best possible performance. For both, scheduling and packing malleable tasks, we present an FPTAS for the NP-hard problem variants and exact algorithms for all remaining special cases. To obtain the positive results, we do not require the common monotonous penalty assumption on processing times, whereas our hardness results hold even when assuming this restriction.
With the close relation between contiguous scheduling and strip packing, our FPTAS
is the first (and best possible) constant factor approximation for (malleable) strip packing under special precedence constraints.
We consider scheduling to minimize the weighted sum of completion
times on a single machine that may experience unexpected changes in
processing speed or even full breakdowns. We design a polynomial
time deterministic algorithm that finds a robust prefixed scheduling
sequence with a solution value within~$4$ times the value
an optimal clairvoyant algorithm can achieve, knowing the
disruptions in advance and even being allowed to interrupt jobs at
any moment. A randomized version of this algorithm attains in
expectation a ratio of~$e$ w.r.t. a clairvoyant optimum.
We show that such a ratio can never be achieved by any deterministic
algorithm by proving that the price of robustness of any such
algorithm is at least~$1+\sqrt{3} \approx 2.73205>e$.
As a direct consequence of our results, the question whether a
constant approximation algorithm exists for the problem with given
machine unavailability periods is answered affirmatively. We
complement this result by an FPTAS for the preemptive and non-preemptive special case with a single
non-available period.
We propose a new approach to competitive analysis by introducing the novel concept of online approximation schemes. Such scheme algorithmically constructs an online algorithm with a competitive ratio arbitrarily close to the best possible competitive ratio for any online algorithm. We study the problem of scheduling jobs online to minimize the weighted sum of completion times on parallel, related, and unrelated machines, and we derive both deterministic and randomized algorithms which are almost best possible among all online algorithms of the respective settings. Our method relies on an abstract characterization of online algorithms combined with various simplifications and transformations. We also contribute algorithmic means to compute the actual value of the best possible competitive ratio up to an arbitrary accuracy. This strongly contrasts all previous manually obtained competitiveness results for algorithms and, most importantly, it reduces the search for the optimal competitive ratio to a question that a computer can answer. We believe that our method can also be applied to many other problems and yields a completely new and interesting view on online algorithms.