Options
Serial batching to minimize the weighted number of tardy jobs
Citation Link: https://doi.org/10.15480/882.13750
Publikationstyp
Journal Article
Date Issued
2024-10-22
Sprache
English
Institut
TORE-DOI
Journal
Volume
27
Issue
6
Start Page
545
End Page
556
Citation
Journal of Scheduling (2024)
Publisher DOI
Scopus ID
ArXiv ID
Publisher
Springer Science + Business Media
Peer Reviewed
true
The 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.
Subjects
Scheduling | Single machine scheduling | Batch scheduling | Weighted number of tardy jobs | Fixed-parameter tractability
DDC Class
620: Engineering
004: Computer Sciences
670: Manufacturing
Publication version
publishedVersion
Loading...
Name
s10951-024-00818-9.pdf
Size
439.28 KB
Format
Adobe PDF