This is not the latest version of this item. The latest version can be found here.
Options
Single machine batch scheduling to minimize the weighted number of tardy jobs
Citation Link: https://doi.org/10.15480/882.4134
Publikationstyp
Preprint
Date Issued
2019-11-27
Sprache
English
Author(s)
Institut
TORE-DOI
TORE-URI
The 1|B,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 in 1994; as a wide generalization of {\sc Knapsack}, it is NP-hard.
In this work we provide a multivariate complexity analysis of the 1|B,rj|∑wjUj problem with respect to several natural parameters. That is, we establish a thorough classification into fixed-parameter tractable and W[1]-hard problems, for parameter combinations of (i) #p = distinct number of processing times, (ii) #w = number of distinct weights, (iii) #d = number of distinct due dates, (iv) #r = number of distinct release dates, and (v) b = batch sizes. Thereby, we significantly extend the work of Hermelin et al. (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|B,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|B,rj|∑wjUj is fixed-parameter tractable with respect to parameter #p+#d+#r and with respect to parameter #w+#d 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.
In this work we provide a multivariate complexity analysis of the 1|B,rj|∑wjUj problem with respect to several natural parameters. That is, we establish a thorough classification into fixed-parameter tractable and W[1]-hard problems, for parameter combinations of (i) #p = distinct number of processing times, (ii) #w = number of distinct weights, (iii) #d = number of distinct due dates, (iv) #r = number of distinct release dates, and (v) b = batch sizes. Thereby, we significantly extend the work of Hermelin et al. (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|B,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|B,rj|∑wjUj is fixed-parameter tractable with respect to parameter #p+#d+#r and with respect to parameter #w+#d 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.
DDC Class
620: Ingenieurwissenschaften
Loading...
Name
1911.12350.pdf
Size
509.37 KB
Format
Adobe PDF