1,720,960 research outputs found
Exponential neighborhood search for a parallel machine scheduling problem
No full textInternational audienceWe consider the parallel machine scheduling problem where jobs have different earliness-tardiness penalties and a restrictive common due date. This problem is NP-hard in the strong sense. In this paper we define an exponential size neighborhood for this problem and prove that finding the local minimum in it is an NP-hard problem. The main contribution of this paper is to propose a pseudo-polynomial algorithm that finds the best solution of the exponential neighborhood. Additionally, we present some computational results
Large neighborhood for a parallel scheduling problem with earliness-tardiness penalties and a common due date
No full textInternational audienceThis paper addresses the parallel machine scheduling problem where jobs have different earliness-tardiness penalties and a common due date. Since the problem is conjectured NP-hard in the strong sense, we propose a large neighborhood search that can be explored by a pseudo polynomial dynamic program algorithm. Computational experiments are presented and compared to a lower bound in order to verify that their gap is reasonable. They are also compared to simple local search based on moves and swaps between jobs
Voisinage exponentiel pour un problème d'ordonnacement avec des pénalités d'avance-retard autour d'une date d'échéance commune
No full textNational audienc
Lower bounds for the earliness-tardiness scheduling problem on parallel machines
No full textInternational audienc
Lower bounds for the earliness-tardiness scheduling problem on parallel machines
No full textInternational audienc
Lower bound for the earliness-tardiness scheduling problem on parallel machines with distinct due dates
No full textInternational audienceThis paper addresses the parallel machine scheduling problem in which the jobs have distinct due dates with earliness and tardiness costs. New lower bounds are proposed for the problem, they can be classed into two families. First, two assignment-based lower bounds for the one-machine problem are generalized for the parallel machine case. Second, a time-indexed formulation of the problem is investigated in order to derive efficient lower bounds throught column generation or Lagrangean relaxation. A simple local search algorithm is also presented in order to derive an upper bound. Computational experiments compare these bounds for both the one machine and parallel machine problems and show that the gap between upper and lower bounds is about 1.5%
A matching-related property of bipartite graphs with applications in signal processing
No full textA bipartite graph G = (L,R;E) is said to be identifiable if for every vertex v ∈ L,
the subgraph induced by its non-neighbors has a matching of cardinality |L| − 1.
This definition arises in the context of low-rank matrix factorization. Motivated by
signal processing applications, in this paper we (i) propose the robustness of identifiability
with respect to edge modifications as a polynomially computable measure
of evaluating how strongly a bipartite graph possesses the property of identifiability,
and (ii) introduce three problems that deal with finding identifiable subgraphs, and
study their complexity.ou
Going Beyond Counting First Authors in Author Co-citation Analysis
Get PDFThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
- …
