Bitte verwenden Sie diesen Link, um diese Publikation zu zitieren, oder auf sie als Internetquelle zu verweisen: https://hdl.handle.net/10419/315298 
Erscheinungsjahr: 
2024
Quellenangabe: 
[Journal:] Journal of Scheduling [ISSN:] 1099-1425 [Volume:] 27 [Issue:] 6 [Publisher:] Springer US [Place:] New York, NY [Year:] 2024 [Pages:] 545-556
Verlag: 
Springer US, New York, NY
Zusammenfassung: 
The 1-batch(∞),rjwjUjscheduling 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-batch(∞),rjwjUjproblem 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-batch(∞),rjwjUjis 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-batch(∞),rjwjUjis fixed-parameter tractable parameterized by #d+#p+#r, and parameterized by #d+#wif there is just a single release date. Both results hold even if the number of jobs per batch is limited by some integer b .
Schlagwörter: 
Scheduling
Single machine scheduling
Batch scheduling
Weighted number of tardy jobs
Fixed-parameter tractability
Persistent Identifier der Erstveröffentlichung: 
Creative-Commons-Lizenz: 
cc-by Logo
Dokumentart: 
Article
Dokumentversion: 
Published Version

Datei(en):
Datei
Größe





Publikationen in EconStor sind urheberrechtlich geschützt.