Source author record

Óscar C. Vásquez

Óscar C. Vásquez appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Data Structures and Algorithms

Catalog footprint

What is connected

2works

1topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2016arXiv

The triangle scheduling problem

This paper introduces a novel scheduling problem, where jobs occupy a triangular shape on the time line. This problem is motivated by scheduling jobs with different criticality levels. A measure is introduced, namely the binary tree ratio. It is shown that the greedy algorithm solves the problem to optimality when the binary tree ratio of the input instance is at most 2. We also show that the problem is unary NP-hard for instances with binary tree ratio strictly larger than 2, and provide a quasi polynomial time approximation scheme (QPTAS). The approximation ratio of Greedy on general instances is shown to be between 1.5 and 1.05.

preprint2015arXiv

The local-global conjecture for scheduling with non-linear cost

We consider the classical scheduling problem on a single machine, on which we need to schedule sequentially $n$ given jobs. Every job $j$ has a processing time $p_j$ and a priority weight $w_j$, and for a given schedule a completion time $C_j$. In this paper we consider the problem of minimizing the objective value $\sum_j w_j C_j^β$ for some fixed constant $β>0$. This non-linearity is motivated for example by the learning effect of a machine improving its efficiency over time, or by the speed scaling model. For $β=1$, the well-known Smith's rule that orders job in the non-increasing order of $w_j/p_j$ give the optimum schedule. However, for $β\neq 1$, the complexity status of this problem is open. Among other things, a key issue here is that the ordering between a pair of jobs is not well-defined, and might depend on where the jobs lie in the schedule and also on the jobs between them. We investigate this question systematically and substantially generalize the previously known results in this direction. These results lead to interesting new dominance properties among schedules which lead to huge speed up in exact algorithms for the problem. An experimental study evaluates the impact of these properties on the exact algorithm A*.