Search

The publications on two-machine flow shop scheduling problems with job dependent storage requirements, where a job seizes a portion of the storage space for the entire duration of its processing, were motivated by various applications ranging from supply chains of mineral resources to multimedia systems. In contrast to the previous publications that assumed that the availability of the storage space remains unchanged, this paper is concerned with a more general case when the availability is a function of time. It strengthens the previously published result concerning the existence of an optimal permutation schedule, shows that the variable storage space availability leads to the NP-hardness in the strong sense even for unit processing times, and presents a polynomial-time approximation scheme together with several heuristic algorithms. The heuristics are evaluated by means of computational experiments.

Bi-criteria lexicographical minimization problems with the makespan as the primary objective and the total machine assignment costs as the secondary objective have been recently introduced to the scheduling research, and polynomial time ( r + 1 , 1 ) -approximation algorithms have been suggested for their solution, where 1 r 2 is the performance ratio of an approximation algorithm for P | | C max . We improve these results by presenting a polynomial time ( 1.5 r − 1 , 1 ) -approximation algorithm for the additive cost type. Then, we introduce a problem of minimizing the total machine assignment cost over the Δ-approximate solutions of the makespan minimization problem. We prove that this new problem is strongly NP-hard and pseudo-polynomially non-approximable in general. A polynomial time approximation algorithm with a guaranteed approximation ratio is presented for the additive cost type and bounded ratio between the maximal and minimal machine costs. An O ( m n 2 k ) time dynamic programming algorithm is also presented, where k is the fixed number of distinct job processing times.

International audience; In this paper, we introduce a model for the speed scaling setting in the framework of explorable uncertainty. In the model, each job has a release time, a deadline and an unknown workload that can be revealed to the algorithm only after executing a query that induces a given additional job-dependent load. Alternatively, the job may be executed without any query, but in that case its workload is equal to a given upper bound. This assumption is motivated for instance in applications like code optimization, or file compression. We study the problem of minimizing the overall energy consumption for executing all the jobs in their time windows. We also consider the related problem of minimizing the maximum speed used by the algorithm. We present lower and upper bounds for both the offline case, where all the jobs are known in advance, and the online case, where the jobs arrive over time. We start with the single machine setting and we finally deal with the more general case where multiple identical parallel machines are available.

We consider a multistage framework introduced recently where, given a time horizon t=1,2,...,T, the input is a sequence of instances of a (static) combinatorial optimization problem I_1,I_2,...,I_T, (one for each time step), and the goal is to find a sequence of solutions S_1,S_2,...,S_T (one for each time step) reaching a tradeoff between the quality of the solutions in each time step and the stability/similarity of the solutions in consecutive time steps. For several polynomial-time solvable problems, such as Minimum Cost Perfect Matching, the multistage variant becomes hard to approximate (even for two time steps for Minimum Cost Perfect Matching). In this paper, we study the multistage variants of some important discrete minimization problems (including Minimum Cut, Vertex Cover, Set Cover, Prize-Collecting Steiner Tree, Prize-Collecting Traveling Salesman). We focus on the natural question of whether linear-programming-based methods may help in developing good approximation algorithms in this framework. We first show that Min Cut remains polytime solvable in its multistage variant, and Vertex Cover remains 2-approximable, as particular case of a more general statement which easily follows from the work of (Hochbaum, EJOR 2002) on monotone and IP2 problems. Then, we tackle other problems and for this we introduce a new two-threshold rounding scheme, tailored for multistage problems. As a first application, we show that this rounding scheme gives a 2$f$-approximation algorithm for the multistage variant of the f-Set Cover problem, where each element belongs to at most f sets. More interestingly, we are able to use our rounding scheme in order to propose a 3.53-approximation algorithm for the multistage variant of the Prize-Collecting Steiner Tree problem, and a 3.034-approximation algorithm for the multistage variant of the Prize-Collecting Traveling Salesman problem.

International audience; Bleuse et al. (EuroPar 2018) introduced a general model for interference-aware scheduling in large scale parallel platforms. They considered two different types of communications: the flows induced by data exchanges during computations and the flows related to Input/Output operations. Rather than taking into account these communications explicitly, they restrict the possible allocations of a job by external topological constraints. In their work, jobs are considered to be rigid: a job requires a specific number of machines in order to be executed. Here, we first adopt the same framework for the platform and the aforementioned topological constraints. We show that there is no polynomial time approximation algorithm under the rigid setting with ratio smaller than 3/2, unless P = NP. Then, we focus on the malleable setting. We show that in the proportional-malleable setting, where the work of every job remains constant independently of the number of machines on which it is executed, the scheduling problem remains NPhard even in the uniform case, where the maximum number of machines is the same for all the jobs. Then, we propose a 2-approximation algorithm for this case. Furthermore, we present an approximation algorithm solving the more general case where the maximum number of machines is job-dependent and the work of the jobs is increasing with respect to the number of used machines, due to the communication overhead.

We consider the Max k-Edge-Colored Clustering problem (abbreviated as MAX-k-EC). We are given an edge-colored graph with k colors. Each edge of the graph has a positive weight. We seek to color the vertices of the graph so as to maximize the total weight of the edges which have the same color at their extremities. The problem was introduced by Angel et al. [2]. We give a polynomial-time algorithm for MAX-k-EC with an approximation factor \(\frac{\mathbf {49}}{\mathbf {144}}\approx 0.34,\) which significantly improves the best previously known factor \(\frac{\mathbf {7}}{\mathbf {23}}\approx 0.304,\) obtained by Ageev and Kononov [1]. We also present an upper bound of \(\frac{\mathbf {241}}{\mathbf {248}}\approx 0.972\) on the inapproximability of MAX-k-EC. This is the first inapproximability result for this problem.

International audience; We consider a single machine, a set of unit-time jobs, and a set of unit-time errors. We assume that the time-slot at which each error will occur is not known in advance but, for every error, there exists an uncertainty area during which the error will take place. In order to find if the error occurs in a specific time-slot, it is necessary to issue a query to it. In this work, we study two problems: (i) the error-query scheduling problem, whose aim is to reveal enough error-free slots with the minimum number of queries, and (ii) the lexicographic error-query scheduling problem where we seek the earliest error-free slots with the minimum number of queries. We consider both the off-line and the on-line versions of the above problems. In the former, the whole instance and its characteristics are known in advance and we give a polynomial-time algorithm for the error-query scheduling problem. In the latter, the adversary has the power to decide, in an on-line way, the time-slot of appearance for each error. We propose then both lower bounds and algorithms whose competitive ratios asymptotically match these lower bounds.

In a so-called mixed-shop scheduling problem, the operations of some jobs have to be processed in a fixed order (as in the job-shop problem); the other ones can be processed in an arbitrary order (as in the open-shop problem). In this paper we present a new exact polynomial-time algorithm for the mixed-shop problems with preemptions and at most two unit operations per job.

In this paper we consider a problem of preemptive scheduling rigid parallel jobs on speed scalable processors. Each job is specified by its release date, its deadline, its processing volume and the number of processors, which are required for execution of the job. We propose a new strongly polynomial approximation algorithm for the energy minimization problem with migration of jobs.

International audience; We study the Max kk-colored clustering problem, where given an edge-colored graph with kk colors, we seek to color the vertices of the graph so as to find a clustering of the vertices maximizing the number (or the weight) of matched edges, i.e. the edges having the same color as their extremities. We show that the cardinality problem is NP-hard even for edge-colored bipartite graphs with a chromatic degree equal to two and k≥3k≥3. Our main result is a constant approximation algorithm for the weighted version of the Max kk-colored clustering problem which is based on a rounding of a natural linear programming relaxation. For graphs with chromatic degree equal to two we improve this ratio by exploiting the relation of our problem with the Max 2-and problem. We also present a reduction to the maximum-weight independent set (IS) problem in bipartite graphs which leads to a polynomial time algorithm for the case of two colors.

© 2015, Springer Science+Business Media New York. This study addresses a relocation scheduling problem that corresponds to resource-constrained scheduling on two parallel dedicated machines where the processing sequences of jobs assigned to the machines are given and fixed. Subject to the resource constraints, the problem is to determine the starting times of all jobs for each of the six considered regular performance measures, namely, the makespan, total weighted completion time, maximum lateness, total weighted tardiness, weighted number of tardy jobs, and number of tardy jobs. By virtue of the proposed dynamic programming framework, the studied problem for the minimization of makespan, total weighted completion time, or maximum lateness can be solved in (Formula presented.) time, where (Formula presented.) and (Formula presented.) are the numbers of jobs on the two machines. The simplified case with a common job processing time can be solved in (Formula presented.) time. For the objective function of total weighted tardiness or weighted number of tardy jobs, this problem is proved to be NP-hard in the ordinary sense, and the case with a common job processing length is solvable in (Formula presented.) time. The studied problem for the minimization of number of tardy jobs is solvable in (Formula presented.) time. The solvability of the common-processing-time problems can be generalized to the m-machine cases, where (Formula presented.).

In clustering problems one has to partition a given set of objects into some subsets (called clusters) taking into consideration only similarity of the objects. One of the most visual formalizations of clustering is the graph clustering, that is, grouping the vertices of a graph into clusters taking into consideration the edge structure of the graph whose vertices are objects and edges represent similarities between the objects.

Parallel jobs require more than one processor at the same time. We study speed scaling scheduling of parallel jobs with preemption. We propose “almost-exact” algorithms for problems with rigid jobs and single mode two-processor jobs. Based on configuration linear programs, our algorithms obtain an \(OPT + \varepsilon \) solution for any fixed \(\varepsilon > 0\).

International audience; We are given a set of jobs, each one specified by its release date, its deadline and its processing volume (work), and a single (or a set of) speed-scalable processor(s). We adopt the standard model in speed-scaling in which if a processor runs at speed . s then the energy consumption is . sα units of energy per time unit, where . α>1 is a small constant. Our goal is to find a schedule respecting the release dates and the deadlines of the jobs so that the total energy consumption to be minimized. While most previous works have studied the preemptive case of the problem, where a job may be interrupted and resumed later, we focus on the non-preemptive case where once a job starts its execution, it has to continue until its completion without any interruption. As the preemptive case is known to be polynomially solvable for both the single-processor and the multiprocessor case, we explore the idea of transforming an optimal preemptive schedule to a non-preemptive one. We prove that the preemptive optimal solution does not preserve enough of the structure of the non-preemptive optimal solution, and more precisely that the ratio between the energy consumption of an optimal non-preemptive schedule and the energy consumption of an optimal preemptive schedule can be very large even for the single-processor case. Then, we focus on some interesting families of instances: (i) equal-work jobs on a single-processor, and (ii) agreeable instances in the multiprocessor case. In both cases, we propose constant factor approximation algorithms. In the latter case, our algorithm improves the best known algorithm of the literature. Finally, we propose a (non-constant factor) approximation algorithm for general instances in the multiprocessor case.

In the classical vertex cover problem, we are given a graph \(G=(V,E)\) and we aim to find a minimum cardinality cover of the edges, i.e. a subset of the vertices \(C \subseteq V\) such that for every edge \(e \in E\), at least one of its extremities belongs to C. In the Min-Power-Cover version of the vertex cover problem, we consider an edge-weighted graph and we aim to find a cover of the edges and a valuation (power) of the vertices of the cover minimizing the total power of the vertices. We say that an edge e is covered if at least one of its extremities has a valuation (power) greater than or equal than the weight of e. In this paper, we consider Min-Power-Cover variants of various classical problems, including vertex cover, min cut, spanning tree and path problems.

In a bounded max-coloring of a vertex/edge weighted graph, each color class is of cardinality at most $b$ and of weight equal to the weight of the heaviest vertex/edge in this class. The bounded max-vertex/edge-coloring problems ask for such a coloring minimizing the sum of all color classes' weights. In this paper we present complexity results and approximation algorithms for those problems on general graphs, bipartite graphs and trees. We first show that both problems are polynomial for trees, when the number of colors is fixed, and $H_b$ approximable for general graphs, when the bound $b$ is fixed. For the bounded max-vertex-coloring problem, we show a 17/11-approximation algorithm for bipartite graphs, a PTAS for trees as well as for bipartite graphs when $b$ is fixed. For unit weights, we show that the known 4/3 lower bound for bipartite graphs is tight by providing a simple 4/3 approximation algorithm. For the bounded max-edge-coloring problem, we prove approximation factors of $3-2/\sqrt{2b}$, for general graphs, $\min\{e, 3-2/\sqrt{b}\}$, for bipartite graphs, and 2, for trees. Furthermore, we show that this problem is NP-complete even for trees. This is the first complexity result for max-coloring problems on trees., 13 pages, 5 figures

We propose a unifying framework based on configuration linear programs and randomized rounding, for different energy optimization problems in the dynamic speed-scaling setting. We apply our framework to various scheduling and routing problems in heterogeneous computing and networking environments. We first consider the energy minimization problem of scheduling a set of jobs on a set of parallel speed scalable processors in a fully heterogeneous setting. For both the preemptive-non-migratory and the preemptive-migratory variants, our approach allows us to obtain solutions of almost the same quality as for the homogeneous environment. By exploiting the result for the preemptive-non-migratory variant, we are able to improve the best known approximation ratio for the single processor non-preemptive problem. Furthermore, we show that our approach allows to obtain a constant-factor approximation algorithm for the power-aware preemptive job shop scheduling problem. Finally, we consider the min-power routing problem where we are given a network modeled by an undirected graph and a set of uniform demands that have to be routed on integral routes from their sources to their destinations so that the energy consumption is minimized. We improve the best known approximation ratio for this problem., Comment: 27 pages

International audience; We consider preemptive machine scheduling problems on identical parallel machines. It is shown that every such problem with chain-like precedence constraints, release dates and a regular unit-concave objective function (e.g. total weighted tardiness and total weighted number of late jobs) has the following integer preemption property: for any problem instance with integral input data there exists an optimal schedule where all interruptions (as well as starting and completion times of jobs) occur at integer time points.

International audience; In this work we show that certain classical preemptive shop scheduling problems with integral data satisfy the following integer preemption property: there exists an optimal preemptive schedule where all interruptions and all starting and completion times occur at integral dates. We also give new upper bounds on the minimal number of interruptions for various shop scheduling problems.