TUHH Open Research (TORE)https://tore.tuhh.deTORE captures, stores, indexes, preserves, and distributes digital research material.Thu, 01 Jun 2023 06:47:07 GMT2023-06-01T06:47:07Z5021Single machine batch scheduling to minimize the weighted number of tardy jobshttp://hdl.handle.net/11420/3924Title: Single machine batch scheduling to minimize the weighted number of tardy jobs
Authors: Hermelin, Danny; Mnich, Matthias; Omlor, Simon
Abstract: 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.
Wed, 27 Nov 2019 00:00:00 GMThttp://hdl.handle.net/11420/39242019-11-27T00:00:00ZScheduling with non-renewable resources: Minimizing the sum of completion timeshttp://hdl.handle.net/11420/7091Title: Scheduling with non-renewable resources: Minimizing the sum of completion times
Authors: Bérczi, Kristóf; Király, Tamás; Omlor, Simon
Abstract: We consider single-machine scheduling problems with a non-renewable resource. In this setting, there are n jobs, each characterized by a processing time, a weight, and a resource requirement. At given points in time, certain amounts of the resource are made available to be consumed by the jobs. The goal is to assign the jobs non-preemptively to time slots on the machine, so that each job has the required resource amount available at the start of its processing. We consider the objective of minimizing the weighted sum of completion times. The main contribution of the paper is a PTAS for the case of 0 processing times (formula presented). In addition, we show strong NP-hardness of the case of unit resource requirements and weights (formula presented), thus answering an open question of Györgyi and Kis. We also prove that the schedule corresponding to the Shortest Processing Time First ordering provides a 3/2-approximation for the latter problem.
Fri, 01 May 2020 00:00:00 GMThttp://hdl.handle.net/11420/70912020-05-01T00:00:00Z