2 results
Filters
Settings
Now showing1 - 2 of 2
- Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: with files , Serial batching to minimize the weighted number of tardy jobsThe 1|s-batch(∞),rj|∑wjUj scheduling problem takes as input a batch setup time Δ and a set of n jobs, each having a processing time, a release date, a weight, and a due date; the task is to find a sequence of batches that minimizes the weighted number of tardy jobs. This problem was introduced by Hochbaum and Landy (Oper Res Lett 16(2):79–86, 1994); as a wide generalization of Knapsack, it is NP-hard. In this work, we provide a multivariate complexity analysis of the 1|s-batch(∞),rj|∑wjUj problem with respect to several natural parameters. That is, we establish a classification into fixed-parameter tractable and W[1]-hard problems, for parameter combinations of (i) #p = number of distinct processing times, (ii) #w = number of distinct weights, (iii) #d = number of distinct due dates, (iv) #r = number of distinct release dates. Thereby, we significantly extend the work of Hermelin et al. (Ann Oper Res 298:271–287, 2018) who analyzed the parameterized complexity of the non-batch variant of this problem without release dates. As one of our key results, we prove that 1|s-batch(∞),rj|∑wjUj is W[1]-hard parameterized by the number of distinct processing times and distinct due dates. To the best of our knowledge, these are the first parameterized intractability results for scheduling problems with few distinct processing times. Further, we show that 1|s-batch(∞),rj|∑wjUj is fixed-parameter tractable parameterized by #d+#p+#r, and parameterized by #d+#w if there is just a single release date. Both results hold even if the number of jobs per batch is limited by some integer b.Publicationtype: Journal Article49 24 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Interval scheduling and colorful independent setsNumerous applications in scheduling, such as resource allocation or steel manufacturing, can be modeled using the NP-hard Independent Set problem (given an undirected graph and an integer $$k$$k, find a set of at least $$k$$k pairwise non-adjacent vertices). Here, one encounters special graph classes like 2-union graphs (edge-wise unions of two interval graphs) and strip graphs (edge-wise unions of an interval graph and a cluster graph), on which Independent Set remains $$\mathrm{NP}$$NP-hard but admits constant ratio approximations in polynomial time. We study the parameterized complexity of Independent Set on 2-union graphs and on subclasses like strip graphs. Our investigations significantly benefit from a new structural “compactness” parameter of interval graphs and novel problem formulations using vertex-colored interval graphs. Our main contributions are as follows:1.We show a complexity dichotomy: restricted to graph classes closed under induced subgraphs and disjoint unions, Independent Set is polynomial-time solvable if both input interval graphs are cluster graphs, and is (Formula presented.)-hard otherwise.2.We chart the possibilities and limits of effective polynomial-time preprocessing (also known as kernelization).3.We extend Halldórsson and Karlsson (2006)’s fixed-parameter algorithm for Independent Set on strip graphs parameterized by the structural parameter “maximum number of live jobs” to show that the problem (also known as Job Interval Selection) is fixed-parameter tractable with respect to the parameter (Formula presented.) and generalize their algorithm from strip graphs to 2-union graphs. Preliminary experiments with random data indicate that Job Interval Selection with up to 15 jobs and (Formula presented.) intervals can be solved optimally in less than 5 min.Publicationtype: Journal Article120